6.2 图灵机

人物略传：阿兰·图灵（Alan Turing），1912年6月23日生于伦敦，曾就学于谢波恩中学和剑桥大学国王学院（学习数学）。1935年4月，冯·诺依曼从普林斯顿到剑桥访问，并在那里有一个月的授课活动，“在那个学期里，图灵当然认识了他，并且几乎从始至终参加了这门课程的学习……图灵可能就是这时听了冯·诺依曼课的原因，他在3月24日写往家里的信中说‘我已经申请了明年去普林斯顿访问的基金’”（hodges，1983：95）。图灵的确去了普林斯顿（于1938年获得数学博士学位），期间同阿朗索·丘奇（Alonzo Church）一起学习。到达一周后，他在写给母亲的信中说：“这里的数学系让我感到满意，这里有一大批杰出的数学家：冯·诺依曼、哈代（hardy）、外尔（Weyl）、柯蓝特（Courant）、爱因斯坦。”1936年7月，他在普林斯顿发表了他最著名的学术论文《论可计算数及其在判定难题（Entscheidungsproblem）中的应用》［1］。在这篇论文里，图灵首次精确定义了“（自动）计算机器”，即后来我们为了纪念他而命名的图灵机。图灵回到英国及随后的6年里，在外事局工作——实际上就是英国代码及加密学校，离伦敦50里远的高度机密机构。在这里，他的“Colossus”计算机帮助破解了德国“Enigma”密码，这项工作被认为缩短了欧洲战场两年时间。1945年，他辞去外事局的工作后，加入伦敦国际物理实验室，并领导设计自动计算引擎ACE（Automatic Computing Engine）项目。1949年，他接受了曼彻斯特大学的曼彻斯特自动数字机器“Madam”副主任职务。1950年，他发表了一生中最著名的非技术性论文《计算机器和智能》。在这篇文章里，他提出了“模仿游戏”的概念——即现在著名的用来测试智能的“图灵测试”。1952年，他因同性恋被判有罪。1954年6月7日，自杀身亡（他吃下了一个钾氰化物浸泡的苹果而死，也可能是意外死亡）。

图灵机（Turing Machine，TM）有相对简单的构造和操作模式，所以很容易用之证明，但却不可能用来实际计算，这就是为什么现实中无人制造它的原因。这里，我们首先了解图灵机的结构和运作方式，然后再介绍图灵机的一些基本特征。

结构和操作

直观上看，图灵机是由磁带和读写磁头（带有一个程序表和一个扫描器）两个主要部分构成的抽象计算设备。

结构

磁带：可双向无限补充，被分成一个个小格子，每个格子上要么是一个预先确定的字母符号，要么是空白。

读写磁头：读写磁头可以相对磁带前后运动，在磁带上读或写符号。

程序表（程序）：是一张有限指令列表，每个指令都包含具体的五种信息：（1）当前状态；（2）输入（读）字符；（3）输出（写）字符；（4）读写头向左或向右运动的命令；（5）下一种状态。

这些组成部分在计算过程中进行如下操作：

操作

控制：读写磁头的运动由程序表控制，而程序表主要关注两件事情：当前机器状态及其正在扫描的符号。得到程序表的指令后，读写头（1）在当前的小格子上写入特定符号，然后（2）向右或向左移动一个格子，或者保持在当前位置不变。然后，机器根据程序表的指令进入下一状态。

图灵机中运行的程序：包括具体的程序表和初始的磁带结构，当机器接收开始符号时便开始运行，遇到停止符时停止，磁带最后的结构状态包含着想要的输出结果。

计算过程：计算过程包括执行指令，由初始化的磁带结构和内部状态开始，再到遇到一个停止符结束。磁带最后的结构就是计算的输出结果。

输入：即初始的磁带结构形式。

输出：磁带最后的结构形式。

这台机器能够交替打印0与1，中间用空格间隔。磁带开始时（在竖栏2为“无”）为空白，机器要么打印“0”，要么打印“1”。“R（Right）”意味着机器将移到当下方格的右边方格，“p（print）”意味着开始打印。例如，一个空白方格以状态1开始，然后：

状态操作

1.打印一个“0”，然后向右移动一个方格，进入状态2。

2.向右移动一个方格，进入状态3。

3.打印一个“1”，然后向右移动一个方格，进入状态4。

4.向右移动一个方格（等等）。

图灵机循环：总结图灵机操作步骤，可以发现机器有一个循环：读、写、移动和进入下一状态。

已经证明了一些有关TMs的定理，但值得关注的是图灵最初提出的图灵定理（1936）：

图灵定理：存在一台“通用TMs（UTMs）”，可以模仿任何其他TM的动作。

根据资料，已知的最小通用图灵机由明斯基设计。如果我们认为一个具体的TM，能够通过编制或者形式化程序完成磁带上表征的事件，那么说通用TM能模仿任何具体TM的行为，就意味着通用TM能编码任何TM磁带上的描述。因为TMs是自动按步执行程序的，而UTM则能够清晰地编码有效步骤和算法的指令。这就引入了所谓的“丘奇-图灵论题”：

