n个方格或者一次可移动
k个方格的仪器。k方格的移动可由一个方格的
k
次移动来积累，而存储一个方格上的
n种记号的行为正和一次读
n个方格
一样。
这样的一台仪器在细节上可做什么呢？什么是我们描述成“机械的”
东西作用的最一般方式呢？我们记得该仪器的内态在数目上是有限的。除
了这种有限性之外，我们所需要知道的一切是该仪器的行为完全被其内态
①事实上，图灵在他原先的描述中允许磁带有更复杂的记号，但这并没有什么本质上的差别。更复杂的记
号总能被细分成记号和空白的序列。我将随意地对他原先的详细说明作各种不重要的变通。
和输入所确定。我们已把输入简化成只是两个符号“0”或“1”之中的一
个。仪器的初态和这一输入一给定，它就完全确定地运行；它把自己的内
态改变成某种其他（或可能是同样的）内态，它用同样的或不同的符号.. 0
或.. 1来取代它刚读过的.. 0或.. 1；它向右或向左移动一个方格；最后它决定
是继续还是终止计算并停机。
和输入所确定。我们已把输入简化成只是两个符号“0”或“1”之中的一
个。仪器的初态和这一输入一给定，它就完全确定地运行；它把自己的内
态改变成某种其他（或可能是同样的）内态，它用同样的或不同的符号.. 0
或.. 1来取代它刚读过的.. 0或.. 1；它向右或向左移动一个方格；最后它决定
是继续还是终止计算并停机。
00→00R
01→131L
10→651R
11→10R
20→01R STOP
21→661L
30→370R
··
··
··
2100→31
··
··
··
2580→00R.STOP
2590→971R
2591→00R.STOP
箭头左边的大写的数字是仪器在阅读过程中磁带上的符号，仪器用右边中
间的大写的数字来取代之。R告诉我们仪器要向右移动一个方格，而.. L告
诉我们它要向左移动一个方格。（如果，正如图灵原先描述的那样，我们
认为磁带而不是仪器在移动，那么我们必须将.. R解释成把磁带向左移动一
个方格，而.. L为向右移动一个方格。）词.. STOP表示计算已经完成而且机
器就要停止。特别是，第二条指令01→131L告诉我们，如果仪器内态为.. 0
而在磁带上读到.. 1，则它应改变到内态.. 13，不改变磁带上的.. 1，并沿着磁
带向左移一格。最后一条指令.. 2591→00 R.STOP告诉我们，如果仪器处于态
259而且在磁带上读到.. 1，那么它应被改变为态.. 0，在磁带上抹去1而产生
0，沿着磁带向右移一格，然后终止计算。
如果我们只用由.. 0到.. 1构成的符号，而不用数字0，1，2，3，4，.. 5..
来为内态编号的话，则就和上述磁带上记号的表示更一致。如果我们有选
择的话，可简单地用一串.. n个.. 1来标号态.. n，但这是低效率的。相反地，
我们使用现在人们很熟悉的二进位记数系统：
我们使用现在人们很熟悉的二进位记数系统：
1→1，
2→10，
3→11，
4→100，
5→101，
6→110，
7→111，
8→1000，
9→1001，
10→1010，
11→1011，
12→1100，等等
正如在标准的（十进位）记数中一样，这里最右边的数字代表“个位”，
但是紧在它前面的位数代表“二”而不是“十”。再前面的位数代表“四”
而不是“百”，更前面的是“八”而不是“千”等等。随着我们向左移动，
每一接续的位数的值为接续的二的幂：1，2，4（=2×2），8（=2×2×2），
16（=2×2×2×2），32（=2×2×2×2×2）等等。（为了将来的其他目的，
我们有时发现用二和十以外的基来表示自然数是有助的：例如基数为三，
则十进位数
64就可被写成
2101，现在每一位数都为三的幂：64=（2×3
3）
+32+1；参阅第四章
122页的脚注。）
对上面图灵机的内态使用这种二进位记号，则原先的指令表便写成：
00→00R
0１→1101１R
1０→1000001１L
1１→1０R
10０→0１STOPR
10１→1000010１L
11０→100101０R
··
··
··
11010010０→11１L
··
··
··
··
100000010１→0０STOP
100000011０→1100001１R
100000011１→0０STOP
我还在上面把
R.STOP简写成
STOP，这是由于可以假定
L.STOP从来不会发
生，以使得计算的最后一步结果，作为答案的部分，总是显示在仪器的左
边。
现在假定我们的仪器处于由二进位序列
1010010代表的特殊内态中，
它处于计算的过程中，第
43页给出了它的磁带，而且我们利用指令
11010010０→11１L；
在磁带上被读的特殊位数（这里是位数“０”）由一个更大写的数字指示，
符号串的左边表示内态。在由上面（我多多少少是随机造出的）部分地指
定的图灵机例子中，读到的“０”会被“1”所取代，而内态变成‘11’，
然后仪器向左移动一格：
该仪器现在已准备好读另一个数字，它又是“０”。根据该表，它现在不
改变这个“０”，但是其内态由“100101”所取代，而且沿着磁带向右移
回一格。现在它读到“１”，而在表的下面某处又有如何进一步取代内态
的指令，告诉它是否改变所读到的数，并向那个方向沿着磁带移动。它就
用这种方式不断继续下去，直到达到
STOP为止，在该处（在它向右再移一
格之后）我们可以想象听到一声铃响，警告机器操作员计算完毕。
我们将假定机器总是从内态“0”开始，而且在阅读机左边的磁带原先
是空白的。所有指令和数据都是在右边输进去。正如早先提到的，被提供
的这些信息总是采用０和１的有限串的形式，后面跟的是空白带（也就是
０）。当机器达到
STOP时，计算的结果就出现在阅读机左边的磁带上。
由于我们希望能把数字数据当作输入的一部分，这样就需要有一种描
述作为输入部分的通常的数（我这里是说自然数
0，1，2，3，4，.）的
方法。一种方法可以是简单地利用一串
n个
1代表数
n（尽管这会给我们
带来和自然数
0相关的困难）：
1→1，2→11，3→111，4→1111，5→11111，等等。
这一初等的记数系统（相当非逻辑地）被称作一进位系统。那么符号
‘O’可用作不同的数之间的分隔手段。这种把数分隔开的手段是重要的，
这是由于许多算法要作用到数的集合，而不仅仅是一个数上面。例如，对
于欧几里德算法，我们的仪器要作用到一对数A和
B上面。图灵机可以很
容易地写下执行该算法的程序。作为一个练习，某些勤奋的读者也许介意
去验证下面的一台图灵机（我将称它为.. EUC）的显明的描述，当应用到一
对由０分隔的一进位数时，的确会执行欧几里德算法：
0０→0０R，0１→1１L，1０→10１R，1１→1１L，10０→1010０R，10１
去验证下面的一台图灵机（我将称它为.. EUC）的显明的描述，当应用到一
对由０分隔的一进位数时，的确会执行欧几里德算法：
0０→0０R，0１→1１L，1０→10１R，1１→1１L，10０→1010０R，10１
→10０R，1001１→1１L，1010０→0０STOP， 1010１→1010１R。
然而，任何读者在进行此事之前，从某种简单得多的东西，譬如图灵机.. UN+1
开始将更为明智：
0０→0０R，0１→1１R，1０→0１STOP，1１→0１R。
它简单地把一加到一个一进位数上。为了检查.. UN+1刚好做到这点，让我们
想象，譬如讲把它应用到代表数.. 4的磁带上去：
.０００００１１１１０００００.。
我们使仪器在开始时从某处向左为一些.. 1。它处于内态０并且读到0。根据
第一条指令，它仍保留为０，向右移动一格，而且停在内态.. 0上，在它遇
到第一个.. 1之前，它不断地这么进行并向右移动。然后第二条指令开始作
用：它把.. 1留下来不变并且再向右移动，但是现在处于内态１上。按照第
四条指令，它停在内态.. 1上，不改变这些.. 1，一直向右移动，一直达到跟
在这些１后面的第一个０为止。第三条指令接着告诉它把那个０改变成
１，向右再移一步（记住.. STOP是表示.. R，STOP），然后停机。这样，另一
个１已经加到这一串１上。正如所要求的，我们例子中的.. 4已经变成了.. 5。
作为更费神的练习，人们可以验证，下面所定义的机器.. UN×2，正如
它所希望的，把一个一进位数加倍：
0０→0０R，0１→1０R，1０→10１L，1１→1１R，10０→11０R10１
→100０R，11０→0１STOP，11１→11１R，100０→101１L，100１→100１R，101０→10１L，101１→101１L。
在.. EUC的情形、为了得到有关的概念，人们可用一些明显的数对譬如
6和.. 8来试验。正如以前一样，阅读机处于态.. 0，并且初始时处在左边，而
现在磁带一开始的记号是这样子的：
.０００００００００００１１１１１１０１１１１１１１１０００００.
在许多步之后，图灵机停止，我们得到了具有如下记号的磁带：
.００００１１００００００００００００.
而阅读机处于这些非零位数的右边。这样，所需的最大公约数正是所需要
的（正确的）2。
要完全解释为何.. EUC（或者.. UN×2）在实际上完成所预想的，牵涉到许
多微妙之处，而且解释本身比机器更复杂，这是电脑程序的通常特征！（为
了完全理解一个算法步骤为何能做到所预想的，牵涉到洞察。“洞察”本
身是算法的吗？这是一个对我们以后颇为重要的问题。）我不想在这里为
EUC或
UN×2提供解释。真正做过检验的读者会发现，为了在所需的方案
中把事情表达得更精密一些，我自作主张地对欧几里德算法作了一些不重
要的变通。EUC的描述仍然有些复杂，对于
11种不同的内态包含有
22条
基本指令，大部分复杂性是纯粹组织形式的。例如，可以看到在
22条指令
中，只有三条真正涉及到在磁带上改变记号！（甚至对于
UN×2用了
12
条指令，其中只有一半涉及到改变记号。）
数据的二进位码
数据的二进位码
数
2那样。问题在于，我们不能把数之间的间隔和作为单独的一个数的二进位
表示中的一部分的０或一串０区分开来。此外，我们或许在输入磁带中包
括所有种类复杂的指令和数。为了克服这些困难，让我们采用一种我称之
为收缩的步骤。按照该步骤，任何一串０或一串１（共有有限个）不是简
单地被当作二进位数来读，而是用一串
0，1，2，3等来取代。其作法是，
第二个序列的每一数字就是在第一个序列中的连续的０之间的１的个数。
例如序列
０１０００１０１１０１０１０１１０１０００１１１０１０１０１１１１００１１０
就可被取代成：
我们现在可以把数
2，3，4，.当作某种记号或指令来读。让我们把
2简
单地当作表示两个数之间间隔的“逗号”，而根据我们的愿望，3，4，5，.
可以代表各种有兴趣的指令或记号，诸如“负号”、“加”、“乘”“到
具有下面号码的位置”，“递归进行前面的运算如下面数目那么多次”等
等。我们现在有了由更高的数分开的各种０和１的串。后者代表写成二进
位的通常的数。这样上面可读成（“逗号”为
2）：
（二进位数１００１）逗号（二进位数
11）逗号..。
使用标准的阿拉伯记号“9”，“3”，“4”，“0”来写相应的二进位１００１，１１，１００，０，我们就得到整个序列：
9，3，4（指令
3）3（指令
4）0，
特别是，这一步骤给了我们一种简单地利用在结尾处逗号终结描述一
个数的手段（并因此把它和在右边的无限长的空白带区分开来）。此外，
它还使我们能对以二进位记号写成０和丨的单独序列的自然数的任何有
限序列编码。让我们看看在一特定情形下这是怎么进行的。例如，考虑序
列
5，13，0，1，1，4
在二进位记号中这是
１０１，１１０１，０，１，１，１００，
它可用扩展（也就是和上面收缩相反）的步骤在磁带上编码成.００００
１００１０１１０１０１００１０１１００１１０１０１１０１０１１０１０００１１０００.为了直截了当地得到这个码，我们可在原先的二进
位数序列上作如下代换：
１００１０１１０１０１００１０１１００１１０１０１１０１０１１０１０００１１０００.为了直截了当地得到这个码，我们可在原先的二进
位数序列上作如下代换：
１→１０
，→１１０
然后在两端加上无限个０。如果我们把它列出，就能更清楚地看出，如何
把这个应用到上面的磁带上：
００００１００１０１１０１０１００１０１１００１１０１０１１０１０１１０１０００１１０００
我将把这种数（的集合）的记号称为扩展二进位记号。（这样，例如
13
的扩展二进位形式为１０１００１０）
关于这种编码还有最后一点必须提及。这只不过是个技巧，但是为了
完备起见是需要的
3。在自然数的二进位（或十进位）表示中处于表式最
左端的
0是不“算”的，它通常可被略去，这里有些多余。例如００１１００１０和１１００１０是两个相同的二进位数（而
0050和
50为相同的
十进位数）。这一多余可适合于数
0本身，它也可写成
000或
00。一个空
白的空间的确也应该逻辑地表示
0！在通常的记号下这会导致巨大的混
淆，但是它和上面刚描述的记号可相安无事。这样，在两个逗号之间的
可只写成两个连在一起的逗号（，，），它在磁带上被编码成两对由单独
的０隔开的１１：
.００１１０１１００.
这样，上面的六个数的集合也可用二进位记号写成
１０１，１１０１，，１，１，１００，
而且在磁带上可以扩展的二进位方式编码成
.００００１００１０１１０１０１００１０１１０１１０１０１１０１０１１０１０００１１０００.（有一个０已从我们以前的序列中略去）。
现在我们可以考虑让一台图灵机，譬如讲欧几里德算法，把它应用到
以扩展二进位记号写出的一对数上。例如，这一对数是我们早先考虑的
6，8，不用以前用的
.０００００００００００１１１１１１０１１１１１１１１０００００.
而考虑
6和
8的二进位表示，也就是分别为
110和
1000。这一对为
