图灵构想通用计算机

早在1834年，查尔斯·巴贝奇就构想出了一种自动的计算机器，这就是他虽然提出但从未制造出来的分析机，旨在完成各种数值计算。他曾对机器运算产生了浓厚的兴趣，并且设想出一种机器——“差分机”，旨在有效地构造数学表。不久，巴贝奇突发灵感，构想出他那更为野心勃勃的差分机。

为了强调他的机器的威力和应用范围，巴贝奇开玩笑说，“除了编乡村舞蹈，它可以做任何事情。”事实上，今天的计算机完全可以通过程序设计而编出乡村舞蹈。今天，如果我们想用一个类似的比喻来强调计算机的威力和应用范围，那么我们就会发现，写出这个句子并不容易。几乎任何可以设想的包含符号，数字或文本的任务都或者已经处于计算机的能力范围之内，或者某位专家语言不久就可以做到。

显然，我们关于计算的概念已经发生了天翻地覆的变化。1935年，阿兰·土林在解决大卫·希尔伯特所提出的一个数理逻辑问题的过程中，突出了基本的概念。

巴贝奇原本打算完全用类似齿轮这样的机械部件制造出他的机器，毫不奇怪，由于这个装置的复杂性，他没有成功。只是到了20世纪30年代，随着使用电子继电器的机电计算器的发展，应用范围达到了巴贝奇所设想的程度的机器才得以制造出来。但是30～40年代，没有一个参与这项工作的人曾经谈起过能够超越数学计算的机器。正如我们将会看到的，第一个使巴贝奇的梦想重新焕发生机的人是霍华德·艾肯。他写道：

如果，一台为了微分方程数值解而设计的机器与百货商店里的一台用来开账单的机器的基本逻辑是一致的，那么我们将把这看成我所遇到过的最令人惊异的一致。

艾肯是在1956年说这段话的，那时计算机通过编程来实现这两项任务在商业上已经是可能的了。如果艾肯认识到阿兰·图灵20年前所发表的论文的重要性，他就不会作出如此可笑的论断了。

希尔伯特的判定问题

莱布尼茨曾经梦想能够把人的理性还原为计算，并且有强大的机器能够执行这些计算。弗雷格第一次给出了一个似乎能够解释人的一切演绎推理的规则系统。哥德尔在1930年的博士论文中曾经证明了弗雷格的规则是完备的，这样就回答了希尔伯特两年前提出的一个问题。希尔伯特也试图找到清楚明白的计算程序，只要用所谓一阶逻辑的符号系统写出的某些前提和结论给定，那么通过这些程序就总是可以判定，弗雷格的规则是否足以保证结论能够从那些前提中导出。寻找这些程序的任务后来被称为希尔伯特的“判定问题”。

当然，用于解决特定问题的计算程序系统并不是什么新的东西。事实上，传统数学课程在很大程度上就是由这些或被称为算法的计算程序构成的。我们先是学习数的加减乘除算法，然后又学习对代数表达式进行操作和解方程的算法。如果我们又学习了微积分，那么我们就学会了使用莱布尼茨最早为这门学科发展出来的算法。然而，希尔伯特所要找的是一种范围极广的算法。从原则上讲，解决他的判定问题的算法将把人的一切演绎推理都还原为冷冰冰的计算，它在很大程度上将实现莱布尼茨的梦想。

数学家们经常喜欢从两个方向解决一个困难的问题。一方面，他们试图考虑一般问题的特殊情形，而另一方面则是把一般问题还原为某些特殊情形。如果一切顺利，这两条路将殊途同归，从而为一般问题提供一种解答。关于判定问题的工作就是沿着这两个方向进行的，而且已经找到算法的特殊情形与一般问题被还原成的特殊情形之间的鸿沟已经被大大缩小，以至于再往前走一小步就可望完全填平这个鸿沟了，这样就可以给出希尔伯特所要寻求的算法。