丘奇-图灵论题：对于任何可计算某一函数的有效步骤，都存在一个能够运行计算这个函数步骤的TM（也就是说，做每一步骤所做）。

“有效步骤”是直觉概念，而不是一个形式概念，所以没有定理能够给予证明。然而，尽管每一次人们认为这个概念已经变得更精确了，新的概念还是被证明与图灵机等价。

术语小议：1931年，科特·哥德尔（Kurt Gdel）提出了一组重要的递归函数，该函数可具体化为若干非常基础的数字操作步骤。1936年，丘奇写道：“这篇论文的目的是提出一种有关有效计算的定义。”（参见Davis，1965：90）丘奇运用的是“Lambda定义”，并提出这种定义在他的“Lambda-演算”中与递归函数等价。131他总结道：“两者相异且（在作者看来）具有相同有效计算的自然定义的事实，证明它们是等价的。这就增加了如下推论的强度，即它们构成了一种普遍的概念特征，正如概念通常由对概念的直觉理解构成一样”。此后不久，图灵在他的另一篇论文（1936/7）中认为，所有图灵机计算函数都是递归的，且所有递归函数都是图灵机可计算的。因此，有效计算可定义为Lambda-定义，Lambda-定义与递归函数等价（丘奇），递归函数又与TM计算等价（图灵），因而有效性就是TM计算（丘奇-图灵论题）：

丘奇（1936）

论题：有效步骤（直觉）=Lambda定义

定理：Lambda定义=递归函数

图灵（1936/7）

定理：TM计算=递归函数

丘奇-图灵

定理：Lambda定义=递归函数=TM计算

论题：有效步骤=TM计算

随后的研究发现，所有的各种形式化后能有效计算的系统（Normal系统、post系统、Thue系统、Semi-Thue系统、Markoff算法）都与图灵机等价。1957年，王浩证明所有递归函数在操作程序图上都是可计算的（机器通过标准操作程序图说明计算）。最近，Fortran、pascal和Lisp程序语言证明也等价于图灵机。

由此可见，图灵机的计算与有效步骤弱等价。此论题的推论是，通用TM能计算任何有效步骤能实现的计算。因为我们的认知功能可视为有效步骤，UTM能模拟这种功能的输入-输出对，所以它们弱等价。因此，在那段时期，有些人认为，这正为可通过恰当编程建造一台能够思维的机器找到了合理依据，并且认为可用脑内具有的有效步骤理解人类的认知功能。

6.3 冯·诺依曼机

132人物略传 约翰·冯·诺依曼（John von Neumann），1903年12月28日生于布达佩斯，出生时起名为Neumann Janos （John） Lajos（按照匈牙利传统，姓放在前面）。因为他的父亲被授予了光荣的“Margittai（源自Margitta）”头衔，所以诺依曼的全名实际上为“Margittai Neumann Janos Lajos”。一家德国出版社将“Margittai”转译为德语“von”，因此就变成了“John von Neumann”。1913年，小诺依曼被政府挑选接受国家教育，部分是因为他的语言天赋。10岁时，他就学会了法语、德语、拉丁语和古希腊语。童年时，他最喜欢学历史，通读了父亲总共44册的通史著作。1913年，10岁的他注册入读布达佩斯的一所著名高中，在那里接受了8年教育。1921年，进入布达佩斯大学学习数学。他习惯花大量的时间到柏林听哈伯（haber，化学）和爱因斯坦（统计学原理）的讲课，只在考试时才会中断。1923年，迫于父亲的压力，接受“实能教育”，进入了苏黎世ETh（Eidgenossische Technische hochschule）学习化学工程。但他对数学的兴趣因经常与那时留居苏黎世的数学家外尔（外尔不在时，曾让诺依曼代课一个学期）和波利亚（polya）的密切联系而保留。1926年，取得布达佩斯大学数学博士学位（他的学位论文后于1928年出版）。1927年，成为柏林大学无俸讲师，时年24岁——是这所大学历史上最年轻的教师。1930年，进入普林斯顿IAS（Institute for Advanced Studies）数学部。1943年访问英国时说道：“我开始对计算技术有了强烈兴趣。”由于他出色的流体动力学知识背景，应罗伯特·奥本海默（Robert Oppenheimer）的邀请，来到洛斯阿拉莫斯，作为一名爆聚（implosion）特性数学专家参加曼哈顿工程。他发现，模拟爆聚的计算问题，需要消耗大量的时间。所以在1944年，他用两周时间致力于改造机械操作穿孔卡和制表机连接板线路，“当他看到制表机连接板线路时特别沮丧，制表机在不同的计数器上平行操作，制表机连接板线路执行平行计算，需要考虑平行操作的相对时间。后来，他的这段经历使他否定了电子计算机并行计算的可能，也否定了他的关于单个地址指令编码的设计，133认为这种编码必然不能采用并行处理运算”。1944年9月7日，诺依曼访问莫尔电子工程学院（宾夕法尼亚大学），讨论了EDVAC（electronic discrete variable arithmetic computer）的设计构想，作为ENIAC的后继发展。1945年春天，在洛斯阿拉莫斯写就

