12→1100，等等
正如在标准的 （十进位）记数中一样，这里最右边的数字代表“个位”，
但是紧在它前面的位数代表 “二”而不是“十”。再前面的位数代表“四”
而不是 “百”，更前面的是“八”而不是“千”等等。随着我们向左移动，
每一接续的位数的值为接续的二的幂：1，2，4 （=2×2），8 （=2×2×2），
16 （=2×2×2×2），32 （=2×2×2×2×2）等等。（为了将来的其他目的，
我们有时发现用二和十以外的基来表示自然数是有助的：例如基数为三，
3
则十进位数64就可被写成2101，现在每一位数都为三的幂：64= （2×3 ）
2
+3 +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
··
··
··
··
----------------------- Page 50-----------------------
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 上面。图灵机可以很
容易地写下执行该算法的程序。作为一个练习，某些勤奋的读者也许介意
----------------------- Page 51-----------------------
去验证下面的一台图灵机 （我将称它为EUC）的显明的描述，当应用到一
对由０分隔的一进位数时，的确会执行欧几里德算法：
0 ０→0 ０R，0 １→1１L，1０→10１R，1１→1１L，10０→1010０R，10１
→11０R，11０→100０R，11１→11１R，100０→100０R，100１→101０R，
101０→111０L，101１→110１L，110０→110０L，110１→1１L，111０→
111０L，111１→1000１L，1000０→1001０L，1000１→1000１L，1001０
→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）在实际上完成所预想的，牵涉到许
多微妙之处，而且解释本身比机器更复杂，这是电脑程序的通常特征！（为
了完全理解一个算法步骤为何能做到所预想的，牵涉到洞察。 “洞察”本
----------------------- Page 52-----------------------
身是算法的吗？这是一个对我们以后颇为重要的问题。）我不想在这里为
EUC或UN×2提供解释。真正做过检验的读者会发现，为了在所需的方案
中把事情表达得更精密一些，我自作主张地对欧几里德算法作了一些不重
要的变通。EUC 的描述仍然有些复杂，对于11种不同的内态包含有 22 条
基本指令，大部分复杂性是纯粹组织形式的。例如，可以看到在22 条指令
中，只有三条真正涉及到在磁带上改变记号！ （甚至对于UN×2 用了 12
条指令，其中只有一半涉及到改变记号。）
----------------------- Page 53-----------------------
数据的二进位码
用一进位系统表示大数极端无效率。正如早先描述的，我们将相应地
用二进位计数系统。然而，不能直接地把磁带当作二进位数来读。如果这
样做的话，就没有办法告知一个数的二进位表示何时结束，以及无限个０
的序列是否代表右端开始的空白。我们需要某种终结一个数的二进位描述
的记号。此外，我们还经常要输进几个数，正如欧几里德算法需要一对数
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
在二进位记号中这是
１０１，１１０１，０，１，１，１００，
它可用扩展 （也就是和上面收缩相反）的步骤在磁带上编码成…００００
----------------------- Page 54-----------------------
１００１０１１０１０１００１０１１００１１０１０１１０１０１１０
１０００１１０００…为了直截了当地得到这个码，我们可在原先的二进
位数序列上作如下代换：
０→０
１→１０
，→１１０
然后在两端加上无限个０。如果我们把它列出，就能更清楚地看出，如何
把这个应用到上面的磁带上：
００００１００１０１１０１０１００１０１１００１１０１０１１
０１０１１０１０００１１０００
我将把这种数 （的集合）的记号称为扩展二进位记号。 （这样，例如13
的扩展二进位形式为１０１００１０）
关于这种编码还有最后一点必须提及。这只不过是个技巧，但是为了
3
完备起见是需要的 。在自然数的二进位 （或十进位）表示中处于表式最
左端的0 是不 “算”的，它通常可被略去，这里有些多余。例如００１１
００１０和１１００１０是两个相同的二进位数（而0050 和50 为相同的
十进位数）。这一多余可适合于数0 本身，它也可写成000 或00。一个空
白的空间的确也应该逻辑地表示0！在通常的记号下这会导致巨大的混
淆，但是它和上面刚描述的记号可相安无事。这样，在两个逗号之间的0
可只写成两个连在一起的逗号 （，，），它在磁带上被编码成两对由单独
的０隔开的１１：
…００１１０１１００…
这样，上面的六个数的集合也可用二进位记号写成
１０１，１１０１，，１，１，１００，
而且在磁带上可以扩展的二进位方式编码成
…００００１００１０１１０１０１００１０１１０１１０１０１１０１
０１１０１０００１１０００…（有一个０已从我们以前的序列中略去）。
现在我们可以考虑让一台图灵机，譬如讲欧几里德算法，把它应用到
以扩展二进位记号写出的一对数上。例如，这一对数是我们早先考虑的6，
8，不用以前用的
…０００００００００００１１１１１１０１１１１１１１１０００
００…
而考虑6和8 的二进位表示，也就是分别为110和 1000。这一对为6，8，
在二进位记号也就是１１０，１０００扩展后在磁带上编码成
…０００００１０１００１１０１００００１１００００００…
对于这一对特殊的数，并没有比一进位形式更紧凑。然而，譬如说我们取
（十进位数）1583169和8610。在二进位记号中它们是
１１０００００１０１００００１０００００１，１００００１１０
----------------------- Page 55-----------------------
１０００１０，
这样，我们在磁带上把这一对编码成
…００１０１００００００１００１０００００１００００００１０
１１０１０００００１０１００１００００１００１１０…
只要用一行就可将其全部写出，而如果用一进位记号的话，表示“1583169，
8610”的磁带用这一整本书都写不下。
当数用扩展二进位记号表示时，一台执行欧几里德算法的图灵机，如
果需要的话，可以简单地把适当的一对在一进位和扩展二进位之间互相翻
译的子程序算法接到EUC 上去而得到。然而，由于一进位计数系统的无效
率仍在 “内部”存在，并且在仪器的迟缓以及需要大量的外部“粗纸”（它
是磁带的右手部分）方面表现出来，实际上这是极其无效率的。可以给出
全部用扩展二进位运算的、更有效率的、欧几里德算法的图灵机，但是它
在这里对我们并无特别启发之处。
相反地，为了阐明如何使一台图灵机能对扩展二进位数运算，让我们
尝试某种比欧几里德算法简单得多的东西，即是对一个自然数加一的过
程。这可由 （我称之为XN+1 的）图灵机来执行：
0 ０→0 ０R，0 １→1１R，1０→0 ０R，1１→10１R，
