http://xys.3322.org/xys/ebooks/others/science/dajia8/zhuqingshi6.txt
◇◇新语丝(www.xys.org)(xys.dxiong.com)(xys.3322.org)(xys.xlogit.com)◇◇
朱清时也许还是看了点书的
雅诗
下面朱清时的这段话（引自柔能的文章）非常有趣。
【代数复杂性的概念可以作复杂性的现代定义的例子。至少在某种程度上，
一个系统的状态可以用一系列数据来描述，这些数据可用数字表示，它们构成一
个数列，因此我们只要定义这种数列的复杂性就行了。
考虑一个具体例子，比如:l、4、9、16、25、36等数字构成的数列，我们发
现这个数列可以由自然数n的平方得到。
每当给出一个数列时，我们就进行类似的研究，确定是否存在一个计算机程
序和一组初始数据(为了规范,假设均为图灵机)，用它们可以计算出整个数列？
它们若存在并能表达出来，则程序和初始数据的最短长度便是代数复杂程度的量
度；若它们的长度大得难以表达（甚至不存在)，则这样的系统就称为复杂系
统。】
这段话有趣的地方是把几种复杂度理论揉在一起了。图林机与最主要最基本
的复杂度理论， NP 理论（见柔能的文章），联系在一起。代数复杂性（复杂
度？）的英文为 algebraic complexity 吧， 也是一个很重要的理论， 跟 NP
理论有一定联系，考虑的也是计算所需要的时间空间等等。朱院士举的例子考虑
的是程序的长度，却有点像 Kolmogorov complexity (wiki 如下）， 哈哈. 像
那个斜眼的笑话了。 不过也许朱院士自己是明白的，只不过说得太通俗， 反而
让一些人（如我）糊涂了。
http://en.wikipedia.org/wiki/Kolmogorov_complexity
In computer science, the Kolmogorov complexity (also known as
descriptive complexity, Kolmogorov-Chaitin complexity, stochastic
complexity, algorithmic entropy, or program-size complexity) of an
object such as a piece of text is a measure of the computational
resources needed to specify the object.
(在计算机科学里,Kolmogorov complexity (也被认为是描述性复杂理
论,Kolmogorov-Chaitin complexity,随机复杂理论,算法熵,程序长度复杂理论)比如
某个对象好比是文本......???)
(XYS20070128)
◇◇新语丝(www.xys.org)(xys.dxiong.com)(xys.3322.org)(xys.xlogit.com)◇◇
Posts