关于判定问题的工作主要是处理被称为前束式的表达式。它们是包含¬，⊃，∧，∨，∃，∀等逻辑符号的表达式，其中所有的存在量词（∃…）和全程量词（∀…）都先于所有其他符号出现在表达式的开头。不难证明，判定问题可以被还原为为这样一个问题找到一种算法，即给定一个前束式，判定它是否是可满足的，也就是说，是否存在着某种解释前束式中非逻辑符号的方法，使得它可以表示一个真句子。为了说明这个概念，考虑以下两个前束式：

(∀x)(∃y)(r(x)⊃s(x, y))和
(∀x)(∃y)(q(x)∧¬q(y))

前一个前束式是可满足的：例如，我们可以令变量x，y表示在某一时刻活着的人，r（x）表示“x是一个一夫一妻制的结婚的男人”，s（x，y）表示“y是x的妻子”；于是，根据这一解释，第一个前束式说的就是“每一个一夫一妻制的结婚的男人都有一个妻子”——这当然是一个真陈述。而第二个前束式则是不可满足的，因为无论如何选择个体域，无论如何解释符号q，这一前束式既规定所有个体都具有q所表示的性质，又规定有些个体没有这种性质。

前束式可以通过它们开头的存在量词和全程量词的特殊样式来分类。例如，前置集∀∃∀的意思是所有以（∀…）（∃…）（∀…）开始的前束式所组成的集合。在哥德尔于1932年发表的一篇论文中，他提出了一种可以检验任何属于前置集∀∀∃…∃的前束式的算法。在一年以后发表的一篇论文中，他证明了要想解决判定问题，只要提出一种算法能够检验所有属于前置集∀∀∀∃…∃的前束式的可满足性就足够了。这样，已经得到的结果和所需的结果之间的差距就只剩下一个全程量词∀了。

剑桥的G·H·哈代对此持怀疑态度，他无不气恼地评论道：“当然不存在这样的定理，这是非常幸运的，因为它如果存在，那么我们就可以用一套机械的规则来解决一切数学问题，我们数学家的活动也就将寿终正寝了。”哈代当然不是第一个确信他的技巧永远也不会被机器替代的行家里手，但后来的结果表明，这位行家说对了！

图灵得知希尔伯特的判定问题开始思考如何能够证明这样的算法是不存在的。

图灵对计算过程的分析

图灵知道，一种算法往往是通过一系列规则指定的，一个人可以以一种精确的机械方式遵循这些规则，就像按照菜谱做菜一样。但图灵把关注的焦点从这些规则转移到了人在执行它们时实际所做的事情。他能够说明，通过丢掉非本质的细节，这样一个人可以被局限在少数几种极为简单的基本操作上，而不会改变最终的计算结果。接下来，图灵要说明这个人可以被一个能够执行这些基本操作的机器所替代。然后，只要证明仅仅执行那些基本操作的机器不可能判定一个给定的结论是否可以用弗雷格的规则从给定的前提中导出，他就能够下结论说，判定问题的算法是不存在的。作为副产品，他发现了通用计算机器的一个数学模型。

为了尽可能］地弄清楚图灵的思考过程，让我们想象自己正在观察一个计算过程。正在做计算的人实际上在做什么呢？她正在一张纸上做记号。我们会看到，她正在把注意力从以前写的东西转移到当前正在写的东西。图灵把不想干的细节从这种描述中去除。她在工作时是否在喝咖啡？这当然是不相干的。她是用铅笔还是用钢笔写字？这也无关紧要。那么，纸张的大小如何？如果纸张较小，那么她就很可能需要经常看看前面那些纸。但图灵确信，这只关乎方便而绝非必然。即使她所用的纸张小得无法在一个符号下面写下另一个符号，或者说，即使她的是一卷被分成水平方格的纸袋，情况也不会发生任何本质的变化。为简便起见，我们设想她正在计算一个乘法：

  4231
   x77
------
 29617
296170
------
325767

我们可以想象她正沿着一个被划分成方格的纸带进行工作，这不会丢失任何本质性的东西，比如

4231x77=29617+296170=325787

