理解图灵机 姜咏江 1. 图灵机定义 图灵机用形式语言定义从维基百科摘抄如下： Following Hopcroft and Ullman (1979, p. 148), a (one-tape) Turing machine can be formally defined as a 7- tuple where Q is a finite, non-empty set of states Γ is a finite, non-empty set of tape alphabet symbols b∈ Γ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation) ∑ is the set of input symbols q0 is the initial state F is the set of final or accepting states . is a partial function called the transition function , where L is left shift, R is right shift. Anything that operates according to these specifications is a Turing machine. 按照现代计算机的观点，我理解如下： 图灵机 M 是一个七元组 M= ｛ Q ，Γ， b ，Σ，δ， q0 ， F ｝其中 1. Q 是一个非空有限状态集； 2. Γ是可输入到带子上非空有限字符集； 3. 空格 b 是带子上计算步骤的间隔符； 4. Σ是不包括空格的输入符号集； 5. δ是不包括 F 的 Q ×Γ空间到 Q ×Γ× {L,R ｝的函数，称为转换函数。 L 是左移， R 是右移； 6. q0 是初始状态； 7. F 是输入或结束状态。 任何机器符合以上七个条件，就是一个图灵机。 2. 如何理解图灵机 结合现代计算机，对七大条件的理解十分重要。 第一， Q 不能理解成程序的指令集，而应理解成解决问题的函数查找变化表。 第二，Γ是数据集，也就是往带子上写的数据。图灵机带子上数据和问题是在接收状态下用特殊方法写上去的，在运行状态可以由读写头改写。 第三，空格做为带子上单词或数据的分隔符，故不应包含在输入字符集中。 第四，转换函数δ是具有函数特性的规定。也就是每次从带子上读到一串问题和数据，都会转换成函数问题，解决的方法就是查表（表是函数的一种表达方式）。通过状态表可以找到问题的答案，然后将答案写入带子上的问题描述部分。读的过程，读写头要从左向右逐步移动，以便并实现理解问题的和数据，建立该问题的状态表，这些都是预先用表函数的方法建立好的。这一部分不是图灵机自身可以完成的事，是人们的思维结晶，是一种问题的解题方法。因而一切可解的问题的解法都在其中。 对于状态转换函数的理解是理解图灵机的关键。我们可以将图灵机运行解释以下： （ 1 ）输入状态是接收问题及数据的过程，也就是要把问题用Σ中的符号顺序写到带子上，不论单词或数据之间要用空格分开，才能辨认和理解。比如在带子上写上“求 3 加 2 的和”，这是中文描述，数学上可以写成 3+2 ＝。这一过程图灵机自己不能做，所以要有输入状态。这一状态图灵机不工作。 （ 2 ）图灵机要有开始工作的问题，这叫初始化状态 q0 。问题已经写到带子上了，那么图灵机的读写头位置一定要放在问题描述开始的地方。假如问题是从左向右写的，那么读写头就要从左向右逐个格子阅读，理解问题的本质。譬如读入“ 3 ”它就会在状态表中找到能够放置数的地方，读到“ + ”，它就要找到加法表，再读到“ 2 ”，它就应该在表中找到 3+2 ＝ 5 。查表的过程是图灵机自己完成的吗？实际还不是，是“他”完成的。他完成之后，将结果 5 通过读写头写到现在读写头的位置，因为问题已经解决了，覆盖掉问题在带子上的符号，不影响问题的解决。 （ 3 ）如果带子上写的问题很复杂，或者有好几个问题，那么读写头当然要移动。向右去读新的问题，向左往往是去处理尚未完全解决的问题。不要将左右移动读写头只是一个格子移动就要去查状态表，有时候要连续移动若干个格子，不进行读写。比如，重新解决前面描述的一些问题等，这要重新去读。 （ 4 ）停机状态是必须的。 F 除了是前面说的需要往带子上写问题之外，当问题已经完成之后，做为终结形式用停机状态最好。 在图灵机理解当中，第 5 条 is a partial function called the transition function , where L is left shift, R is right shift. Anything that operates according to these specifications is a Turing machine. 一般要理解清楚 partial function ，这是在不完全论域上的函数，function在这里理解成一般变元论域上的不完全映射比较更好。 如何构造转换函数，图灵机并没有解决。到了现代计算机的时代，从冯 . 诺依曼之后，这些问题才可以用机器运行实现。 2014-10-24
2011 第十三届全国 Petri 网理论与应用学术年会上的报告 报告题目： 谈谈无穷 Petri 网。 报告人： 郝克刚，西北大学信息与技术学院教授。 报告时间： 2011.8.20. 报告地点： 北京外国专家大厦二楼多功能厅。 内容简介： 一般在讨论和应用 Petri 网时，总假定 Petri 网的位置和转移集合是有穷集。如果允许它们是无穷集，则称其为无穷 Petri 网。不要以为所有的无穷 Petri 网系统都是难以捉摸，不可执行的。如果我们限制 所有的转移的入弧数和出弧数是有穷的 ，这样转移是否可激发就能够判定，而且激发后转移托肯的动作也是可以完成的。如果再加上每一步只允许执行有穷个互不冲突转移的激发的限制。无穷 Petri 网系统就可以同有穷 Petri 网系统一样地执行。我们把这样的无穷 Petri 网的子类称为可执行无穷 Petri 网。 报告着重介绍的是可执行无穷 Petri 网的一个子类，称为递归无穷 Petri 网。所谓递归是指：无穷 Petri 网由两个有穷 Petri 网（一个称基始一个称递归模版），按照如下的方法来动态地构造。以基始 Petri 网为基础，然后一个一个地同由递归模版逐个生成的具有同样结构的有穷 Petri 网，按照一定的方法串连起来。具体说就是用共享接口中的位置和转移的方法来动态地构造。系统的初始标识也按类似的方法构造。我们研究了这类网的某些属性。 有趣的是我们可以严格地证明，递归无穷 Petri 网同图灵机是等价的。即图灵机的结构以及操作执行过程，可以完全用递归无穷 Petri 网系统来描述和表达。从而解决了长期困惑我们的，无穷 Petri 网同图灵机是如何等价的问题。报告将简要介绍证明的思路。 作此报告，是想引起大家研讨这些理论问题的兴趣，听听同行们的看法、意见和建议。 讲稿： 递归无穷Petri网2011.pps
16日我应邀参加北师大举办的《2011国际莱布尼茨学术研讨会》，研讨会给每人35分钟的时间，其中25分钟为报告，10分钟为讨论。二者不可混用。我今天刚刚将参会的PPT文件赶制出来，明天就要报告了。现在将我的PPT文件的pdf版本传到网上，供大家批评指正。我的发言题目是:On Universal Number of Heaven and Earth, Leibniz's Universal Character and Universal Turing Machine (论大衍之数、莱布尼茨的普遍逻辑和通用图灵机）。但愿能对人有所启迪。 On UNHE, UC UTM.pdf
元胞自动机研究的相关理论方法 元胞自动机与相关理论和方法的发展有着千丝万缕的联系，一方面，元胞自动机的发展得益于相关理论的研究，如逻辑数学、离散数学、计算机中的自动机理论，图灵机思想;另一方面，元胞自动机的发展也促进了一些相关学科和理论(如人工智能、非线性科学、复杂性科学)的发展，甚至还直接导致了人工生命科学的产生。另外，在表现上，元胞自动机模型还与一些理论方法存在着较大的相似性，或者相对性。下面，我们对元胞自动机的一些相关理论方法，以及它们与元胞自动机模型的关系进行简要讨论。 1.元胞自动机与人工生命研究 人工生命是90年代才刚刚诞生的新生科学，是复杂性科学研究的支柱学科之一。人工生命是研究能够展示自然界生命系统行为特征的人工系统的一间科学，它试图在计算机、机器人等人工媒体上仿真、合成和生物有机体相关联的一些基本现象，如自我复制、寄生、竞争、进化、协作等，并研究和观察"可能的生命现象"(Life-as-it-could-be)，从而使人们能够加深理解"已知的生命现象"(Life-as-we-know-it)(Longton，C·G·，1987;吴建兵，1998)。 元胞自动机是人工生命的重要研究工具和理论方法分支，兰顿(Christopher Langton)等人正是基于对元胞自动机的深入研究提出和发展了人工生命。同时，人工生命的发展又为元胞自动机赋予了新的涵义，元胞自动机模型得到科学家们的重新认识和认可，并在90年代又一次成为科学研究的前沿课题，其理论和方法得到进一步的提高。另外，元胞自动机与其他的人工生命研究方法有着很大的相似性。元胞自动机模型与神经网络、遗传算法等其他人工生命方法一样，都是基于局部的相互作用，来研究系统的整体行为。另外，元胞自动机、神经网络、L—系统都可以归为非线性动力学中的网络动力学模型，它们相互联系，关系密切。目前，一种被称为元胞神经网络(Cellular Neural Network，简称CNN)的模型就是元胞自动机与神经网络结合的产物。 2.元胞自动机与"混沌的边缘" "混沌的边缘 (On the Edge of Chaos)(Langton C. G.，1992;M. Waldrop，1997)"是当前复杂性科学研究的一个重要成果和标志性口号，为圣塔菲(Santa Fee)学派的旗帜。所谓的"混沌"并非科学意义上的"混沌"，而是Chaos本身的原有涵义，即与有序相对的"混乱"、"无序"的概念。因此，"混沌的边缘"应当被理解为"混乱的边缘"。或"无序的边缘"，而与混沌动力学的"混沌"没有直接联系。其实，"混沌的边缘"完整的含义是指:生命等复杂现象和复杂系统存在和产生于"混沌的边缘"。有序不是复杂，无序同样也不是复杂，复杂存在于无序的边缘。 "混沌的边缘"这个概念是Norman Packard和Chhstopher Langton在对元胞自动机深入研究的基础上提出的，在此我们予以简要介绍。 Langton在对S. Wolfram动力学行为分类的分析和研究基础上，提出"混沌的边缘"这个响亮的名词，认为元胞自动机，尤其是第四类元胞自动机是最具创造性动态系统--复杂状态，它恰恰界于秩序和混沌之间，在大多数的非线性系统中，往往存在一个相应于从系统由秩序到混沌变化的转换参数。例如，我们日常生活中的水龙头的滴水现象，随着水流速度的变化而呈现不同的稳定的一点周期、两点或多点周期乃至混沌、极度紊乱的复杂动态行为，显然，这里的水流速度。或者说水压就是这个非线性系统的状态参数。Langton则相应地定义了一个关于转换函数的参数，从而将元胞自动机的函数空间参数比。该参数变化时，元胞自动机可展现不同的动态行为，得到与连续动力学系统中相图相类似的参数空间，Langton的方法加下 (谭跃进，1996): 首先定义元胞的静态(Quiescent State)。元胞的静态具有这样的特征，如果元胞所有领域都处于静态。则该元胞在下一时刻将仍处于这种静态(类似于映射中的不动点)。现考虑一元胞自动机，每个元胞具有k种状态(状态集为Σ)，每个元胞与n个相邻元胞相连。则共存在kn种邻域状态。选择k种状态中任意一种s∈Σ并称之为静态sq。假设对转换函数而言，共有nq种变换将邻域映射为该静态，剩下的kn-nq种状态被随机地、均匀地映射为Σ-{sq} 中的每一个状态。则可定义: 这样，对任意一个转换函数。定义了一个对应的参数值λ。随着参数λ由0到1地变化，元胞自动机的行为可从点状态吸引子变化到周期吸引子，并通过第四类复杂模式达到混沌吸引子 因此，第四类具有局部结构的复杂模式处于。秩序"与"混沌"之间，被称之为"混沌的边缘"，在上述的参数空间中。元胞自动机的动态行为(定性1具有点吸引于十周期吸引子-"复杂模式"-混沌吸引子这样的演化模式。同时，它又给元胞自动机的动力学行为的分类赋予了新的意义:即λ低于一定值(这里约为0.6)，那么系统将过于简单。换句话说，太多的有序而使得系统缺乏创造性;另外一个极端情况，λ接近1时。系统变的过于紊乱，无法找出结构特征;那么，λ只有在某个值附近，所谓"混沌的边缘"，系统使得极为复杂。也只有在此时，"生命现象"才可能存在。在这个基础上，兰顿提出和发展了人工生命科学。在现代系统科学中。耗散结构学指出"生命"以负墒为生，而Langton则创造性的提出生命存在于"混沌的边缘"。从另外一个角度对生命的复杂现象进行了更深层次 探讨的。 3.元胞自动机与微分方程 微分方程有着三百多年的发展历史。一批伟大的科学家，如Euler、Caus。Langrange、Laplace、Poisson都作出了卓越的贡献。而且，后来发展的偏微分万程对量子力学等现代物理学的产生相发展有着重要的意义，一大批的物理规律就是利用偏微分方程来惟理和表达的，如麦克斯维方程等。恩格斯还指出“自然界的统一性，显示在关于各种现象领域的微分方程的 '惊人类似'之中"。总之，微分方程是现代科学的语言，也是科学研究中最为重要的研究工具之一。 微分方程的主要特点是时间、空间均连续(如果方程中有空间因子的话），这是建立在时空连续的哲学认识基础上的。而元胞自动机则是完全的空间离散、时间离散，在这个意义上，微分方程和元胞自动机一对相对的计算方法 (Toffoli.T.，1987)。 在人工计算的情况下。由符号组成的(偏)微分方程可以灵活地进行约简等符号运算，而得到精确的定量解。这是其优势。但在现代计算机日益发展，已成为我们科学研究的重要工具时，微分方程却遇到了一个尴尬的问题。即计算机是建立在离散的基础上的，微分方程在计算时不得不对自身进行时空离散化，建立差分方程等;或者展开成幂系列方程，截取部分展开式;或者采用某种转换用离散结构来表示连续变量。这个改造过程不仅是繁杂的，甚至是不可能解决的，但最重要的是在这个过程中，微分方程也失去了它的自身最重 要的特性----精确性、连续性。 而对于元胞自动机来讲，脱离计算机环境来进行运算几乎是不可能的，但是借助计算机进行计算，则非常自然而合理，甚至它还是下一代并行计算机的原型。因此，在现代计算机的计算环境下，以元胞自动机为代表的离散计算方式在求解方面，尤其是动态系统模拟方面有着更大的优势。元胞自动机虽然在理论上具备计算的完备性，但满足特定目的构模尚无完备的理论支持，其构造往往是一个直觉过程。用元胞自动机得到一个定量的结果非常困难，即便是可能的话，元胞自动机也将陷入一个尴尬，元胞自动机的状态、规则等 构成必然会复杂化，从而不可避免地失去其简单、生动的特性。 然而，证如物理学家玻尔所说，"相对的并不一定是矛盾的，有可能是相互补充和相互完善的"。二者互有优缺点，相互补充，都有其存在的理由。但在现代计算机环境下，对于元胞自动机这一类相对来讲还处于幼年阶段的离散计算方式，需要予以更多的关注和支持。在地理学中，Lowry、Wilson、张新生(张新生，1997)等人的空间动力学模型都是基于微分方程的模型，由于这些模型大多是复杂的非线性微分方程，无法求得其解析解，需要按Euler方法或Runge-Kutta方法对微分方程进行一步或多步差分，完成相应的计算机模型或在GIS支持下的空间分析模型。对于这些模型，我们都可以构建相应的元胞自动机模型。 4.元胞自动机与分形分维 元胞自动机与分形分维理论有着密切的联系。元胞自动机的自复制、混沌等特征，往往导致元胞自动机模型在空间构形上表现出自相似的分形特征，即元胞自动机的模拟结果通常可以用分形理论来进行定量的描述。同时，在分形分维的经典范例中，有些模型本身就是，或者很接近元胞自动机模型，例如下面我们提到的凝聚扩散模型，因此，某些元胞自动机模型本身就是分形动力学模型。但是，究其本质，元胞自动机与分形理论有着巨大的差别。 元胞自动机重在对想象机理的模拟与分析;分形分维重在对现象的表现形式的表达研究。元胞自动机建模时，从现象的规律入手，构建具有特定涵义的元胞自动机模型;而分形分维多是从物理或数学规律、规则构建模型，而后应用于某种特定复杂现象，其应用方式多为描述现象的自相似性和分形分维特征。然而，这些分数维究竟能够给我们提供多少更有价值的信息?分形理论的进一步应用问题尚末得到解决 (仪垂祥，1995)。 此外，两者都强调一个从局部到整体的过程，但在这个过程的实质上，二者却存在巨大的差异。分形论的精髓是自相似性。这种自相似性不局限于几何形态而具有更广泛更深刻的含义;它是局部 (部分)与整体在形态、功能、信息和结构特性等方面而具有统计意义上的相似性。因此，分形理论提供给我们分析问题的方法论就是从局部结构推断整体特征(陈述彭，1998)。相反，元胞自动机的精华在于局部的简单结构在一定的局部规则作用下，所产生的整体上的"突现"性复杂行为;即系统 (整体)在宏观层次上，其部分或部分的加和所不具有的性质(谭跃进等，1996)。因此，分形理论强调局部与整体的相似性和相关性，但元胞自动机重在表现"突现"特征，即局部行为结构与整体行为的不确定性、非线性关系。 5.元胞自动机与马尔科夫(链)过程 马尔科夫过程(MarKov Process)是一个典型的随机过程。设X(t)是一随机过程，当过程在时刻t0所处的状态为已知时，时刻t(tt0)所处的状态与过程在t0时刻之前的状态无关，这个特性成为无后效性。无后效的随机过程称为马尔科夫过程。马尔科夫过程中的时同和状态既可以是连续的，又可以是离散的。我们称时间离散、状态离散的马尔科夫过程为马尔科夫链。马尔科夫链中，各个时刻的状态的转变由一个状态转移的概率矩阵控制。 马尔科夫链与元胞自动机都是时间离散、状态离散的动力学模型，二者在概念上有一定的相通性。尤其是对于随机型的元胞自动机来讲，每个元胞的行为可以视为一个不仅时间上无后效，而且在空间上无外效的马尔科夫链。 但是，即使是随机型的元胞自动机也与马尔科夫链存在相当大的差别。首先,马尔科夫链没有空间概念，只有一个状态变量;而元胞自动机的状态量则是与空间位置概念紧密相关的;其次，马尔科夫链中的状态转移概率往往是预先设定好的，而随机型元胞自动机中的元胞状态转移概率则是由当前元胞的邻居构型所决定的。 6.元胞自动机、随机行走模型和凝聚扩散模型 随机行走模型(Random Walk Model)模拟的是统计数学中提供"最可能状态"常用的数学模型。它的基本思想为:给定空间中的一个粒子:它在空间中的移动矢量 (包括方向和距离)是由跃迁概率的随机量所控制，由此可以模拟诸如自然界中的分子布朗运动、电子在金属中的随机运动等复杂过程。其理论研究主要集中在对单个粒子的运动规律的研究。但是，随机行走模型中粒子可以是很多个，但是它们遵循的规则都是一个统一的随机规程，而且它们之间的运动是相互独立的，互不影响。如果考虑它们之间的相互作用，就可能构 造出其他基于随机行走的模型，例如凝聚扩散模型。 凝聚扩散(Diffusion-Limited Aggregation)模型，简称DLA，可以看作是一个多粒子的随机行走模型，而且它的计算空间也往往是一个离散的格网。它是由A·Written和Sander于1981年首先提出的。其基本思想如下:给定初始点作为凝聚点，以它作为圆心做一个大圆，在圆周上的一个随机点释放一个粒子，为简单起见，它的运动通常规定为一个随机行走过程，直到它运动至与已有的凝聚点相邻，改变它的状态为凝聚点，不再运动;再随机释放一个粒子;直至凝聚。重复上述过程，就可以得到一个凝聚点的连通集，形似冬日里玻璃上的冰花。凝聚扩散模型还可以有不同的形式，如释放点可以在一个四边形中的顶部，从而在下面省长出形似荆棘的灌丛。而1984年，R·F·Voss提出的多粒子凝聚扩散(Multi-Particle Diffusion Aggregation)模型是对凝聚扩散模型的改进和发展。其基本思想是:在给定的离散空间中，依照一定的密度随机散布自由粒子，在中心设置一个凝聚点作为种子点，也可以随机布设若干个凝聚点作为种子，然后各自由粒子随机行走，一旦与凝聚点相邻，则变为新的凝聚点，直至所有的自由粒子"凝聚"。 元胞自动机、随机行走模型、凝聚扩散模型都是典型的分形图形的生成方法，在很多情况下，它们都可以生成相似的复杂图案。但它们之间仍存在着一定的差别。 随机行走模型与元胞自动自动机的差别在于以下几个方面:第一、随机行走模型通常只是考虑单个粒子的运动，而元胞自动机模型中则通常存在众多的元胞;第二、即使模型中，存在多个粒子，随机行走模型通常并不考虑粒子间的相互作用，粒子的运动是相互独立的;第三、随机行走中的粒子是运动的概念，而元胞自动机的元胞通常是一个状态变化的过程;第四、随机行走中的粒子的运动空间可以是离散的，也可以是连续的，但在元胞自动机中，元胞都分布在离散的空间网格上。 凝聚扩散模型。尤其是多粒子凝聚扩散模型与元胞自动机则非常相似:时间空间离散;模型中存在粒子的相互作用，且这种作用具有局部特征，即自由粒子在有凝聚点为邻居时，状态转变为凝聚点。特殊的是这种转变只是一个单向的转变，凝聚扩散模型在最终达到一种定态吸引子;粒子的运动遵循相通的规律，可以进行同步计算。因此。在广义上，凝聚扩散模型可以归为元胞自动机的一个特例。但是，它们之间仍存在以下几个不同点:一、元胞自动机模型面向的是整个网格空间，而凝聚扩散模型面向的是特定粒子的运动;二、元胞自动机的元胞通常只有状态的改变，其空间位置是固定的，而凝聚扩散模型中的粒子不仅有状态的变化，更是一个运动的粒子。三、凝聚扩散中，多个粒子通常可以同时占据一个格网空间点，而元胞自动机模型中，每个格网点只能有一个元胞。因此，在某种意义上讲，凝聚扩散模型与下面提到的多主体模型更相似，可以看作是粒子间不存在目的性、竞争、协作等智能特征的"无头脑"的主体模型。 7.元胞自动机与多主体系统 多主体系统(Multi-Agent System，简称MAS)是分布式人工智能的热点课题 (史忠植.1998)，主要研究为了共同的、或各自的不同目标，自主的智能主体之间智能行为的协作、竞争等相互作用。基于主体的模型(Agent Based Model，简记为ABM)，简称主体模型，又称基于实体的模型(Entity Based Model，简记为EBM)，或基于个体的模型(lndividual Based Model，简记为IBM)，是多主体系统的一个子集，其主要特征是每个主体代表了现实世界中一个智能性、自治的实体或个体，如人群中的个人，生态系统中的植物个体、动物个体，交通流中的汽车，计算网络中的计算机，经济系统中的经营者等。而在多主体系 统中，组成系统的个体可以是任何系统部件，如组成专家系统的是一条条意见。 一些基于主体的模型中的主体是具有空间概念的，交通流中的汽车，生态系统中的动植物个体等;但有些并不具有空间概念，如计算网络中的计算机。对于那些有空间概念的主体，其空间表示即可以是连续的，如一组实数坐标对;也可以是离散的，即格网空间中的行列值。而元胞自动机与这种具有离散空间概念的主体模型非常相近，二者均研究在离散空间上个体间的相互作用而形成整体上的复杂行为。但仍然存在很大的区别; (l)主体模型中的主体可能是可以移动的，如动物个体;但也有可能是不可以移动的;而元胞自动机模型中的元胞个体通常是不可以移动的，元胞自动机在整体上的运动是通过元胞个体的状态变化来实现的。 (2)在基于格网空间的主体模型中，格网只是作为主体的空间定位，多个主体可以占据一个格网点;而在元胞自动机模型中，每个格网点只能拥有一个特定状态的元胞。 (3)在本质上讲，可以说，主体模型是面向(通常是稀疏，分布在网格空间上的个体的，而元胞自动机则是面向整个网格空间的。在模型运行时，主体模型将只考虑个体的行为，而元胞自动机将考虑整个元胞空间上的每个格网 (元胞)的状态。 8.元胞自动机与系统动态学模型 系统动力学 (SystemDynamics，简称SD)是一间分析研究反馈系统的学科，也是一门认识系统问题和解决系统问题交叉的综合性学科。它最初由美国麻省理工学院的Jay W·Forrestr教授于1956年开发提出，其特点是引入了系统分析的概念，强调信息反馈控制，是系统论、信息论、控制论和决策论的综合产物，非常适于研究复杂系统的结构、功能与动态行为之间的关系。通过分析系统结构，选取适当因素，建立它们之间的反馈关系，并在此基础上建立一系列微分方程，构建系统动态学方程，进一步考察系统在不同参数和不同 策略因素输入时的系统动态变化行为和趋势，为决策者提供决策支持。由于它能够对实际系统进行动态仿真，因而系统动力学模型可作为实际系统，特别是社会、经济、生态复杂大系统的"实验室"(Forrester。J·W·，1969;裴相斌，1999;李一智等，1987)。 系统动态学模型在地球科学研究中具有比较广泛的实用性。因为它着眼于系统的整体最佳目标，不是单纯追求个别子系统的最佳目标，有助于实现人口、资源、环境与社会、经济各子系统之间的协调，采用无量纲的综合研究。同时，该模型仍采用的一阶微分方程组，带有延迟函数和表函数，又能引入投入一产出反馈回路的概念，能比较直观、形象地处理某些比较复杂的非线性问题 (陈述彭，1991)。但是，系统动态学也有"先天不足"，而限制了它在地球科学中的应用。 (1)首先，SD对系统的描述带有主观性。建模者对系统结构的认识，主要包括因素的选取及其相关关系的描述，就直接反映在模型中。而复杂系统的不确定性、非线性等复杂性特征决定了它的系统结构具有混沌性，不同人对它的描述可能有很大的差别，因而，系统动态学在地学建模中，难免会受到个人主观性的干扰，而影响模型的模拟结果。 (2)其次，SD缺乏全面的协调指标体系。复杂系统中有许多因素是定性的，需要一个量化的过程。那么，多个相关因子的分类、分级定量标准就需要从系统的高度进行协调，这往往是系统动态学模型的一个难题。 (3)最后，缺乏空间因素的处理功能，难以刻画空间系统中各要素在空间上的相互作用和相互反馈关系(张新生，1997;裴相斌，1999)。这对其应用于空间复杂系统研究是个致命的限制。 系统动态学模型与元胞自动机都是采用 "自下而上"的研究思路，利用系统要素间的反馈等相互作用，来模拟和预测系统的整体的动态行为，它们都是研究复杂系统动态变化约有力工具。但是，二者又有所不同:首先，在模型机制上，CA模型基于系统要素间的空间相互作用，而SD则更多的考虑要素间指标属性的关联关系;其次，在模型表现形式上，CA是时间、空间、状态全离散的，转换规则也往往表现为参照表形式，而SD则表现为系列的微分方程组，时间、属性及要素间反馈关系的表达都是连续性质的i第三，在结果表 现上，CA模型表现为系统空间结构的时空动态演化，而SD模型的结果是系统某个社会经济指标的动态变化;最后，在应用上，CA模型多用于复杂系统的时空演化模拟，而SD模型缺乏空间概念，更适于社会经济系统的模拟预测。 元胞自动机的应用 元胞自动机可用来研究很多一般现象。其中包括通信、信息传递(Communicahon)、计算(Compulation)、构造 (ConsTruction)、生长 (Growth)、复制 (Reproductionj、竞争(Competition)与进化(Evolutio，])等(Smith A.,1969;Perrier，J.Y.,1996)。同时。它为动力学系统理论中有关秩序 (Ordering)、紊动 (Turbulence)、混沌 (Chaos)、非对称(Symmetry-Breaking)、分形(Fractality)等系统整体行为与复杂现象的研究提供了一个有效的模型工具 (Vichhac。G，1984; Bennett，C,1985)。 元胞自动机自产生以来，被广泛地应用到社会、经济、军事和科学研究的各个领域。应用领域涉及社会学、生物学、生态学、信息科学、计算机科学、数学、物理学、化学、地理、歹境、军事学等。 在社会学中，元胞自动机用于研究经济危机的形成与爆发过程、个人行为的社会性，流行现象，如服装流行色的形成等。在生物学中，元胞自动机的设计思想本身就来源于生物学自繁殖的思想，因而它在生物学上的应用更为自然而广泛。例如元胞自动机朋于肿瘤细胞的增长机理和过程模拟、人类大脑的机理探索(Victor.Jonathan.D.，1990)、爱滋病病毒HIV的感染过程(Sieburg，H.B.. 1990)、自组织、自繁殖等生命现象的研究以及最新流行的克隆 (Clone)技术的研究等 (ErmentroutG。B。，1993)。 在生态学中。元胞自动机用于兔子-草，鲨鱼-小鱼等生态动态变化过程的模拟，展示出令人满意的动态效果;元胞自动机还成功地应用于蚂蚁、大雁、鱼类洄游等动物的群体行为的模拟;另外，基于元胞自动机模型的生物群落的扩散模拟也是当前的一个应用热点。在信息学中。元胞自动机冉于研究信息的保存、传递、扩散的过程。另外。Deutsch(1972)、Sternberg(1980)和Rosenfeld(1979)等人还将二维元胞自动机应用到图像处理和模式识别中 (WoIfram.S.，1983)。 在计算机科学中。元胞自动机可以被看作是并行计算机而用于并行计算的研究(Wolfram.S.1983)。另外。元胞自动机还应用于计算机图形学的研究中。 在数学中，元胞自动机可用来研究数论和并行计算。例如Fischer(1965)设计的素数过滤器(Prime Number Sieves)(Wolfram,S.1983)。 在物理学中。除了格子气元胞自动机在流体力学上的成功应用。元胞自动机还应用于磁场、电场等场的模拟，以及热扩散、热传导和机械波的模拟。另外。元胞自动机还用来模拟雪花等枝晶的形成。 在化学中，元胞自动机可用来通过模拟原子、分子等各种微观粒子在化学反应中的相互作用，而研究化学反应的过程。例如李才伟 (1997)应用元胞自动机模型成功模拟了由耗散结构创始人I·Prgogine所领导的Brussel学派提出的自催化模型---Brusselator模型，又称为三分子模型。Y·BarYam等人利用元胞自动机模型构造了高分子的聚合过程模拟模型，在环境科学上，有人应用元胞自动机来模拟海上石油泄露后的油污扩散、工厂周围废水、废气的扩散等过程的模拟。 在军事科学中，元胞自动机模型可用来进行战场的军事作战模拟"提供对战争过程的aq理解（谭跃进等，1996)。 元胞自动机作为一种动态模型，更多的是作为一种通用性建模的方法，其应用几乎涉 及社会和自然科学的各个领域，在此我们不在一一介绍。 参考文献 陈述彭，地球科学的复杂性与系统性，地理科学，10(4)。1991。 陈述彭主编，地球系统科学，北京:中国科学技术出版社，1998。 李才伟，元胞自动机及复杂系统的时空演化模拟，武汉: 华中理工大学博士学位论文，1997。 李元香，格子气流体力学的九点矩形模型，武汉大学学报。并行计算专刊:22-32，1991。 李元香，康立山、陈硫屏，格子气自动机，清华大学出版社与广西技术出版社，1994。 李一智、林巍和，系统动态学，长沙:中南工业大学出版社，1987。 史忠植，高级人工智能，北京:科学出版社，1998。 裴相斌，中国科学院地理所博士论文:辽宁诲岸带城市化和环境污染的调控研究，1999。 谭跃进、高世揖、周曼殊，系统学原理， 长沙:国防科技大学出版社，1996。 吴建兵、杨杰、吴月华、刘际明、何多慧，人工生命与人工智能，模式识别与人工智能 PRLAl.11 (3) : 274~279, 1998. 夏培肃，英汉计算机辞典,北京:人民邮电出版牡,1984。 谢惠民，非线性科学丛书: 复杂性与动力系统，上海科技教育出版社, 1994。 仪垂祥，非线性科学及其在地学中的应用，北京:气象出版社，1995。 张新生，中国科学院地理所博士论文:城市空间动力学模型研究及应用，1997。 Amoroso, S. and Patt, Y., Decision Procedures for Surjectivity and Injectivity of Parallel Maps for Tes sellation Structures, J. Computer System Sci.. 6, 448-464, 1972. Bays, C., A New Candidate Rule for the Game of Three-Dimensional Life ? Complex Systems 6 (5) ,1988. Bays, C., Candidates for the game of life in three dimensions, Complex Systems, 5 (1), 1987. Bays, C., Classification of Semitotalistic Cellular Automata in Three Dimensions, Complex Systems,(2), 1988 Bennett , C and Grinstein G., Role of Irreversibility in Stabilizing Complex and Nonenergodic Behavior in Locally Interacting Discrete Systems, Physical Review Letters, 55: 657 ?660 ? 1985,Culik, II K., Hurd, L P. and Yu, S., Computation Theoretic Aspects of Cellular Automata, Physic D. 45: 357-378, 1990. Deutsch, E. S., Thinning Algorithms on Rectangular ? Hexagonal and Triangular Arrays, Communication ACME 15, 8Z7, 1972- Dewdney, A. K., The Cellular Automata Programs That Create Wireworld , Rugworld and Other Diver sions, Scientific American, 262: 1, 146 149, 1990. Dewdney,A. K., The Game of Life Aaquires Some Successors in Three Dimensions, Computer Recre ations, Scientific American, pages: 8~13, Feb. 1987. Ermentrout G. B. and Edelstein-Keshet L. Cellular Automata Approaches to Biological Modeling, Jour nal of Theoretical Biology 160: 97~133, 1993. Forrester, J. W., Urban Dynamics, The MIT Press, 1969 Gardner, M., On Cellular Automata, Self-reproduction, the Garden of Eden and the Game "Life", Scientific American, 224 (2): 112 117, February 1971. Gardner, M., The Fantastic Combinations of John Conway's New Solitaire Game "Life",Scientific American, pages 120 123, October 1970. Gardner, M., Wheels, Life and Other Mathematical Amusements, W, H. Freeman, New York, 1983. Gutowitz,H. A.,A Hierarchical Classification of Cellular Automata, Phydica D 45, 136~156, 1990. http://gold.cchem.berkeley.edu/gavinc/Java/CA/Polymer.html . Longton C. G., Life at the Edge of Chaos, in C. G. Langton, etc. (ed), Artificial Life II, pp41-91. New York: Addison - Wesley, 1992, Longton, C G..,1987,1990, 1992,Artificial Life, I, II, III, Addison Wesley Pub. M. Waldrop 著，陈玲译, 复杂：诞生于秩序与混沌边缘的科学，生活.读书.新知三联书店，1997 Perrier, J. Y., Sipper, A. G. and Zahnd, J., Toward a Viable, Self-reproducing Universal Computer.Physica D, 97: 335 352, 1996. Rosenfeld, A., Picture Languages , Academic, New York' 1979 Sieburg, H. B., McCutchan, J. A. , Clay, 0 K., Cabalerro, L. and Osrlund, J J, Simulation of HIV Infection in Artificial Immune System, Physica D 45, 208 ?227 ' 1990. Smith A, Cellular Automata Theory. Technical Report 2, Stanford Electronic Lab. , Stanford University, 1969. Sternberg, S. R., Language and Architecture for Parallel Image Processing, in Pattern Recognition in Practice, edited by E. S. Gelesma and L. N. Kanal , 35 , 1980 Toffoli, T., Margolus N,, Cellular Automata Machines: A New Environment for Modeling. The MIT Press ?Cambridge ?Massachusetts, 1987. Turing A M., On computable numbers with an application to the entscheidungs problems, Proc. London Math. Soc., 2: 544 ?548, 1936 Vichniac, G, Simulating Physics With Cellular Automata, Physica D, 10: 96 ?115 ? 1984. Victor, Jonathan ? D., What Can Automaton Theory Tell Us About The Brain? Physica D 45 ?205~ 207,1990. Wolfram, S., Statistical Mechanics of Cellular Automata. Reviews of Modern Physics, 55 (3): 601~ 644 July 1983. Wolfram, S., Theory and Applications of Cellular Automata, World Scientific, Singapore, 1986
上回我们看到，停机问题这个良定义的问题，不能由图灵机来解决。那么像停机问题这样的图灵机不可解或者说不可计算的问题，究竟是有很多呢，还是只是个别呢？ 其实，有另外一种论证，可以说明绝大多数将自然数映射到自然数的函数是图灵机不可计算的。这个论证的思路是把一切可能的图灵机进行点数，把它们排个队。 首先，请注意图灵机的有限性。这个 我们在讨论通用性的时候 说过。除了带子之外，图灵机所有其他方面都是有限的。记号的种类是有限的，控制器的可能状态数是有限的，读写头的可能移动是有限的。这样一来，任何特定的图灵机，其指令表中包含的五元组的数目也就自然是有限的。这就意味着，我们可以把图灵机们按照它们各自的指令表来排队。比如，把指令表视为一个句子，每个五元组视为一个单词，同时将组成五元组的记号种类、控制器状态和读写头移动方向视为字母并规定其字母表顺序。这样，我们就可以像把英语句子按字母顺序排序那样来给图灵机排序了。由此我们可以说明所有可能图灵机的集合是可数（无穷）的。因此，可能图灵机的数目和自然数一样多。（更准确地说，图灵机集合的基数和自然数集合的基数相同。） 另一方面，将自然数映射自然数的函数个数是不可数（无穷）的，远远超过我们用来给图灵机点数的自然数集合的大小，而至少有［0 1］区间里的实数那么多个。（因为这种自然数到自然数映射的集合至少有自然数的幂集那么大。） 由此可见，从自然数到自然数的函数个数比可能的图灵机的个数要多很多。（在集合的基数序列里要整整高出一阶。）这就意味着必然存在着图灵机不可计算的函数；而且，事实上有无穷不可数那么多的函数是图灵机所不可计算的。跟不可计算函数的数目比起来，可能图灵机的数目相对而言小到可以忽略不计。所谓停机问题只是这些不可计算函数中的一个有趣的例子罢了。 需要注意的是这里所谓不可解，是相对于图灵机而言的，所以也叫图灵机不可计算或者图灵不可计算。这里的论证并没有说明其他的跟图灵机不同的机制也不能解决图灵机的停机问题，虽然这些别的机制也可能有自己的停机问题。 这里的讨论表明，存在这数学上良定义的函数，其映射是图灵机这种机制所不能实现的。正如哥德尔曾经指出的，如停机问题这样的不可计算函数的存在，表明了语义是超越纯粹的机制的，就是说哪怕在自然数算术这样一个很简单的领域里，数学语义上可以严格一贯地定义的映射也不能为纯粹机制加以有效执行。 在过去六七十年乃至今天，有不少人由此得出结论说，既然我们一方面能够理解和把握停机问题这类情况，尤其是哥德尔句子为真这样的事实，而机器却不能机械地解决停机问题或者推导出哥德尔句子，因此人的理解或者直觉能力不是机器能够实现的，完全的人工智能也就是不可能的。这个推断成不成立，咱们以后会专门详细讨论。 不过，图灵机并非唯一的计算模型。前面提到过丘奇对不可判定性的工作，他用的模型叫做演算，这个是后来Lisp程序设计语言的基础。此外，还有由克林尼（Stephen Kleene）在哥德尔工作基础上加以整理推广的递归函数（recursive functions）、波斯特（Emil Post）的波斯特产生式系统（Post production systems）等等。再后来，有戴维斯（Martin Davis）提出的S编程语言。这一模型对于程序员来讲会比较直观。它非常简单，只有三种指令，分别是加1、减1和条件转移： （1）x i = x i + 1 （2）x i = x i 1 （3）if x i = 0 goto LABEL 这个模型下的程序由上述三种类型的指令行构成。每行有仅属于自己的唯一标记（LABEL），可以用在转移（goto）语句里面来指明转移的目标。这个模型假定了存在很多下标变量x i 可用，它们起的作用是存储器，跟图灵机的带子相当。不过，这个可是随机存储器（RAM）！您要有兴趣的话，可以试着用S编程语言来写点小程序。（提示：您可以先考虑如何把一个下标变量拷贝到另一个下标变量，由此构造出赋值语句来。） 在1930年代的短短几年里面递归函数、演算、图灵机等等先后被提出，人们很快证明了他们之间的任何一对都是等价的。所谓等价，在这里的意思就是说一个模型能做的，另一个模型也都能做；反之亦然。 当然，要谈两个模型之间的等价性，就必须有一定的准则来界定各个模型要做的事情。比如说，你不能要求演算去做图灵机能做的移动读写头，因为演算里根本就没有读写头；此外，你也不能要求任何这些模型给你炒个小菜或者打个华尔兹的拍子啥的。在这里，等价性证明采用的准则很简单，就是看这些模型如何实现自然数到自然数的函数映射。所谓等价的意思就是说，对于任何一个自然数到自然数的函数映射，如果一个模型能够实现此映射，那么另一个模型也能实现该映射；反之亦然。因为我们前面看到，图灵机并不能实现全部这些映射，所以这个准则并不是空洞的，因为有可能存在某个映射是图灵机不能做的，演算可以做；或者说反过来。 值得注意的是，这里的等价关系是相当的行为主义的，它只关心输入和输出──如果有输出的话──两端的符合，其他任何方面都不管。模型里面具体如何运作，算法是什么，运作有多快，需要多少存储等等全都无所谓，经典计算和量子计算之间的区别也无所谓。 不管怎么样，既然这些特定的模型一个个地被证明为相互等价，人们就在想：嘿，咱们是不是抓住了一点什么具有一般性的东东呢？是不是说所有这些模型共同指向了直观上的计算或者可计算概念的本质呢？由此就有了著名的丘奇-图灵论题（Church-Turing thesis）： 任何直观上可计算的函数都可以由某个图灵机来计算。 这个说法之所以叫做论题（thesis）而不是定理（theorem），是因为直观上可计算这个概念是没法形式化，所以也就不可能有形式化的证明。直观上可计算，其大体意思恐怕是说按照某种确定的过程来一步一步地、机械而有效地把输入变形到输出。与其他等价的模型相比，图灵机有个特点，就是它一方面把这个思想给形式化了，另一方面又保留了机器之为机器的直观性。由此，我们可以理解为什么哥德尔会认为，是图灵机这个模型的提出，真正把有效可计算性这个概念给抓住了。 丘奇-图灵论题提出至今有70多年的了。它也不是没有人反对，今天也还有人在尝试提出与图灵机不等价的，计算能力超越图灵机的模型。不过，迄今为止还没有任何被断言为超越图灵机的计算模型被普遍接受为合理的、符合直观可计算观念的模型。所以，今天的主流观点依然认为这一论题是对的，以图灵机为代表的这批计算模型确实抓住了直观上的可计算性。
标签: 图灵机
