※ 引述《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