图灵确信，虽然沿着这样一个一堆纸带进行一个复杂的计算也许是件麻烦的，但这样做并不会导致什么基本问题。我们继续来观察计算过程，现在把注意力集中在一卷纸带：我们的目光沿着纸带前后移动，写下符号，有时还会返回去擦除符号并在原处写下新的符号，而且还取决于她当前的心灵状态。即使是在我们这个简单乘法的例子中，当她注意到一对对的数字时，她的心灵状态将决定是把它们相加还是相乘。开始时，纸带看起来是这样的：

   ↓  ↓
4231x77=

数字1和7上方的箭头（↓）表示她最初注意的是这些符号。她在纸带上写下它们的乘积7:

  ↓   ↓
4231x77=7

现在她把注意力转向数字3和7，接下来轮到它们相乘了。像这样把一对对的数字相乘之后，她需要把得到的两部分乘积加起来：

            ↓      ↓
4231x77=29617+296170=

她先把数字7和0加起来，得到

           ↓      ↓
4231x77=29617+296170=7

现在她必须把1和7加起来得到8.注意，这时她所注意到的数字与她开始计算时进行相乘的数字是相同的。然而尽管数字是相同的，但她的心灵状态却不一样，这时它们是相加而不是相乘。

这个简单的例子已经说明了任何计算所具有的本质特征。每一个进行算术，代数，微积分或任何一个数学分支中的计算的人的操作都要受以下限制：

• 在计算的每一个阶段，只有少数符号受到了注意
• 每一个阶段所采取的行动仅仅取决于受到注意的那些符号以及计算者当前的心灵状态

一个人可以同时处理多少符号？正确地进行一项计算需要多少人？

第一个问题的答案当然是因人而异的，但无论如何不可能很多。而对于第二个问题，答案是一个人。这是因为，同时注意几个符号总是可以通过每次注意一个符号来实现。而且，把注意力从纸带上的一个方格转到一定距离以外的另一个方格总是可以通过一系列移动来实现，其中每一次移动或者是左移一个方格，或者是右移一个方格。由这一分析可以推出，任何计算都可以被看作是以下面的方式进行的：

• 计算通过在一条被划分成方格的纸带上写下符号来进行。
• 执行计算的人在每一步都只注意其中一个方格中的符号。
• 她的下一步将仅仅取决于这个符号和她的心灵状态。
• 她的下一步是这样的：她在当前注意的方格里写下一个符号，然后把注意力转向它左边或右边的相邻方格。

现在就很容易看出，做这项工作的人可以用一个机器来替代，纸带（可以看成带有用编码信息来表示的符号的磁带）在机器中来回移动。计算者的心灵状态用机器内部的不同布局来表示。机器的设计必须使得每一时刻纸带上只有一个符号，这个符号被称为被注视符号.根据其内部布局和被注视符号，机器将在纸带上写下一个符号（取代被注视符号），然后或者继续注视同一个方格，或者转到纸带上与之相邻的左边或右边的位置。就计算而言，机器如何制造或者由什么来制造，这都无关紧要，重要的只是它能够控制一个具有不同布局（也被称作状态）的数，当它处于每一种布局或状态时，都可以作相应的处理。

问题的关键不在于真的造出一台图灵机，它毕竟只是数学的抽象。关键之处在于，基于图灵对计算概念的分析，我们就有可能得出结论说，通过某种算法程序可计算的任何东西都可以通过一台图灵机来计算。因此，如果我们可以证明某项任务无法用图灵机来完成，那么我们就可以说，没有任何算法程序可以完成这项任务。这就是图灵证明判定问题不存在算法的方法。此外，图灵还说明了如何造出这样一台图灵机，这台图灵机可以独自完成任何图灵机所能做到的任何事情——通用计算机的一个数学模型。

运转的图灵机

由图灵对计算过程的分析我们可以看出，任何计算都可以通过一种后来被称为图灵机的受到严格限制的装置来实现。我们可以考虑几个非常简单的例子。演示一台图灵机需要哪些东西呢？

首先，我们需要它所有可能的状态。然后，对于每一个状态以及纸带上可能出现的每一个符号，我们必须指明处于那个状态的机器遇到那个符号时会怎样进行操作。我们已经说过，这个操作仅仅包括被注视方格中的符号的可能改变，向左或向右移动一个方格以及状态的一种可能变化。如果我们用大写字母来表示不同的机器状态，那么陈述：

