10０→11０L，10１→10１R，11０→0 １STOP，11１→100０L，100０→101１L，100１→100１L，101０→110０R，101１→10１R，110１→111１R，111０→11１R，111１→111０R，某些勤奋的读者可把它应用到，譬如讲数 167上去，以再次验证这一台图灵机在实际上做到了所预想的。这一个数的二进位表示可由下面的磁带给出：…００００１００１０００１０１０１０１１０００…为了把一加到这个二进位数上，我们简单地找到最后的那个0，并把它改成 1，然而用0 来取代所有跟在后面的 1。例如167+1=168在二进位记号下写成１０１００１１１+ １= １０１０１０００.这样，我们的 “加一”图灵机应把前面的磁带用…００００１００１００１００００１１０００００…来取代，它的确做到了这一点。我们注意到，甚至这种简单加一的非常基本的运算在用这种记号时都会显得有些复杂，它使用了十五条指令和八种不同的内态！由于在一进位系统中 “加一”只是把1 的串再延长一个而已，事情当然是简单得多。所以我们的机器UN+1 更为基本，这一点也不奇怪。然而，对于非常大的数，由于所需的磁带非同寻常地长，UN+1 就会极慢。而用更紧凑的扩展二进位记号运算的更复杂的机器XN+1 就会更好。作为旁白，我愿意指出对于扩展二进位比一进位图灵机显得更简单的----------------------- Page 56-----------------------一个运算，这就是乘二。在这里由0 ０→0 ０R，0 １→1０R，1０→0 １R，1１→10０R，10０→11１R，11０→0 １STOP，给出的图灵机XN×2 能在扩展的二进位上实现这个运算，而前面描述的相应于一进位的机器 UN×2 就要复杂得多！我们从这里得到了，关于图灵机在非常基础水平上可做到的一些事情的概念。正如预料得到的，当进行某些复杂的运算时，它们会变得极为复杂。这种仪器的终极能力是什么呢？让我们在下面讨论这一个问题。----------------------- Page 57-----------------------撤屈——图灵主题人们一旦对建造简单的图灵机稍有一些熟悉，下面这些事实就很容易使他们感到满意。特殊的图灵机的确能执行各种基本的算术运算，诸如把两个数加到一起，或把它们相乘，或求一个数的到另一个数的方次。显明提供其结果为一对自然数的运算，譬如带有余数的除法，或者其结果为任意大数目的数的有限集合。此外，可以这样地建造图灵机，即预先没有必要指定它要做何种运算，其运算的指令由磁带提供。需要实行的特定运算也许在某一阶段依赖于该机器在某个更早阶段的需要进行的某个计算的结果。 （“如果那个计算的结果比某数大，则做这个；否则就做那个。”）一旦人们理解到，他可制造实现算术或简单的逻辑运算的图灵机，则很容易想象如何使之进行具有算法性质的更复杂的任务。在他们捣弄了好一阵之后，很容易坚信，这类机器的确能实行不管什么样的机械运算！在数学上，可以很合情合理地把机械运算定义为可被这样的一台机器所执行的运算。数学家用名词 “算法”以及形容词“可计算的”、“递归的”和“有效的”来表示能由这类理论机器——图灵机实行的机械运算。一个步骤只要是足够清楚并且机械的，则可合理地相信能找到一台执行它的图灵机。这正是我们 （也就是图灵）引进图灵机概念本身的初步讨论的全部要点。另一方面，人们仍会感到，这些机器的设计不必这么局限。初看起来，只允许仪器在一个时刻读一个二进位位数 （０或１），并且一次沿着一个单独的一维磁带只移动一格似乎是限制。为什么不允许大数目或相互联结的阅读机一下子跑过四条或五条甚至一千条分开的磁带呢？为什么不允许０和１的方格的整个平面（或者甚至一个三维的阵列），而坚持只用一维的磁带呢？为什么不允许从某种更复杂的计数系统或字母来的其他符号呢？事实上，虽然这些改变中的一些会对运算的经济性造成一定程度的不同 （正如允许用多于一条的磁带一定会是这种情形那样），但是所有这一切都不会对我们在原则上要得到的东西造成丝毫的影响。即使我们在所有这些方面一下子推广该定义，这种归于 “算法”的名下（或“计算”、“有效步骤”或 “递归运算”）所实现的运算种类刚好和推广以前的完全相同！我们可以看到，没有必要有多余一条的磁带。只要该仪器需要时总能在给定的磁带不断地找到新的空白。为此，也许必须不断地把数据从磁带的一处往另一处调度。这也许是 “低效率的”，但是它不限制在原则上可4以得到的极限 。类似地，利用多于一台并行动作的图灵机——这在近年由于和想更接近地仿照人脑试图相关联而变得很时髦——不能在原则上得到任何新东西 （虽然在某种情形下可改善动作的速度）。拥有两台分开的、不直接相互联络的仪器并不比两台相互联络的得到更多，而且如果它们联络，则实际上只不过是一台单独的仪器！----------------------- Page 58-----------------------关于图灵的对于一维磁带的限制能说些什么呢？如果我们认为该磁带代表 “环境”，也许宁愿把它当作一个平面或许一个三维空间，而不当作一维磁带。一个平面似乎比一维磁带更接近于一个 “流程图”（正如在上①面对欧几里德算法运算的描述）所需要的 。然而，在原则上没有困难以“一维的”形式 （也就是利用流程图的通常术语来描述）写出流程图的运行。在二维平面上显示只是为了我们的便利和容易理解，它对原则上能得到的并没造成什么影响。人们总能把一个二维平面上甚至三维空间上的一个记号或对象的地址，直截了当地在一维磁带上编码。 （事实上，使用一个二维平面完全等效于用两根磁带。这两根磁带提供为在二维平面上指明一点所需的两个 “座标”；正如三根磁带可作为一个三维空间的一点的“座标”一样。）这一维的编码再次可能为 “低效率的”，但是它在原则上不限制我们的目标。尽管所有这一切，我们仍然可心询问，图灵机的概念是否真的和我们希望叫做 “机械的”每一逻辑或数学运算相统一。在图灵写他的开创性文章的时候，这一点比今天模糊得多，所以他觉得有必要把情形解释得更清楚一些。图灵的严密论证从以下事实得到了额外的支持，这就是美国逻辑学家阿伦佐·撤屈 （在S.C.克利涅的协助下）完全独立地 （并实际上稍早一些）提出了一种方案，也是旨在解决希尔伯特的判决问题的拉姆达计算。尽管它不如图灵的那么明显地为一种完全广泛的机械的方案，但在数学结构上的极端经济性方面有些优点。 （我将在本章的结尾描述撤屈的杰出的计算。）还存在其他一些解决希尔伯特问题的和图灵相独立的设想（见甘迪 1988），尤其是波兰——美国逻辑学家爱弥尔·波斯特的设想 （比图灵稍晚些，但其思想和图灵比和撤屈更相像许多）。所有这些方案很快就被证明是完全等效的。这就给现在称作撤屈——图灵主题的观点增加了许多份量，即图灵机 （或等效的）概念实际在数学上定义了我们认为是算法（或有效、或递归、或机械的）步骤的东西。现在，高速电脑已变成我们生活中如此熟悉的部分，很少人似乎觉得有必要去问这些主题的原始形式。相反地，已有不少人转去注意真正的物理系统 （假定包括人脑）——精确服从物理定律的东西——是否能够实行比图灵机更多、更少或刚好一样多的逻辑和数学运算。我本人是非常喜欢撤屈——图灵主题的原先的数学形式。另一方面，它和实在物理系统的行为的关系是我们以后在本书主要关注的另外一个单独的问题。① 正如这里所描述的，这一流程图本身实际上是 “仪器”的一部分，而不是外部环境的“磁带”。我们在磁带上表示的正是实际的数A ，B，A-B 等等。然而，我们还要以一个线性的一维形式来表达该仪器的详细指明。正如我们将要看到的，和普适图灵机相关的，在一台特殊仪器的详细指明和对该仪器可能的 “资料”（或“程序”）的详细指明之间有个密切关系。所以，使这两者都处于一维形式是方便的。----------------------- Page 59-----------------------不同于自然数的数我们在上述的讨论中考虑了自然数的运算，并且注意到了这一显著的事实，即尽管每台图灵机只有固定的有限数目的不同内态，它却可能处理任意大小的自然数。然而，人们经常需要使用比这更复杂的其他种类的数，诸如负数、分数或无理数。图灵机可以容易地处理负数和分数 （例如像-597/26），而且我们可取任意大的分母和分子。我们所要做的全部是对“-”和“/”作适当的编码。这可容易地利用早先描述的扩展二进位记号做到（例如， “3”表示 “-”以及 “4”表示 “/”，它们分别在扩展二进位记号中编码成 1110和 11110）。人们就是这样地按照自然数的有限集合来处理负数和分数的。这样，就可计算性的一般问题而言，它们没有告诉我们什么新的东西。类似地，由于长度不受限制的有限小数表式仅仅是分数的特殊情形，它们并没给我们带来什么新问题。例如，无理数π的由3.14159265 给出的有限小数近似，简单地就是分数314159265/100000000。然而，无限小数表式，譬如完全无限展开π=3.14159265358979…出现了一定的困难。严格地讲，无论是图灵机的输入或者输出都不是无限小数。人们也许会想到，我们可以找到一台图灵机，在其输出磁带上产生由π的小数展开的、所有的一个接一个位数3，1，4，1，5，9，…。我们就简单地让机器一直开下去好了。但这对于一台图灵机来讲，是不允许的。我们必须等待机器停了以后 （铃声响过！）才允许去检查输出。只要机器还没有到达停止命令，其输出就可能要遭受到改变，所以不能对它信任。另一方面，在它到达停止时，其输出必须是有限的。然而，存在一种合法地使图灵机以与此非常类似的方法，一个位数跟着另一个位数产生位数的步骤。如果我们希望产生一个数，譬如讲π的无限小数展开，我们可以让一台图灵机作用于0 上以产生整数部分了；然后使机器作用到 1上，产生第一小数位 1；然后使其作用于2 上，产生第二小数位4；然后作用于3 上，产生 1，这样不断地下去。事实上，一定存在在这个意义上产生π的全部小数展开的图灵机，尽管要把它明显地造出来颇费一点周折。类似的评论也适用于许多其他无理数，譬如 2=1.414213562…。然而，正如在下一章将要看到的，人们发现有些无理数（非常引人注目地）根本不能由任何图灵机产生。能以这种方式产生的数叫作可计算的 （图灵1937）。那些不能的 （实际上是绝大多数！）是叫作不可计算的。我们将在后面的章节中回到这件事体及有关的问题上来。按照物理理论，用可计算的数学结构能否足够地描述实在的物理对象 （也就是人脑），是我们要关心的问题。一般地讲，可计算性是数学中的一个重要问题。人们不应该只将其当----------------------- Page 60-----------------------成只适合于这类数的事体。人们可有直接作用于诸如代数或三角的数学公式上的图灵机，或可进行微积分的形式运算的图灵机。人们所需的一切是某种准确地把所有涉及的数学符号编码成0 和 1序列的形式，然后再利用图灵机的概念。这毕竟是图灵在着手解决判决问题时心里所想的，即寻求回答具有一般性质的数学问题的算法步骤。我们将很快地回到这上面来。----------------------- Page 61-----------------------普适图灵机我还未描述普适图灵机的概念。虽然其细节是复杂的，但是它背后的原则并不十分复杂。它的基本思想是把任意一台图灵机T 的指令的表编码成在磁带上表示成0 和 1 的串。然后这段磁带被当作某一台特殊的被称作普适图灵机U 的输入的开始部分，接着这台机器正如T所要进行的那样，作用于输入的余下部分。普适图灵机是万有的模仿者。 “磁带”的开始部分赋予该普适机器U 需要用以准确模拟任何给定机器T 的全部信息！为了了解这是如何进行的，我们首先需要一种给图灵机编号的系统方式。考虑定义某个特殊的，譬如讲在前面描述的图灵机的一个指令表。我们必须按照某种准确的方案把这表编码成0 和 1 的串。我们可借助于以前采用的 “收缩”步骤来办到。因为，如果我们用数2，3，4，5和 6来分别代表符号 R、L、STOP、箭头 （→）以及逗点，那么我们就可以用１１０、１１１０、１１１１０、１１１１１０以及１１１１１１０的收缩把它们编码。这样，出现在该表中的这些符号实际的串可以采用分别被编码成０和１０的位数0 和１。由于在该图灵机的表中，在二进位计数的结尾大写的数的位置足以把大写的０和１从其他小写的阿拉伯数字中区分开来，所以我们不需要用不同的记号。这样，110１将被读成二进位数1101，而在磁带上被编码成１０１００１０。特别是，0 ０读作00，它可毫不含糊地被编码成０，或者作为被完全省略的符号。实际上我们可以不必对任何箭头或任何在它紧前头的符号进行编码，而依靠指令的数字顺序去标明哪些符号必须是什么。尽管在采用这个步骤时，在必要之处要提供一些额外的“哑”指令，以保证在这个顺序中没有缝隙。这样的做法具有相当好的经济性。 （例如，图灵机XN+1 没有告诉我们对 110０要做什么的命令，这是因为这条指令在机器运行时从不发生，所以我们应该插入一条“哑”指令，譬如讲 110０→0 ０R，它可合并到表中而不改变任何东西。类似地，我们应该把 10１→0 ０R插入到XN×2 中去。）若没有这些“哑的”，表中后面的指令的编码就会被糟蹋了。因为在结尾处的符号L或R 足以把一条指令和另一条隔开，所以我们在每一指令中实际不需要逗号。因此，我们采用下面的编码：０表示0 或０，１０表示 1或１，１１０表示R，１１１０表示L，１１１１０表示stop。作为一个例子，让我们为图灵机XN+1 编码 （插入指令110０→0 ０R）。在去掉箭头和在它们紧前面的位数以及逗号之后，我们得到0 ０R 1 １R 0 ０R 10 １R 11 ０L 10 １R 0 １STOP100０L 101 １L 100 １L110 ０R10 １R0 ０R111 １R11１R 111 ０R为了和早先说的相一致，我们可以去掉每一个００，并把每一个01 简单地----------------------- Page 62-----------------------用 1来取代，这样得到R1 １RR10 １R11 ０L10 １R １STOP100 ０L101 １L100 １L110 ０R10 １RR111 １R11 １R111 ０R如下是在磁带上的相应的码：１１０１０１０１１０１１０１００１０１１０１０１００１１１０１００１０１１０１０１１１１０１００００１１１０１００１０１０１１１０１０００１０１１１０１０１０００１１０１００１０１１０１１０１０１０１０１０１１０１０１０１０１１０１０１０１００１１０我们总是可以把开始的１１０ （以及它之前的无限的空白磁带）删去。由于它表示0 ０R，这代表开头的指令0 ０→0 ０R。而我已隐含地把它当作所有图灵机共有的。这样仪器可从磁带记号左边任意远的地方向右跑到第一个记号为止。而且，由于所有图灵机都应该把它们的描述用最后的１１０