T12：0０→0０R，0１→0０R，1０→0０R。
其中，T
0简单地就是向右移动并且抹去它所遇到的每一件东西，永不
停止并永不往回退。机器
T
1最终得到同样的效应。但它是以更笨拙的方
法，在它抹去磁带上的每个记号后再往后跳回。机器
T
2也和机器
T
0一样无
限地向右移动，但是它更有礼貌，简单地让磁带上的每一件东西原封不动。
由于它们中没有一台会停下，所以没有一台可以合格地被称为图灵机。T
3
是第一台可敬的机器。它的确是在改变第一个（最左边）的１为０后便谦
虚地停止。
T4遭遇了严重的问题。它在磁带上找到第一个１后就进入了一个没有
列表的内态，所以它没有下一步要做什么的指令。T
8、T
9和
T
10遇到同样的
问题。T
7的困难甚至更基本。把它编码的０和１的串涉及到五个接续的１
的序列：１１０１１１１１０。对于这种序列不存在任何解释，所以只要
它在磁带上发现第一个
1就被绊住。（我把
T
7或其他任何机器
T
n，它的
n
的二进位展开包含多于四个１的序列称为不是正确指明的。）机器
T
5、T
6
和
T
12遭遇到和
T
0、T
1和
T
2类似的问题。它们简单地、无限地、永远不停
地跑下去。所有
T
0、T
1、T
2、T
4、T
5、T
6、T
7、7
8、T
9、T
10和
T
12都是伪品！
只有
T
3和
T
11是可工作的，但不是非常有趣的图灵机。T11甚至比
T
3更谦虚，
它在第一次遇到
1时就停止，并且没有改变任何东西！
我们应该注意到，在表中还有一个多余。由于
T
6和
T
12从未进入内态
1，机器
T
12和
T
6等同，并在行为上和
T
0等同。我们既不必为这个多余，
也不必为表中的图灵机伪品而烦恼。人们的确可以改善编码以摆脱许多伪
品和大大减少重复。所有这些都是以使我们可怜的普适图灵机变得更复杂
作为代价。普适图灵机必须把所读到的号码
n解码并假装成图灵机
T
n。如
果我们可以把所有伪品（或者多余量）取走，这还是值得做的。但是，我
们很快就会看到，这是不可能的！这样，我们就不触动我们的编码好了。
例如，可方便地把具有
.０００１１０１１１００１００００.
接续记号的磁带解释成某个数字的二进位表示。我们记得０在两端会无限
地继续下去，但是只有有限个１。我还假定１的数目为非零（也就是说至
少有一个１）。我们可以选择去读在第一个和最后一个
1（包括在内）之
中的有限的符号串，在上述的情况是为一自然数的二进位写法
１１０１１１００１，
它在十进位表示中为
441。然而，这一过程只能给我们奇数（其二进位表
示以１结尾的数）。而我们要能表示所有的自然数。这样，我们采取移走
最后的１的简单方案（这个１仅仅被当作表示这一程序的终止记号），而
把余下来的当成二进位数来读
5。因此，对于上述的例子，我们有二进位
数
１１０１１１００，
它是十进位的
220。这个步骤具有零也用磁带上的记号代表的好处，也就
是
.００００００１００００００.
我们考虑图灵机
T
n对我们从右边提供给它的磁带上（有限的）０和１
的串的作用。根据上面给出的方案，可方便地把这串也考虑作某一个数，
譬如
m的二进位代表。我们假定，机器
T
n在进行了一系列的步骤后最终到
达停止（即到达
STOP）。现在机器在左边产生的二进位数串是该计算的答
案。让我们也以同样方式把这当作，譬如是
p的二进位代表来读。我们把
表达当第
n台图灵机作用到
m上时产生
p的关系写成：
Tn(m)=p。
现在，以稍微不同的方式看这一关系。我们把它认为是一种应用于一
对数
n和
m以得到数
p的一个特别运算。（这样，若给定两个数
n和
m，
视第
n台图灵机对
m作用的结果而得出
p。）这一特别运算是一个完全算
法的步骤。所以它可由一台特殊的图灵机
U来执行。也就是说，U作用到
一对(n，m)上产生
p。由于机器
U必须作用于
n和
m两者以产生单独结果
p，
我们需要某种把一对(n，m)编码到一条磁带上的方法。为此，我们可假定
n以通常二进位记号写出并紧接着以序列１１１１１０终结。（我们记得，
任一台正确指明的图灵机的二进位数都是仅仅由０，１０，１１０，１１
１０和１１１１０组成的序列，因此它不包含比四个１更多的序列。这样，
如果
T
n是正确指明的机器，则１１１１１０的发生的确表明数
n的描述已
终结。）按照我们上面的规定，跟着它的每一件东西简单地是代表
m的磁
带（也就是，紧跟二进位数
m的是１０００.）。这样，这第二个部分简
单地就是
T
n假设要作用的磁带。
作为一个例子，如果我们取
n=11和
m=6当作
U要作用的磁带，其记号
序列为
.０００１０１１１１１１１０１１０１００００.
这是由以下组成的：
.００００（开始的空白带）
.００００（开始的空白带）
１１１１１０（终结
n）
１１０.（6的二进位表示）
１００００.（余下的磁带）。
在
T
n作用到
m上的运算的每一接续的步骤，图灵机
U要做的是去考察
n的表达式中的接续数位的结构，以使得在
m的数位（也就是
T
n的磁带）
上可进行适当的代换。在原则上（虽然在实践中肯定很繁琐）不难看到人
们实际如何建造这样的一台机器。它本身的指令表会简单地提供一种，在
每一阶段读到被编码到数
n中的“表”中，应用到
m给出的磁带的位数时，
合适元素的手段。肯定在
m和
n的数位之间要有许多前前后后的进退，其
过程会极为缓慢。尽管如此，一定能提供出这台机器的指令表，而我们把
它称为普适图灵机。把该机器对一对数
n和
m的作用表为
U(n,m)，我们得
到：
U(n,m)=Tn(m)。
这儿
T
n是一台正确指明的图灵机
6。当首先为
U提供数
n时，它准确地摸
拟第
n台图灵机！
因为
U为一台图灵机，它自身也必须有一号码；也就是说，我们有
U=Tu
此处号码
u待定。u究竟是多少呢？事实上我们可以准确地给出
u=72448553353393175771983950396157112379523606725565596311081447
9660650505940424109031048361363235936564444345838222688327876762
6556144692814117715017842551707554085657689753346356942478488597
0469347257399885822838277952946834605210611698359459387918855463
2644092552550582055598945189071653741489603309675302043155362503
4984529832320651583047664142130708819329717234151056980262734686
4299218381721573334828230734537134214750597403451843723595930906
4002432107734217885149276079759763441512307958639635449226915947
9654614711345700145048167337562172573464522731054482980784965126
9887889645697609066342044779890219144379328300194935709639217039
0483327088259620130177372720271862591991442827543742235135567513
4084222299889374410534305471044368695876405178128019437530813870
6399427728231564252892375145654438990527807932411448261423572861
9311833261065612275553181020751108533763380603108236167504563585
2164214869542347187426437544428790062485827091240422076538754264
4541334517485662915742999095026230097337381377241621727477236102
0678685400289356608569682262014198248621698902609130940298570600
1743006700868967590344734174127874255812015493663938996905817738
5916540553567040928213322216314109787108145997866959970450968184
1906299443656015145490488092208448003482249207730403043188429899
3931352668823496621019471619107014619685231928474820344958977095
5356110702758174873332729667899879847328409819076485127263100174
0166787363477605857245036964434897992034489997455662402937487668
8397514044516657077500605138839916688140725455446652220507242623
9237921152531816251253630509317286314220040645713052758023076651
83351995689139748137504926429605010013651980186945639498（或者至少是这等数量级的其他的可能性）。这个数无疑是极其巨大，但
是我似乎没有办法使它变小许多。虽然我的图灵机编码步骤和号码指定是
相当合理和简单的，但是在一台实际的普适图灵机的编码中仍然不可避免
地导向这么大的一个数
7。
我曾说过，实际上所有现代通用电脑都是普适图灵机。我并不是说，
这种电脑的逻辑设计必须在根本上和我刚刚给出的普适图灵机的描述非常
相似。其要点可以简述为，首先为任一台普适图灵机提供一段适当的程序
（输入磁带的开始部分）可使它摸拟任何图灵机的行为！在上面的描述中，
程序简单地采取单独的数（数
n）的形式。但是，其他的步骤也是可能的，
图灵原先方案就有许多种变化。事实上，在我自己的描述中，已经有些偏
离图灵的原型。但是对于我们当前目的，这些差别中没有一个是重要的。
希尔伯特问题的不可解性
希尔伯特问题的不可解性
第
n台图灵机作用于数
m时实际上是否会停止的问题。该
问题被称作停机问题。很容易建造一个指令表使该机器对于任何数
m不
停。（例如，正如上面的
n=1或
2或任何别的在所有地方都没有
STOP指令
的情形）。也有许多指令表，不管给予什么数它总停（例如
n=11）；有些
机器对某些数停，但对其他的数不停。人们可以公正地讲，如果一个想象
中的算法永远不停地算下去，则并没有什么用处。那根本不够格被称作算
法。所以一个重要的问题是，决定
T
n应用在
m时是否真正地给出答案！如
果它不能（也就是该计算不停止），则就把它写成
Tn(m)=□。
（在这记号中还包括了如下情形，即图灵机在某一阶段由于它找不到合适
的告诉其下一步要做什么的指令而遇到麻烦，正如上面考虑的伪品机器
T
4
和
T
7。还有不幸得很，我们粗看起来似乎成功的机器
T
3现在也必须被归于
伪品：T
3(m)=□，这是因为
T
3作用的结果总是空白带，而为使计算的结果
可赋予一个数，在输出上至少有一个
1！然而，由于机器
T
11产生了单独的
1，所以它是合法的。这一输出是编号为
0的磁带，所以对于一切
m，我们
都有
T
11(m)=0。）
能够决定图灵机何时停止是数学中的一个重要问题。例如，考虑方程：
(x+1)w+3+(y+1)w+3=(z+1)w+3。
（如果专门的数学方程使你忧虑，不要退缩！这一方程只不过是作为一个
例子，没有必要详细地理解它。）这一特殊的方程和数学中著名的或许是
最著名的未解决的问题相关。该问题是：存在任何满足这方程的自然数集
合
w，x，y，z吗？这个著名的称作“费马最后定理”的陈述被伟大的十七
世纪法国数学家皮埃尔·德·费马(1601—1665)写在丢番都的《代数》一
书空白的地方。费马宣布这方程永远不能被满足①8。虽然费马以律师作为
职业（并且是笛卡尔的同时代人），他却是那个时代最优秀的数学家。他
宣称得到了这一断言的“真正美妙的证明”，但那里的空白太小写不下。
可惜迄今为止既没有人能够重新证明之，也没有人能找到任何和费马断言
相反的例子①！
很清楚，在给定了四个数(w,x,y,z)后，决定该方程是否成立是计算的
①记住我说的自然数是指
0，1，2，3，4，5，6，.。我写成“
x+1”和“
w+3”等等，而不写成费马断言的
更熟知的形式(xw+yw=xw，x，y，z＞0，w＞2)的原因是，我们允许
x,w等等为从零开始的所有自然数。
①普林斯顿大学的英籍数学家安德鲁·怀尔斯在
1993年
6月
23日宣布证明了费马最后定理（译者）。
事体。这样，我们可以想象让一台电脑的算法一个接一个地跑过所有的四
数组，直到方程被满足时才停下。（我们已经看到，存在于一根单独磁带
上，把数的有限集合以一种可计算方式编码成为一个单独的数的方法。这
样，我们只要跟随着这些单独的数的自然顺序就能“跑遍”所有的四数组。）
如果我们能够建立这个算法不停的事实，则我们就有了费马断言的证明。
事体。这样，我们可以想象让一台电脑的算法一个接一个地跑过所有的四
数组，直到方程被满足时才停下。（我们已经看到，存在于一根单独磁带
上，把数的有限集合以一种可计算方式编码成为一个单独的数的方法。这
样，我们只要跟随着这些单独的数的自然顺序就能“跑遍”所有的四数组。）
如果我们能够建立这个算法不停的事实，则我们就有了费马断言的证明。
我们能够决定这台图灵机是否会停，我们也就有了决定哥德巴赫猜想真理
ìí.
述。“哥德巴赫猜想”即是这样的一个例子，它断言比
2大的任何偶数都
是两个质数之和②。决定给定的自然数是否为质数是一个算法步骤，由于人
们只需要检验它是否能被比它小的数整除，所以这只是有限计算的事体。
我们可以设计跑遍所有偶数
6，8，10，12，14，.的一台图灵机，尝试把
它们分成奇数的对的所有不同的方法：
6=3+3，8=3+5，10=3+7=5+5，12=5+7，
14=3+11=7+7，.
对于这样的每一个偶数检验并确认其能分成都为质数的某一对数。（我们
显然不需要去检验除了
2+2之外的偶的被加数对，由于除了
2之外所有质
数都是奇的。）只有当我们的机器达到一个由它分成的所有的任何一对数
都不是质数对的偶数为止才停止。我们在这种情形就得到了哥德巴赫猜想
的反例，也就是说一个（比
2大的）偶数不是两个质数之和。这样，如果
性的方法。
