Von Neumann：复杂性研究的先驱

2009-03-26 17:50:03 来自: jake

真实太怀念这个人了，下面是我们AI小组在上周日的讨论总结，贴过来晾一晾，希望更多的人能读到它。

Von Neumann 冯·诺依曼
　　
　　1) Von Neumann （1903-1957）其人
　　
　　Von Neumann出生于奥匈帝国布达佩斯，犹太人，从小就被誉为神童。之后由于战争原因，移居美国，就职普林斯顿高等研究院，与爱因斯坦、哥德尔等人相邻。Von Neumann早期从事纯数学理论的研究，领域涵盖了集合论与数理逻辑、量子力学的数学基础等领域。后来从事应用方面的研究，包括计算机科学（第一台电子计算机ENIAC）、自动机理论、计算流体力学、经济学与博弈论
　　
　　Von Neumann喜欢与政客和商界人士打交道，曾先后参与了迈哈顿计划，美国向日本投放原子弹的地点的决策，后成为美国军方的顾问。他还曾为IBM、RAND公司等商业机构作过兼职顾问。
　　Von Neumann经常穿着一身灰色的西服（甚至在打网球的时候），给人一种圆滑、事故的感觉。他喜欢社会交往，平均每周都有1~2次各界人士参与的家庭聚会。Von Neumann是着名的马路杀手，经常一年就要换一部车，因为他经常在开车的时候思考问题。
　　
　　2)《计算机与人脑》
　　
　　这本书是von Neumann留给我们的为数不多的着作之一（似乎是仅有的中文译作），这是他讲演稿的总结，主要比较了当时的计算机和人脑之间的共性与差异，其中很多观点对于现在的复杂性科学、人工智能研究仍然具有重要意义。
　　
　　下面概述一下von Neumann在本书中做出的结论。
　　对比计算机和人脑，我们发现：
　　1、在同样的时间内，人脑要比电脑完成更多的操作（这个结论对于目前的计算机来说已经不适用了）。
　　2、计算机比人脑具有更快的计算单元，但是整体性能却不如人脑。
　　3、计算机更多的采用串行的方法计算，而人脑更多采用并行的方式。
　　4、在记忆方面，计算机与人脑有很大不同。计算机的记忆相当于是局部、静态记忆的。而人脑的记忆则产生于通过神经元之间的连接构成的系统和信息传递的动态过程中。
　　5、从计算精度的角度来看，由于计算机实行的串行操作模式，因此误差就会在一系列串行操作的过程中累加，这就要求每个计算单元的计算精度必须特别小才能保证整体的精度。而人脑更多的采用并行的模式，因此，误差会在大量计算中抵消，从而导致即使每个部件的精度可能很低也能保证整体的计算精度较高。
　　6、计算机的技术系统是数字化的，而人脑使用的计数系统本质是统计的。
　　人脑传递消息的统计性质之一，就是频率。人脑采用频率编码，而不是直接的波形编码。这种编码的好处就是鲁棒性。试想一个波动信号传递，假如编码在波形之中，则一点小的改变就可能导致编码信息的丢失；而如果编码在频率中，则一次波形的小改变并不导致频率的整体畸变。
　　7、关于语言，计算机是使用数学语言为基础的。而人脑则是一种构建在“第一语言”之上的数学语言。也就是说人脑的语言基础可能不是数学语言。
　　
　　总结来看，计算机系统是一个用相当可靠、精确的部件构造而成的一个不可靠的系统，而人脑则是一个用不可靠、不精确的部件构造成的一个相当可靠的系统！
　　
　　3）《Theory of Self-reproducing Automata》
　　
　　关于本书：该书源自von Neumann在1940年代于Illinois大学做的一系列讲座。之后由von Neumann的助手密西根大学的Arthur Burk（John Holland的老师）整理、编辑出版。该书可分为两部分，第一部分是von Neumann的讲座，说明了von Neumann为什么要研究自复制自动机，以及他的理论根据。第二部分则是von Neumann设计的自复制自动机细节部分。
　　
　　个人以为，第一步非常经典，von Neumann当时思考的很多问题已经抓住了复杂性科学的本质，而且这些问题甚至对于现在来说仍极具指导意义。下面，我将摘录一些书中的原话，并展开一定的讨论。
　　Editor’s Introduction （Arthur Burk写的几段对本书的简短介绍）
　　“Finally, He (von Neumann) formulated and partially answered two basic questions of automata theory: How can reliable systems be constructed from unreliable components? What kind of logical organization is
　　sufficient for an automaton to be able to reproduce itself?”
　　这段话概括出来von Neumann当年设计自复制自动机的本质目的并不是想模拟或者理解生物体的自我复制，也并不是简单想制造自我复制的计算机病毒，他的最终目的是想回答一个理论问题：我们如何用一些不可靠的部件来构造出一个可靠的系统。而自复制自动机恰好就是一个最好的用不可靠部件构造的可靠的系统。这里，不可靠部件可以理解为构成生命的大量分子，由于热力学干扰，这些分子很不可靠。但是生命系统之所以可靠的本质，恰是因为它可以完成精确的自我复制。所以，自复制就是一个实例。
　　
　　“He thought, for example, that below a certain level, complexity is degenerative, and self-reproduction is impossible. He suggested that, generally speaking, in the case of simple automata a symbolic description of the behavior of an automaton is simpler than the
　　automaton itself, but that in the case of exceedingly complex automata the automaton is simpler than a symbolic description of its behavior.”
　　“Von Neumann mentioned two further connections between thermodynamics and automata theory. First, he found an analog of thermodynamic degeneration in the theory of self-reproducing automata: below a certain minimum level, complexity and degree of organization are
　　degenerative, but above that level they are not degenerative and may even increase.”
　　
　　这两段话概括了von Neumann关于进化论、热力学第二定律、复杂度和自复制自动机方面的想法。他说，任何一个系统（无论是人工的还是自然的），只要它的复杂性级别不够，那么由于热力学第二定律的作用，这个系统就会退化（degenerative）。对于这种简单自动机（Turing机），我们说这个自动机行为的符号描述（该Turing机的编码）要比这个自动机自身简单。但是，一旦系统的复杂度超过了一定级别之后，我们就能看到进化的现象
　　了。对于自动机来说，这意味着描述该自动机的代码（Turing机的编码）要比这个自动机本身的行为更复杂。那么，这个复杂性的阈值是什么呢？这就是自复制自动机，我们后面会看到，自复制自动机恰恰由于一个叫做“递归定理”的数学原理，使得它的行为表现和它的编码结构刚好形成了一个镜像对称（我们通俗
　　来说，这就叫自指，即图灵机的编码刚好在描述它自己！）。也就是说，自复制自动机刚好是一个时间箭头的分水岭，系统的复杂度小于自复制自动机，热力学时间箭头就会引起系统的衰退，而超过了这个复杂度，那么热力学时间箭头就会导致进化。
　　
　　“Everybody who has worked in formal logic will confirm that it is one of the technically most refractory parts of mathematics. The reason for this is that it deals with rigid, all-or-one concepts, and has very little contact with the continuous concept of the real or of the complex number, that is, with mathematical analysis. Yet analysis is the technically most successful and best elaborated part of mathematics. Thus formal logic is, by the nature of its approach, cut
　　off from the best cultivated portions of mathematics, and forced onto the most difficult part of the mathematical terrain, into combinatorics.”
　　这段话是Arthur Burk摘录的von Neumann的原话。他的意思是说，现在大部分研究逻辑或计算机的科学家对连续性的数学（例如实数、复数）即数学分析的分支都不闻不问。然而，数学分析才是数学中的大宝藏，数理逻辑这部分仅仅是一个角落而已。所以，von Neumann是非常强调把连续性数学的结论引入到自动机理论中的，即强调将计算机的逻辑部分和热力学及其信息论（连续数学）联系起来。
　　
　　“Second, he discussed the thermodynamic aspect of the concept of balance in computing machine design. The efficiency of a computer depends on the proper balance of its different parts with respect to speed and size. For example, in the memory hierarchy the different
　　kinds of memory (e.g. transistor, core, tape) should be matched to one another in size and speed. A computer in which the arithmetic unit is too fast for the memory, or the memory is too small, is like a heat
　　engine which is inefficient because large temperature differences exist between two parts of it. The efficiency of a computer must be defined relative to its environment (i.e., the problems it is to solve), just as the efficiency of a heat engine depends on its
　　environment. These problems of balance and matching are handled empirically by engineers. Von Neumann wanted a quantitative theory of balance akin to thermodynamics.”
　　这段话表达了von Neumann理解的复杂的计算系统和热力学系统之间的类比。计算系统需要协调各个计算单元之间的尺寸和速度，这就像热机需要协调各个部分的温度梯度使得机械效率增高一样。另外，热机的效率必须根据它与外界环境的协调性来定义，同样，计算系统的效率也需要外界沟通。这就说明了计算
　　系统的开放性其实与热力学系统的开放性有着一定深刻的联系。因此，von Neumann很想构造一套类似热力学的关于计算系统各个部件平衡方面的理论。
　　
　　接下来就进入了von Neumann讲稿的正题，综述了von Neumann当时的关于自动机理论、信息论等理论的进展情况，一步一步引出了自复制自动机方面的研究。我仍然摘抄一些经典语句。
　　
　　在叙述到关于Turing和Godel等人的工作的时候，他提到：
　　“I am twisting a logical theorem a little, but it’s a perfectly good logical theorem. It’s a theorem of Godel that the next logical step, the description of an object is one class type higher than the object and it’s absolutely necessary; it’s just a matter of complication when you get to this point. … They may easily be in this condition already, where doing a thing is quicker than describing it, where the circuit
　　is more quickly enumerated than a total description of all its functions in all conceivable conditions.”
　　这段话谈到了哥德尔的工作中蕴含的关于复杂性方面的研究。哥德尔和图灵等人研究的最大贡献在于他们开发了一套将机器和代码混合在一起的方法。这样，哥德尔就能采用这种具有“二义性”的语言来构造自指命题，从而提出了哥德尔定理。然而，除了如此应用哥德尔德的发明以外，我们还可以讨论它的复杂度和执行速度快慢。即把每个图灵机或者图灵机的编码赋予一个执行速度值，或者复杂度值。这样我们就讨论两件事情，一个是图灵机行为的复杂度，一个是图灵机代码的复杂度。所以，针对类似大脑这样的复杂系统来说，让它执行运算远比对它的运作机制进行描述来得要快。
　　
　　在回顾关于热力学和信息论的时候，他提到：
　　“Now this inclines one to view probability as a branch of logics, or rather, to view logics affected with probability as an extension of ordinary rigorous logics…. In more recent times the distinction was
　　emphasized strongly and made the basis of a system by the economist Keynes, who wrote his thesis on probability…. There are undeniable weaknesses of the logical position. In some ways of looking at
　　probability it is opportune not to identify zero probability with absurdity. Also, it is not quite clear in what sense a low probability means that one might expect that the thing will not happen…. Anyway,
　　one is also tempted in the case of quantum mechanics to modify one’s outlook on logics and to view probability as intrinsically tied to logics”
　　这段话谈到了von Neumann对概率论的看法，他认为我们可以把概率论理解为逻辑的一个分支，或者反过来，概率论是严格逻辑的一种延伸。这种观点与传统的对概率论的频率理解有很大的不同。着名的经济学家凯尔斯写过一本书叫做《A Treatise on Probability》，就是从逻辑的观点看待概率的。这种观点似乎能描述我们主观对概率事件的感受，例如，我们并不能接受：小概率事件就一定不能发生。这种情况与在量子力学中的情景很相
　　似，在那里，人们正试图修改对概率的理解，使得它可以和逻辑学相连。文中引了一本书《The logic of quantum mechanics》，作者是Von Neumann。
　　
　　“In other words, living organisms are very complicated aggregations of elementary parts, and by any reasonable theory of probability or thermodynamics highly improbable. That they should occur in the world at all is a miracle of the first magnitude; the only thing which removes, or mitigates, this miracle is that they reproduce themselves.
　　Therefore, if by any peculiar accident there should ever be one of them, from there on the rules of probability do not apply, and there will be many of them, at least if the milieu is reasonable. But a
　　reasonable milieu is already a thermodynamically much less improbable thing. So, the operations of probability somehow leave a loophole at this point, and it is by the process of self-reproduction that they are pierced.”
　　从概率论的角度来理解自我繁殖生命体自发涌现的问题是一个奇迹，它就仿佛是概率论中的一个漏洞。生命正是利用了这种漏洞的。因为任何一个有机体都是由大量部件构成的，从概率论的意义上来看，任何一种构型都是那么的不可能。然而，一旦生命这种构型具备了自繁殖的功能之后，它就能够钻进概率论留下的空隙中去。因为生命的自复制使得这种不可能的构型变成了必然发生的大概率事件了。
　　进一步，von Neumann指出了，这种自复制自动机不仅仅戳穿了概率论的阴谋诡计，而且还利用了概率论而实现进化！
　　
　　 “You can do one more thing. Let X be A+B+C+D, where D is any automaton. The (A+B+C)+d(A+B+C+D) produces (A+B+C+D)+d(A+B+C+D). … The system (A+B+C+D) can undergo processes similar to the process of mutation…. Self-reproduction includes the ability to undergo
　　inheritable mutations as well as the ability to make another organism like the original.”
　　Von Neumann指出了一个机器A+B+C+d(A+B+C)，（其中A是通用构造器、B是通用拷贝器，C是控制部件，d(A+B+C)是A,B,C这三个机器的源代码）是可以完成自我复制功能的，这个机器是根据计算理论中着名的递归定理构建的（递归定理就是自指的基础，也是哥德尔用来构造自我毁灭性的哥德尔定理的工具）。之后，对这个机器稍加改造就能创造出可进化的机器来。即假设由于热力学第二定律的作用，整个系统受到干扰产生变异。
　　如果变异发生在A,B,C身上，那么变异就是有害的，因为系统不能完成自复制。但如果变异发生在源代码部分，即d(A+B+C)变异为d(A+B+C+D)，那么这种变异就不会摧毁整个机器，而是创造出了一个新的机器A+B+C+D+d(A+B+C+D)。这个新的机器不仅仅由于变异获得了新功能D，而且他仍然具有自我复制的功能。也就是说，这为一种可遗传的变异提供了可能，也就是达尔文的进化方式。回顾一下，变异的出现恰是因为底层由概率论支配的热力学涨落，而自我繁殖机器恰恰是巧妙地利用了这种热力学涨落，而创造出了进化！
　　
　　4) 总结：
　　虽然在1930~50年代涌现出了很多科学大师，例如维纳、von Neumann等人，但是，相比较其他大师来说，von Neumann由于自己丰富的社会和工程经验，而能够提出一些更具体的问题出来。然而，很可惜的是，这些大师的思想并没有被后来的人们所继承，由于后人们的哲学高度没有达到von Neumann、Wiener等人的水平。而且，这些人的猜想过于超前，没有任何技术、数据的支持，所以人们根本不能理解这些大师们思考问题的出发点。于是，他们的徒子徒孙们继承的就全部是技术细节方面的东西，例如von Neumann和Ulam发明的元胞自动机受到了人们的欢迎。
　　Wiener的Cybernetics也变成了Control theory。
　　然而，随着近年来的研究，情况已经稍微改变。近年来，人们对复杂系统的研究已经上到了一个新台阶，大量数据的积累使得我们可以很确定的谈论复杂性现象。
　　因此，von Neumann当年的目标部分已经实现，例如他提倡构造一套可以描述自动机的概率理论。目前，复杂系统研究中，统计物理已经越来越显得重要。但是，由于现代的复杂性理论研究没有哲学思想的指导，使得人们虽然拥有大量的数据，却仍然是盲人摸象，不知道下一步会走向何方。例如，现在的复杂网络研究虽然很热，但是这么研究来研究去，我们究竟要得出一个什么结论呢？尽管有少数科学家已经开始思考构建复杂网络的热力学理论（例如Newman），但是这些目标离早期von Neumann的宏伟目标还差得挺远。我个人以为，沿着von Neumann设计的大致步骤，复杂系统理论的发展首先是在概率论上突破，借用量子力学的工具，重新给概率的主观、客观两种观点赋予含义。其次，人们就将利用新的概率论工具结合早年对计算理论的研究（哥德尔、图灵等人的工作），把概率论中的漏洞：自复制逻辑发现出来。到达这一天，人们对复杂系统，对生命和智能的本质将有全新的认识。