不管你对图灵的概念或原理有多深的了解，都不会对你构建一台真正的计算机有所帮助。数字计算机是由半导体管和其他一些如继电器和真空电子管等开关机制部件构建的。这些半导体管组装成逻辑门，从而实现简单的逻辑功能。寄存器和累加器等高层次的组件都是由这些逻辑门构成的。［1］

图灵机是由什么构成的呢？图灵从来没有告诉过我们。图灵并没打算让他的机器成为实际计算机的蓝图。图灵机是对计算的一种简单抽象的模型，这种计算既可以由人完成，也可以由机器完成。图灵创造图灵机的初衷是为了一个特定的目的：证明对于一阶逻辑并不存在通用判定过程。只是后来，我们发现这种想象中的机器对理解计算理论也有重大的辅助作用。这个转变花了20年的时间，也就是在图灵机成为了我们目前称之为“计算机科学”这一学科的研究对象之后。

将图灵机应用于其他目的（而不是单纯为了证明判定性问题），需要在某种程度上重新改造图灵机。大多数图灵机会永不停息地计算0到1之间某个实数的数位。数学里的常见任务，也是计算机编程里的常见任务，就是函数的计算。一个函数需要一个或者几个数作为输入——称作函数的参数。基于输入，函数会输出计算的结果——称作函数的值。

一类重要的函数就是数论函数，之所以这么称呼是因为它的输入和输出仅限于自然数。图灵在其论文的第10节（本书第页）中发明了一种技巧来计算数论函数，即打印由单个0间隔的连续1的串。第一个0前的连续1的个数表示参数为0的函数值，第二个0前（第一个0后）的连续1的个数表示参数为1的函数值，等等。

对图灵的数论函数持怀疑态度的一位数学家是斯蒂芬·科尔·克莱尼。克莱尼是邱奇在普林斯顿的学生，他在年取得博士学位，之后开始在威斯康辛麦迪逊大学教书。

克莱尼后来写道：“虽然我很向往图灵所构想的机器的非凡能力，但我依然对他用如此简单的方法将此应用到数论函数的计算中表示怀疑。在任何情况下，只有完全函数?(x)才能用这种方法计算。”［2］图灵的方法对部分函数不适用，这些函数只对自然数的部分子集成立。

年开春，克莱尼在威斯康辛麦迪逊大学教授的一个数学基础研讨班上开始寻求一种不同的解决方法。克莱尼重新改进的图灵机在他年出版的经典图书《元数学引论》的第8节中占据了重要的位置。

克莱尼版本的图灵机仍然是读符号，写符号，沿纸带左右移动。不过，它只限于一种符号，即一个简单的竖线，称为tick或tally符号。机器只有这种符号和空格。自然数以由空格分割的一系列连续格上的tick符号表示。克莱尼的自然数以0开始，一个tick符号表示0，2个tick符号表示1，以此类推。克莱尼好像是第一个在文章中将图灵机纸带的例子作为插图的人。［3］

图灵机通常以一个空白纸带开始。而克莱尼改进后的机器则从一个已经编码了一个或几个隔着空格的连续tick串符号（作为函数输入）的纸带开始。克莱尼的机器稍后计算函数的值，并将数字编码到纸带上。克莱尼给出的第一个例子是计算后继函数（即计算被编码的数的下一个数）的值。它只是简单地将另外的tick符号打印在现有tick符号串的后面，因此很方便。

克莱尼的函数计算机器只需要在一段有限的时间内进行计算，当机器完成计算的时候就停止了。这种机器并没有特殊的“停止”或“停机”格局，但是有克莱尼所谓的“被动状态”，即已经不存在机器可以到达的位置。当机器被指令转移到不存在的格局时，“这个机器被称为停止了，我们称它停止时候的状态为终止状态或者输出”。［4］

在图灵的概念里，一台好的机器——图灵称之为非循环机，即符合要求的机器，是永不停止的。经过克莱尼改造后，一台好的机器将在计算完函数后停止运行。一台陷入了无限循环而无法停止的克莱尼机是“不好”的机器。显然，克莱尼的机器更接近传统的数学观念，即函数接受输入并经过有限步骤输出结果。

就如第15章讨论的，到了年，已经存在3种形式的计算有效性直观表示，它们是：

〉图灵机；

〉年，哥德尔基于雅克·赫尔布兰德的建议而定义的递归函数，克莱尼做了进一步的发展；

〉邱奇及其学生（主要是克莱尼）发展的λ可定义函数。

这三种不同形式表示方法的等价性，一部分是由图灵在年关于可计算数的论文的附录中建立起来的，更严格的说明是在其年的论文“可计算性和λ可定义性”中。另外，斯蒂芬·克莱尼在年的论文“λ可定义性与递归性”中也有所说明。现在“递归函数“与”可计算函数”几乎表达同一意思。

斯蒂芬·克莱尼是第一个提出这些形式化表示方法如何直观表达可计算性的人。他在《元数学导论》一书中，第一次明确提出邱奇论题：“每一个有效可计算函数（或者有效可判定谓词）都是一般递归的。”克莱尼又在其后的两章中说：“图灵论题，即每一个被自然认为可计算的函数在他的定义下（即通过一台图灵机）也是可计算的，它实际上与邱奇论题等价……”［5］

在其年出版的书中，克莱尼将两个论题结合在了一起：

图灵论题和邱奇论题是等价的。我们应该将它们统一称为“邱奇论题”，或者“邱奇邱图灵论题”，以表明它和三种形式化表示方法之一的“图灵机”有关。［6］

自那以后，”邱奇邱图灵论题”成为了最适当的术语。

《元数学导论》显然是一本面向数学家们的书。6年以后，另一本经典著作帮助我们跳出纯数学的视野，从计算机科学的角度阐述问题。

马丁·戴维斯于年生于纽约市。他在年获得了普林斯顿大学的博士，其博士论文是《递归的不可解性理论》。戴维斯的论文导师是邱奇，也是克莱尼（年）和图灵（年）的导师。

在伊利诺伊大学教书时，戴维斯开始称判定图灵机能否完成计算的问题为“停机问题”，也许最早是在年。［7］这个术语在年戴维斯出版了《可计算性和不可解性》一书后而广为人知。在这本书的前言里，戴维斯诡秘地写道：“虽然这一卷里真正新的东西很少，但是我对相应主题的安排和论述可能会让专家感到新颖，”随后他做了说明，“特别是，图灵机的概念是这本书行文论述的关键。”［8］

在克莱尼的《元数学导论》中，图灵机直到第页才出现，在第13章之前也没有更深的提及；而在戴维斯的《可计算性和不可解性》中，图灵机在第1章的第一页就出现了。

和克莱尼一样，戴维斯把自然数表示为连续的tick符号，并用图灵机来计算函数。用图灵机计算加法、减法、乘法的例子出现在书的第12页。

虽然《可计算性和不可解性》表面上是数学图书，但是戴维斯意识到这本书“由于和某些哲学问题以及数字计算机理论相关，一些非数学家也可能有兴趣一读”。［9］

为进一步强调不同，《可计算性和不可解性》作为McGraw-Hill出版公司”信息处理和计算机系列丛书“中的一部作品出版。即使在这套丛书中，这本书也是独一无二的。其他书都

转载请注明:http://www.aideyishus.com/lkzp/1074.html