※ 引述《klain (klain)》之銘言：
: 而且，algorithmic complexity這個名稱好像也不多見，
: 還是你是想說Kolmogorov complexity?
: 綜觀下來，不知道你想說明的是什麼呢?
用 Turing machine 來計算的複雜度稱作 Turing machine complexity.
另外還有 Bit Complexity 之類的。
Kolmogorov complexity 則算是 algorithmic complexity 當中最主要的
一支吧，當然我並不熟悉。
我覺得本來這就是一種沒有精確定義的通稱，但意義應該是可以理解的。
: : 另外有不同領域但其實差不多的 program analysis 和 logical depth.
: : 其中 program analysis 就真的是研究最短的程式碼長度了。由於它
: : 比較不會陷入函數分析或 Turing Machine 中，看起來比較像電腦科學
: : 領域的東西。
: 請問你文中的"program analysis"跟"函數分析"是一樣的東西嗎?
: 又，如果是一樣的，有這名詞的定義嗎?
: 我想，可能需要更精確的了解名詞後再討論。
Program Analysis 比較有名的好像是這本書：
http://www.imm.dtu.dk/~riis/PPA/ppa.html
它的簡介：
http://www.imm.dtu.dk/~riis/PPA/summary.html
另外這裡有以前朋友給我看的一篇文章：
http://www.di.ens.fr/~cousot/publications.www/Cousot-81-PFA-ch10-p303-342.pdf
這東西有夠難，所有相關的東西，我從來就沒有真的看懂過。
: 亂入一下， XD
: logical depth是不是在討論計算機組織的時候的data path的長度呀?
不是。
logical depth 是 IBM 的 Charles Bennett 提出的東西。常常看見有人
提到，但就是沒看到資料。
: 這我也完全不懂，哈哈
: 以上有錯請訂正。
對了，這二篇簡介不錯：
What is Complexity?
http://bruce.edmonds.name/evolcomp/evolcomp_2.html
From Philosphy to Program Size
http://www.umcs.maine.edu/~chaitin/eesti.html
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.222.173.26