逻辑深度与元胞自动机计算机之父冯·诺伊曼对复杂性问题研究方法的贡献及其影响

逻辑深度与元胞自动机计算机之父冯·诺伊曼对复杂性问题研究方法的贡献及其影响

计算机之父冯诺伊曼的自动机理论经历了对“复杂性”的研究。他对复杂自动机,尤其是人的神经系统,未来的巨型计算机系统十分感兴趣,他想要建立复杂系统的逻辑组织理论,并相信这样的理论是建造大型计算机的最本质的前提。“在20世纪40年代早期,计算系统的复杂性还没有被清楚地认识。大多数早期计算机研究者的眼光没有超出元件设计、硬件工程的细节。冯·诺伊曼对计算机的发展产生重大影响的原因之一是他对计算系统复杂性的认识以及从不同方面对复杂性的贡献。”1算法信息的提出冯·诺伊曼提出了度量复杂性———“逻辑深度”(Logicaldepth)的概念。在比较自然和人工自动机的可靠性与复杂性时,他认为自然自动机和人工自动机的一个不同之处是计算组织不同,即自然自动机是并行运行而人工自动机序列运行的。在这里,他提出了一个计算的“逻辑深度”概念。一个计算包括许多基本逻辑步骤(开关、延迟),每步的结论都依赖于前面的步骤。冯·诺伊曼把每个依赖于前面步骤组成的序列称为“计算链”。计算的逻辑深度是它的最长的计算链的逻辑步骤的数字。由于计算机的高速度高效率,计算机常被用来完成极长逻辑深度的计算,最后的结果错误需限定在很小的概率内,这就要求每个逻辑步骤具有高度可靠性,所以冯·诺伊曼认为,自动机逻辑中的失败的可能性促使人们去考虑计算度的大小。数理逻辑的通常方法是去考虑一个自动机器是否能在有限步骤内完成某些任务,无论这个数字有多大,但是现实是计算数字越大,机器在计算中出错的可能性就越大。冯·诺伊曼没有建议如何去构造一个计算大小的理论,但“逻辑深度”概念的提出对度量计算的复杂性非常具有启发性意义:要准确把握复杂性的概念,我们需要考虑如何度量复杂性的问题。冯·诺伊曼的后继者勃克斯后来对这个理论做了研究,认为这个理论是建立在“计算的量”这个量的概念上,考虑到计算的深度(逻辑深度)和宽度(并行的量),计算的量的理论和错误的可能性必须包括连续数学和离散数学。沿着这个思路,在20世纪60年代,俄罗斯数学家柯尔莫哥洛夫(A.N.Kolmogorov)、美国数学家蔡廷(G.Chaitin)和索洛莫洛夫(R.Solomonoff)又分别提出“算法信息量”的概念。算法信息量是指一种计算机程序的长度。算法信息量的提出是基于这样的思想:为了确定一个具体的信息(比特)串的复杂性,先考虑一台理想的计算机(图灵机),它具有无限的存储能力;然后针对这一信息串,寻找一个计算程序,让这个程序在这台理想计算机上运行到打印出这个信息串,最后停机。一个能够生成该信息串的最短程序的长度便是它的算法信息量。20世纪80年代早期,美国物理学家贝内特(GBen-nett)为了刻画计算的复杂性,又提出了一个考虑到信息与付出这两个方面的概念:“逻辑深度”(Logi-caldepth),不过这个概念与冯·诺伊曼提出的逻辑深度概念的内涵不太一样。贝内特把对一个信息串或数据集的最似真说明等同于能产生该信息串或数据集的最短程序,然后再考虑这一程序的计算复杂性,他把从运行该程序开始到产生信息串所需的付出也叫做“逻辑深度”。贝内特的逻辑深度所指的是比特串、计算机程序和逻辑运算。逻辑上深的信息串具有更复杂的结构和行为。2计算机数值分析的目的和方法冯·诺伊曼是现代数值方法的创始人。19世纪早期,K.F.高斯(Gauss)对其进行了全面研究,在他的研究基础上,19世纪到20世纪早期发展应用数值方法是为了解决线性方程的小系统、倒置小矩阵、近似组合以及一般微分方程。冯·诺伊曼看到了计算机在无人干涉的情况下快速执行长序列运算的能力,并把此作为扩大数值技术应用领域的机遇。这个机遇包括研究线性方程大系统、更复杂的系统,偏微分方程以及它们在经典物理学、量子物理学、生物学、地球科学中的应用。冯·诺伊曼早在1940年就知道数值方法将使计算机成为时髦有效地科学工具,他也知道计算机将引起对数值分析这门学科的重新研究。他在设计IAS计算机的同时开始对数值分析进行思考,这个早早的开端使他成为对新计算机方向的数值分析感兴趣的早期科学家之一。他的一些结论持续影响了40年,蒙特-高利法(MonteGarlo)和线性算法是很好的例子;其它一些例子———譬如为解决PDES和大型矩阵的方法,调整冲击(Accomodationshocks)的方法以及解决数值稳定性分析法———他的工作虽然被后人大大地超越,但他的工作是第一步,他使这些问题的重要性成为人们注意焦点,并建设性地提出了解决方法。冯·诺伊曼认为数值方法的变化主要目的是为了让计算机更有效、更可靠的运行。计算机在一些关键方面与台式计算器及穿卡装置(Punched-cardequipment)这些先前进行数值分析的机器不同。计算机执行乘法运算是手动方法的105倍,但在存储数据、指令、中间计算结果的能力上严重地受到限制。而穿卡机卡片上可以无限制地储存大量信息,系统也非常可靠,但高速计算机装置中只能储存20到150个数字。对数值问题的复杂性以及计算装置的速度的分析令冯·诺伊曼和戈德斯汀(Godstine)相信偏微分方程、组合方程以及线性方程系统的新基础将被打破,但他们又担心数值稳定性问题———也就是,结果错误的积累与放大———将使过去150年数值方法发生改变成为必然。在1946年的报告《论巨型计算机的原则》中,冯·诺伊曼和戈德斯汀为计算机数值分析法列出了研究日程,这个研究工作从他们开始研究计算机起一直到冯·诺伊曼患癌症去世。倒置矩阵与解决线性方程系统的相关问题在数学中是非常普通的问题。在20世纪20年代,有许多种方法用于解决这个问题,但这些方法仅对于方程的小系统以及低阶矩阵,对小于20级的矩阵有用,是因为受乘法运算步骤的限制当时的计算只能用铅笔和纸或台式计算器。20世纪30年代,情况有所改变,主要是因为两个原因。哥伦比亚大学的WallaceEcket、英国国家年历办公室主任JComrie以及其他人主张穿卡分类与列表装置可有效地用于解决科学问题,用这个装置缓解了乘法运算步骤的限制,于是线性系统规模问题趋于解决。同时,科学正需要找到解决大型问题的方法———例如,在天文学以及飞机设计的动力分析中对电子工程的网络分析、对农业与心理学的统计分析以及对机械工程的结构分析等。为了满足这些需求,统计学家以及应用数学家在数值线性代数上做出了新的研究。解决高阶线性系统的方法是冯·诺伊曼研究计算机数值分析的主题之一。在二战中,他曾在研究所组织过一个研究小组为流体动力学研究做数值分析。ValentineBargmann和DeaneMontgomary是他的合作者。在1949年10月他们三人发表了一篇论文,分析了现有的解决大型线性系统的可靠性方法,并建议把重复方法(IterativeMethod)用于计算机。论文第一节比较了常见的解决线性系统算法的复杂性。用乘法的步骤数来测度解决一个线性系统所需的总时间。他们为每种计算方法确定了一个测度复杂性的级别,级别为n的系统的函数,他们估算了排除法为n研究者们也考虑到了数值稳定性。如果连串错误不可避免地在每个阶段出现而不累积起来破坏结果,那么一个计算方法被认为是数值稳定的。在做手动计算时,数值稳定性并不是严重的问题,因为在计算的数值上做了限制。所以这个问题还不被人重视。在使用高速计算装置时,它变得极为重要,因为计算机能执行数千次重复的数值过程。研究者们承认估算单独的数值方法的稳定性非常困难,但他们判定了排除法、分割法、正交法、决定法都不是稳定的,不适用于计算机。从他们的视角看,数值方法的稳定性比复杂性更重要。电子计算机,譬如ENIAC,比过去的计算装置快数千倍,所以使用者非常乐意在一个控制连串错误运算程序里加大计算的复杂性或步骤。由此,冯·诺伊曼小组选择了重复方法为最适用于高速计算机的方法。该方法在重复的步骤中得到所给定的精确程度非常有效,更重要的是它很稳定,为计算精确而起铺垫作用的额外数字少,算法可以实践应用于高速计算机。后来,冯·诺伊曼与戈德斯汀合作发表了两篇论文,主要是为了考查计算机装置中由噪声引起的累积起来的错误。第一篇论文他们从严格决定基础法对错误进行估算,但他们发现错误本质上象随意变体,所以他们建议使用概率法。第二篇论文研究了概率法。冯·诺伊曼在偏微方程的数值分析法中的贡献是研究了数值稳定性。在冯·诺伊曼的指导下,电子计算机工程成为计算机数值分析的重要中心。赫尔曼·戈德斯汀组织了大约50人在这个领域耕耘,并从与计算机的接触中受益。这个组织无疑是战后十年唯一活跃的数值分析研究中心。冯·诺伊曼是常客,在研究中心的各个方面做出了贡献,直到他成为原子能委员会委员因工作太繁忙而结束。在数学界以及政府部门中地位的提升有助于他呼吁的学科的合法化以及招募研究基金。由于以上所有理由,冯·诺伊曼被看作是现代数值分析的创始人。在复杂性科学的发展中,由于传统的数学解析方法对非线性、变系数及不规则复杂问题无法解决,只能依靠计算机辅助下的数值实验方法对复杂问题给出更系统、更丰富而直观的启示,因此数值方法变得得越来越重要。3德国法上的自然和外在表现冯·诺伊曼的元胞自动机为我们提供了一种新的建构方法:自下而上的方法。所谓“自下而上”的方法是指:“先从底部定义许多小的单元以及几条关系到它们内部的、完全是局部的相互作用的简单规则,从这些相互作用中产生出连贯的‘整体’行为,这种行为并不是根据特殊规则预先编好的。”冯·诺伊曼在亚瑟·勃克斯编辑整理的《自增殖自动机理论》第二章第二节中,详细介绍了元胞自动机模型的“态”及其转换规则。他认为元胞自动机模型是基于晶状媒介(Cristallinemedia)的,可以在二维空间里用平方(规则)晶格(Quadraticlat-tice)结构构造它。假定这个晶状体上的每个格点具有有限个不同的态(记为N态),其行为可以用明确的转换规则来描述或(控制)。转换规则中包含当其受近邻元胞影响时,这些态之间的转换。按照转换规则的步骤演化,元胞自动机会形成各种各样不同的复杂图案。元胞自动机的复杂行为并非预先设计好的,而是“涌现”出来的,涌现是指“在复杂的(非线性)形态中许多简单单元彼此相互作用时产生出来的引人注目的整体特性”在冯·诺伊曼的元胞自动机的启发下,剑桥大学数学家约翰·康韦(JohnCoway)于1970年编制了一个名为“生命”的游戏程序,他所用的二维元胞的状态以及这个模拟生态原理的行为规则是非常简单的,该程序只有几条简单的规则,但简单的行为通过相互作用和迭代运作后,模拟出了自然生命、人工生命的各种形态和现象,如代谢、生长、繁殖,进化与混沌边缘的多样性等。英国科学家沃尔弗拉姆从1986年起,在计算机上将元胞自动机用于模拟复杂现象。基于对元胞自动机的思考与研究,沃尔弗拉姆选择了一种由最简单的规则所构成的元胞自动机作为研究对象,“我采用一个简单的程序,然后让其系统地