当机器正处于状态R，注视纸带上的符号a时，它将用b来代替a，向右移动一个方格，然后转到状态S。

就可以用符号表示为R a: b -> S.类似地，同样条件下向左移动一个方格可以表示为R a:b <- S.最后，只改变纸带上的符号而不沿纸带运动的状态可以表示为R a: b * S.我们通常把这些公式称为“五元组”，因为其中的每一个都要用到5个符号（不包括冒号）。于是任何一台图灵机都可以通过一些列这样的五元组来演示。

让我们看看如何造出一台能够检验一个给定的自然数是奇数还是偶数的图灵机。所指定的数将用哦我们呢所熟悉的记法记作由1，2，3，4，5，6，7，8，9，0所组成的一串数字。当然（以这种方式写出）一个数是奇是偶一眼就能看出。只要看看最右边的数字，如果它是1，3，5，7或9，那么这个数就是奇数，否则就是偶数。但是我们所使用的装置将从注视最左边的数字开始。由于图灵机每次只能处理一个数字，而且每次只能移动一个方格，所以如何进行处理并不是显而易见的。写在纸带上的“输入的”数就像这样：

Q
↓
94383

这里纸带上写的数字94383，机器处于它最初的状态Q上，此时正在注视最左边的方格。虽然纸带只显示了5个方格（刚好足够容纳输入的数），但对于一项计算来说，很重要的一点就是纸带的量没有限制。因此，如果机器试图从纸带的最右端移出去，那么一个空白的方格总会出现。我们把空白方格当作一个特殊字符来处理，记作□。

我们的图灵机将总是从注视最左端方格的状态Q开始。无论什么数输入机器，最后的结果都是一条除一个方格外其余都是空白的纸带。如果最初输入的数是偶数，那么那个方格中将是0；如果最初输入的数是奇数，那么那个方格中将是1.这台机器将具有4个状态，分别用Q，E，O和F来表示。我们已经说过，Q是最初状态。无论机器处于什么状态，如果它注视的是一个偶数，那么它将擦除这个数字（即在它上面印上一个空格），向右移动一格，然后终止于状态E。类似地，如果它注视的是一格奇数，那么它将擦除这个数字，向右移动一格，然后终止于状态O。最终，它将注视并擦除整个输入，得到一个空格。如果它终止于状态E，那么它将印上一个0；如果终止于状态O，则印上一个1.然后，它将向左移动一格停止下来。下面是组成这个机器的五元组：

输入为94383的全部计算显示了机器的详细操作：

Q
↓
94383
 O
 ↓
□4383
  E
  ↓
□□383
   O
   ↓
□□□83
    E
    ↓
□□□□3
     O
     ↓
□□□□□□
     F
     ↓
□□□□□1

机器从注视数字9的状态Q开始，相应的五元组位于表中的第二行，最后一列。这一五元组使机器擦除了9，向右移动一个位置，进入状态O。在注视4的状态O中，相应的五元组位于表中的第五行，第三列。相应地，机器擦除4，向右移动，进入状态E。接着，在注视3的状态E中，相应的五元组位于表中的第四行，第二列，机器擦除3，继续向右移动，进入状态O。在注视8的状态O中，相应的五元组位于表中的第五行，最后一列，机器擦除8，向右移动，进入状态E。状态E又一次注视3，相应的五元组位于表中的最后一行，第二列，空格被1替换，机器处于原位不懂，进入状态F。在状态F中，机器注视的是一格空格，此时没有五元组可用了，于是机器停止。计算的结果是纸带上只留有一格数字1，这是正确的，因为输入的数为奇数。

与物理装置不同，图灵机仅仅作为数学抽象而存在，所以可以不必受纸带的量的限制。当由一个五元组Q□: □ -> Q所组成的图灵机从一条空白的纸带开始时，它将随着纸带的量的持续增长而“永远”向右移动：