了《EDVA报告草案》，6月份时他把这个初步草案邮寄到摩尔学院，此时《报告草案》还有一些引文仍留有空白，没有标题。摩尔学院为之添加了一张封面就此出版，诺依曼的这篇尚未完整的报告草案就这样流传开来。“文献非常有力地，仅用100页的油印文本就给定了程序存储计算机的基础……没过多久，美国及英国出现了很多对建造这种高速计算装置感兴趣的不同组织团体。事实上，他的工作，为很多早期程序储存计算机提供了一种逻辑程式”。1955年，诺依曼被诊断患有骨癌。1956年，他为斯蒂尔曼讲座（耶鲁大学）写作了《计算机和脑》。1957年2月8日离世。

“冯·诺依曼机（vNMs）”或者称之为“寄存器结构”机的设计，部分地克服了图灵机的不足［2］。冯·诺依曼机的原型是依据冯·诺依曼最初关于EDVAC的研究（1945）建造的，成为勃克斯、哥德斯坦和诺依曼在普林斯顿高等研究院（IAS）关于计算机储存器研究的基础（Burks，Goldstine，Neumann，1946：98-9）：

1.1 ［完全自动］ 这个设备完全是通用目的的计算机器。包含一些元件，涉及算法、存储器、控制器及与人类操作的连接。这表明，计算机具有完全自动的特征，如当计算开启后可不依靠人类操作而独立完成……

1.2 ［储存器］ 显然，机器不仅需要对特定计算需要的数字信息以某种方式储存……而且对控制实际执行数字数据路径的指令也能够存储…因此必须有某种元件，能够存储这些程序命令。而且，还需要有一个单元能够理解并执行这些指令。

1.3 ［程序存储］ 上面我们已经概括地讨论了两种不同形式的存储：数字存储和指令存储。如果把对机器的指令化简为数字编码，并且如果计算机能以某种方式区分数字和指令，那么储存元件就能同时储存数字和指令……

1.4 ［控制器］ 如果存储元件仅仅是对指令的存储，那么还需要存在一个能够自动执行存储于储存器内指令的元件，称之为“控制器”。

1.5 ［运算器］ 因为装置是计算机器，所以必须存在运算元件，它能够进行一些基本运算操作……

被看作是机器基础的这些操作，通过机器线路实现……

1.6 ［输入-输出］ 最后，必须存在的设置是输入和输出元件，这样操作者才能与机器互相交流……

这些部分的构成关系，派利夏恩（pylyshyn，1984）对冯·诺依曼的最初设计说明作过一个合理的评论：“事实上，人们对每一个广泛有效的结构都会认为是冯·诺依曼提出的某一种类型（虽然使用这个名字常常意味着是指‘传统计算机’）。这种结构——从普林斯顿IAS计算机设计开始得到了广泛应用——是一种寄存机器，通过数字‘地址’储存及检索符号，通过程序的序列转换（除分支指令）实现控制，符号操作则由如下步骤完成：先从存储器中检索符号，把它们储存在指定的寄存器里，再提供一个原初命令，然后再将结果符号重新储存在存储器内。虽然存在各种变式，但自从数字计算机开始，通过一系列‘提取’、‘操作’和‘存储’控制而实现序列加工的主要思想，一直占据支配地位”（pylyshyn，1984：96-7）。

冯·诺依曼机循环：总结冯·诺依曼机操作循环如下：提取、操作、存储。然而，每次循环只可执行一个指令，这就对计算机信息流量产生了约束。这种约束有时称为“冯·诺依曼瓶颈”。

冯·诺依曼机的程序运作：物理句法

我们已经知道，冯·诺依曼机的基本操作循环是提取指令、操作（执行）指令和存储结果。程序是使用某种编程语言执行某种算法的一组指令。我们现在要介绍的是，至少是简述，程序怎样在冯·诺依曼机上运作——我们怎样使一台物理机器能够做我们告诉它做的事情？或者更夸张地说，如果程序是计算机的“心灵”，触发器、寄存器以及电路闸是它的“身体”，那么我们如何解释计算机的心-身问题呢？［3］

我们现在以简单的汇编语言程序比较两个内存地址的内容是否相同（寄存器1和寄存器2），来说明这个问题。如果它们相同，计算机显示“OK”，如果不相同则显示“NO”。下面就是这个程序（选自Copeland 1993b，chapter 4）。大括号里的内容是对每个指令的说明。

“比较和输出”程序：

1.比较：寄存器1和寄存器2

{比较寄存器1和寄存器2的内容，如果它们不同，将0放入匹配寄存器内，如果相同则放置1}

2.分支——0 6

{检查匹配寄存器，如果是0，则跳至第6行}

3.输出——字符1001111

{这是字母O的ASCII码}

4.输出——字符1001011

{这是字母K的ASCII码}