Q
↓
□
 Q
 ↓
□□
  Q
  ↓
□□□
   Q
   ↓
□□□□
  .
  .
  .

图灵机的计算可以永远持续下去，即使它所通过的纸带的量是固定的。例如，考虑由Q1: 1 -> Q和Q2: 2 <- Q这两个五元组所组成的图灵机。如果输入为12，那么这台机器将像下面这样来回跳动：

Q
↓
12
 Q
 ↓
12
Q
↓
12
 Q
 ↓
12
Q
↓
12
 Q
 ↓
12
 .
 .
 .

这种行为严格依赖于输入。例如，如果输入是13，那么同一台机器的计算将是下面这样：

Q
↓
13
 Q
 ↓
13

在注视3的状态Q中，没有五元组可以应用，于是机器停止。

总之，某些输入会使得有些图灵机停止下来，另一些则不会。图灵把康托尔的对角线方法应用于这种情况，得到了图灵机所不能解决的问题，由此便推出了判定问题的不可解性。

图灵应用康托尔的对角线方法

马科斯·纽曼的课使阿兰·图灵注意到了判定问题，它是令人感兴趣的部分是哥德尔的不完备定理。所以正在思考用一系列五元组来表示他的机器的图灵就很自然地想到了用自然数来做机器的代码，并且可以使用康托尔的对角线方法。我们将遵循图灵的思路，设置一种与他所使用的代码相似但不尽相同的代码。

为了设置我们的代码，我们考虑彼此由分号隔开的组合图灵机的额五元组。于是由一对五元组：

Q1: 1 -> Q Q2: 2 <- Q

所组成的图灵机可以记作Q1 : 1 -> Q; Q2: 2 <- Q.然后我们根据下述方案用一串十进制数来替换每一个符号：

• 开始和结尾都为8，其间只有0，1，2，3，4，5的字串将被用来表示纸带上的符号。下表给出了我们将要用来替换十进制数和□（作为纸带上的符号）以及→←*:;的特殊表示：

• 开始和结尾都为9，其间只有0，1，2，3，4，5的字串将被用来表示状态。特别地，开始的状态Q将用字串99来表示。

于是，刚才所说的两个五元组的图灵机将用998018 646 8018 616 99 77 998028 646 8028 626 99来编码。对于我们用来区分奇数和偶数的图灵机来说，我们可以分别用919，929和939来编码E，O，F这三个状态。这样，整个机器的码数就成为：

9980086468558616919 77 9980286468558616919 77 9980486468558616919 77
...
...
...

尽管这不过是一格大数，但它已经显示了各个五元组的码数。请注意，从这个码数中恢复五元组是很简单的：首先找到分隔五元组码数的77这个字串，然后再对每一个五元组进行解码。例如：92985386468558616919这个码数可以分解成929 8538 646 8558 616 919，它可以被解码为O8: □ -> □E.当然，编码可以通过许多不同的方式来设置，但这一方案拥有一个重要而有用的性质，那就是明显的可解码性。

注意，这一编码方案允许带子上的符号可以不是十进制数和□，而是像81118这样的符号。这就使得标记带子上的特定方格的符号可以出现，从而在返回时可以被找到。可以证明，使用十进制系统与图灵机所能做的事情没有关系。

从上面的例子可以看出，任何图灵机都可以被认为是从纸带上的数的最左边的数字开始注视。在这些数中，有些数会使机器最终停止，而另一些则会使机器永远运行下去。让我们把由前一类自然数所组成的集合称为图灵机的停机集合。现在，如果我们认为一台图灵机的停机集合组成一个“包裹”，并认为那台机器的码数就是这个包裹的标签，那么我们就具备了应用对角线方法的标准条件：包裹上的标签就是包裹里的东西——这里是自然数。

对角线方法将允许我们构造出一格与图灵机的任何停机集合都不同的自然数集合，我们把它称为D。方法是这样的：D将完全由图灵机的码数组成。对于每台图灵机来说，它的码数属于D，当且仅当它不属于那台机器的停机集合。这样，如果某台图灵机的码数属于它的停机集合，那么这个码数就不属于D；而如果这个码数不属于机器的停机集合，那么它就属于D。无论是哪种情况，D都不可能是这台机器的停机集合。既然每台图灵机都是如此，我们就可以得出结论说，集合D不是任何图灵机的停机集合.

不可解问题

自然数集D的定义使它与任何图灵机的停机集合都不同。但这与判定问题有什么关系呢？它们之所以有关，是因为希尔伯特把这个问题称为数理逻辑的基本问题.希尔伯特认为，对判定问题的解答将会为解决所有数学问题提供一种算法。同样的理解也潜藏于哈代的看法中，他确信判定问题永远也不会有一个解答。只要我们严肃地看待这一点，便会发现，它隐含着只要有一个数学问题可以被证明在算法上是不可解的，那么判定问题本身就必定是不可解的。集合D将为我们提供这样一个例子。

考虑下面这个问题：

找到一种算法，判定一个给定的自然数是否属于集合D。

这就是一个不可解问题的例子。要想弄明白不存在这样的算法，我们首先要看到，通过图灵对计算过程的分析，如果存在着这样一种算法，那么就会有一台图灵机能够完成同样的事情。就像我们构造出来的区分奇偶数的图灵机那样，我们可以想象一台处于初始状态Q的机器人从已知数的最左端数字开始注视，就像这样：

Q
↓
32691

类似地，我们将希望机器最终会停机，除一个数字以外，纸带的其余部分都是空白的：如果输入的数属于集合D，那么这个数字就是1，否则就是0.最后，我们希望它终止于状态F，并且机器五元组都不从字母F开始。例如，

     F
     ↓
□□□□□0

现在，我们想象把以下两个五元组加到我们的图灵机中：

F0: □ -> F和F□: □ -> F

如果输入的数属于D，那么新机器将像以前那样运转，最终将以纸带上的1而告终。然而，如果输入的数不属于D，那么这台机器将永远向右移动。因此，这台新机器的停机集合恰恰就是集合D。然而这是不可能的，因为D是用对角线方法构造出来的，所以它与任何图灵机的停机集合都不同。因此，我们关于存在着一种区分D的成员与非成员的算法的假定必定是错误的。这样的算法不存在！用算法来区分D的成员与非成员的问题是无法解决的！

应当强调指出，如果真有一种把D的成员与非成员区分开来的算法，那么这些输入输出就不成其为问题了。毕竟，把输入的数交给一个人去执行那种形式的算法不会有问题，让她把输出的数以所希望的形式印在带子上也不会有什么问题。

正如我们已经看到的，希尔伯特和哈代都相信，对于判定问题的一个算法解将意味着任何数学问题都可以通过一种算法来解决。所以一旦我们有了一个算法上不可解的数学问题，那么判定问题的不可解性就得到了。为了看出如何与集合D发生关系，我们把下面的前提和结论与每一个自然数n相联系：

前提

n是某台图灵机的码数，它被印在机器的纸带上，最左边的数字被注视。

结论

以这种方式启动的图灵机最终将停止。

利用一阶逻辑的语言，这两个句子被翻译成逻辑符号。于是可以证明，这个结论可以用弗雷格的规则从前提中导出，当且仅当这台图灵机从它纸带上的码数开始后将最终停止。相应地，它为真当且仅当当n不属于D。因此，如果我们有了一种判定问题的算法，那么我们就可以用它来判定一个数是否是D的成员。也就是说，给定一个自然数n，我们可以用这种判定问题的算法来检验这个结论是否可以从前提中导出。如果可以，那么我们就知道n不属于D，如果不可以，那么n就属于D。由此可知，判定问题在算法上是不可解的。

尽管判定问题的不可解性可以用这种方法来证明，但它是相当麻烦的，因为我们需要改进图灵机的构造来处理十进制整数。

为了理解图灵机的实际工作，我们先来说明，判定一台带子完全空白的图灵机是否会停机的问题是不可解的。因为如果假定这个问题有一种算法，那么为了检验码数n是否属于D，我们先写出构成码数为n的图灵机T的五元组，然后写出使n写在图灵机带子上的五元组。把这些五元组家在T的五元组上，我们就得到了一台新的机器，它将先把n写在带子上，然后按照输入n时T的响应来运转。这台从空白带子开始的新机器最终将停机，当且仅当T从带子上的n开始时会最终停机，而后一结论成立，当且仅当n不属于D。因此，所假定的用于检验一个从空白带子开始的给定的图灵机最终是否会停机的算法，可以被用来解决判定一个数是否属于D的不可解问题。

我们还注意到，一台给定的图灵机是否曾经印下一个符号的问题也是不可解的。这是因为，很容易使得一台图灵机无论什么时候停机，它都处于不再启动五元组的状态F。我们选择这台机器的任何五元组中都没有出现的一个新符号X，然后加入五元组：

F a: X * F

其中a可以是出现在原始五元组中的任何符号。无论最初的机器什么时候停机，这台新机器都将会印上X。于是我们便得到，没有算法可以判定一台从空白带子开始的图灵机是否将印上某一符号。这是图灵用一阶逻辑语言表达的问题，于是我们便得到了判定问题的不可解性。

图灵的通用机

图灵的工作中有一些地方是令人困惑的。他已经证明，没有图灵机可以被用于解决判定问题。然而，为了说明判定问题不存在任何种类的算法，图灵曾诉诸他对人执行一项计算时的过程的讨论。

他关于任何这样的计算也可以用一台图灵机来完成的论证是否令人信服呢？

为了支持他的论证，图灵证明了许许多多复杂的数学计算都可以在图灵机上完成。例如，图灵说明了如何构造出能够产生0和1的字串以得到实数e和π的二进制表示的机器。对于标准数学中说出现的其他实数问题——整系数多项式方程的根甚至是贝塞尔函数的实零点，他也如法炮制。

不过他在检验自己的工作的有效性方面所提出的最为大胆的，影响最为深远的思想却是通用机。

考虑被一个空白方格所隔开的写在图灵机纸带上的两个自然数（通常的十进制记法）。第一个数是某台图灵机的码数，第二个数是这台机器的一个输入：

| 图灵机M的码数 | M的输入 |

现在想象一个人要完成这样一项任务，他要完成把纸带上的第二个数作为输入时，码数为第一个数的图灵机所要做的事情。这项任务是很简单的。她先得到码数为纸带上第一个数的机器的五元组，然后只要按照五元组的要求在纸带上进行操作就可以了。
图灵的分析已经证明，任何计算任务都可以通过一台图灵机实现。把这一思想应用到当前的任务中，我们可以设想一台图灵机，它从图灵机M的码数开始，只要它的输入与M的输入相同，它就可以完成机器M所能做到的事情。

一台图灵机单凭自身就可以完成任何图灵机可能做到的任何事情。图灵通过说明一个人如何能够得出这样一台通用机的五元组来验证这个非凡的结论。在现在被称为程序设计的几页文献中，他出色地做到了这一点！

自莱布尼茨地时代起，甚至更早一些时候，人们已知在对计算机器进行思考。在图灵之前，一般地想法是，对于这种机器来说，机器，程序和数据这三种范畴是完全分离地。机器是一种物理对象，今天我们把它称为硬件；程序是做计算地方案，也许体现在穿孔卡片或线路连接板上地缆线连接上；而数据则是数据输入。

图灵的通用机表明，这三种范畴相互分离是一种错觉。图灵机开始被看成是一台拥有机械部件——硬件——的机器。它在通用机纸带上的码数则起到了程序的作用，它为通用机详细指明了执行计算所需要的指令。最后，通用机在一步步的运转中把机器码的数字仅仅看成需要一步处理的数据 .

这三个概念之间的流动性对于现在的计算机实践来说是非常基本的。用一种现代的编程语言所写的程序对于处理它以使其指令能够得到执行的解释程序或编译程序来说就是数据。事实上，图灵的通用机本身就可以被看成一个解释程序，因为它是通过解释一连串五元组来执行它们所标明的任务的。

图灵的分析为理解古代的计算技术提供了一种独到而深刻的角度。计算的概念原来远不止算数和代数运算。同时，这种眼光预见到了原则上能够计算任何可计算的东西的通用机。图灵关于专用机器的例子已经成了程序设计的实例；通用机器则是解释程序的第一个例子。

通用机还为存储程序计算机提供了一个模型，纸带上编了码的五元组扮演了存储程序的角色，机器在程序和数据之间没有作基本的区分。

最后，通用机表明了如何能够把被认为是机器功能描述的五元组形式的硬件，替换成以编码的形式存储在通用机纸带上的以同样的五元组形式表现出来的等价的软件。

虽然图灵的大部分成就都可以说是对美国人所做工作的再发现，但他对计算概念的分析以及他对通用计算机的发现却是全新的。

阿兰·图灵在普林斯顿

图灵去普林斯顿大学两年里完成了一篇著名的博士论文。由于从系统外部考察时，哥德尔的已经系统的不可判定命题可以被看成为真，一个自然的想法就是把这样一个命题作为一个新的公理加到已知系统中，这样就得到了一个新系统，其中不可判定命题不再时不可判定的。当然，应用哥德尔的方法，新系统也会有它本身的不可判定命题。图灵在他的论文中一次次地这样做，从而研究了系统的分层结构。

这篇论文所引入的另外一个概念是一种改进了的图灵机，它可以中断它的计算来寻求外部信息。利用这样的机器，谈论两个不可解问题中哪一个“更不可解”就是可能的了。

图灵的通用计算机是一个奇妙的概念装置，它仅凭自己就可以执行任何算法任务。但我们真能制造出这样一种东西吗？除了这种机器原则上所能完成的任务之外，它的设计和制造能否使其在可以接受的时间内应用适量的资源来解决真实世界的问题呢？这些问题从一开始就被图灵注意到了。

为了熟悉现有的技术，图灵特地用机电继电器制造出了一台能够把二进制数进行相乘的装备。为此，他进入了物理系研究生的机加工车间，制造了各种部件，而且亲手制造出了所需的继电器。

阿兰·图灵的战争

阿兰·图灵倾向于忽视我们大部分人生活于其中的社会框架，在任何情况下，他都会通过思考得出答案，并且从头开始寻求最佳的行动。

与此同时，图灵从未停止思考通用机概念的可应用性。他猜想，正是这种通用性概念揭示了人的大脑拥有强大的能力的秘密，从某种意义上来说，我们的大脑正是通用机，他设想，如果一台通用机可以被制造出来，那么它就可以玩象棋这样的游戏，可以像一个孩子那样学习许多东西，并且最终展示出智能行为。在布莱奇利庄园，人们就这些思想曾经有过许多讨论，图灵甚至还草拟了可以让机器下棋的算法。同时，制造一台通用计算机说需要的某些硬件也在布莱奇利庄园发展起来。

美国无线电公司的真空管可以实现以前由电子继电器来完成的逻辑转换。这些真空管很快：它们的电子以接近光速的速度行进，而继电器则依赖于机械运动。事实上，真空管电路已经被实际应用于电话交换，图灵与这项研究的带头人——极富才华的工程师T·弗劳尔斯进行了联系。在弗劳尔斯和纽曼的领导下，一台体现了“图灵主义”的机器很快就做出来了。这台被称为“巨人”的机器是一项工程奇迹，它包含1500根真空管。世界上第一台电子自动计算装置诞生了。毫不奇怪，从本质上讲，它所进行的计算是逻辑的而非算术的。被截获的德军讯息以打孔纸带的形式被一个速度极快的读带机输送到机器里：当纸带通过读带机时，从纸孔中透出的光束被把信号送给“巨人”的光电管截获。纸带必须被迅速地读出，以免减慢真空管电路的操作。

到了1945年战争结束时，图灵已经掌握了真空管电子学的应用知识。他确信可以用真空管电路来制造一台通用计算机，于是便花了大量精力去思考机器的具体实现和各种应用方面的事情。现在，他所需要的只是充分的支持和有利条件，以便把这项伟大的工程付诸实施。