按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
各种基本的算术运算，诸如把两个数加到一起，或把它们相乘，或求一个数的到另一个数的方次。显明提供其结果为一对自然数的运算，譬如带有余数的除法，或者其结果为任意大数目的数的有限集合。此外，可以这样地建造图灵机，即预先没有必要指定它要做何种运算，其运算的指令由磁带提供。需要实行的特定运算也许在某一阶段依赖于该机器在某个更早阶段的需要进行的某个计算的结果。（“如果那个计算的结果比某数大，则做这个；否则就做那个。”）
一旦人们理解到，他可制造实现算术或简单的逻辑运算的图灵机，则很容易想象如何使之进行具有算法性质的更复杂的任务。在他们捣弄了好一阵之后，很容易坚信，这类机器的确能实行不管什么样的机械运算！在数学上，可以很合情合理地把机械运算定义为可被这样的一台机器所执行的运算。数学家用名词“算法”以及形容词“可计算的”、“递归的”和“有效的”来表示能由这类理论机器――图灵机实行的机械运算。一个步骤只要是足够清楚并且机械的，则可合理地相信能找到一台执行它的图灵机。
这正是我们（也就是图灵）引进图灵机概念本身的初步讨论的全部要点。
另一方面，人们仍会感到，这些机器的设计不必这么局限。初看起来，只允许仪器在一个时刻读一个二进位位数（０或１），并且一次沿着一个单独的一维磁带只移动一格似乎是限制。为什么不允许大数目或相互联结的阅读机一下子跑过四条或五条甚至一千条分开的磁带呢？为什么不允许０和１的方格的整个平面（或者甚至一个三维的阵列），而坚持只用一维的磁带呢？为什么不允许从某种更复杂的计数系统或字母来的其他符号呢？事实上，虽然这些改变中的一些会对运算的经济性造成一定程度的不同（正如允许用多于一条的磁带一定会是这种情形那样），但是所有这一切都不会对我们在原则上要得到的东西造成丝毫的影响。即使我们在所有这些方面一下子推广该定义，这种归于“算法”的名下（或“计算”、“有效步骤”或“递归运算”）所实现的运算种类刚好和推广以前的完全相同！
我们可以看到，没有必要有多余一条的磁带。只要该仪器需要时总能在给定的磁带不断地找到新的空白。为此，也许必须不断地把数据从磁带的一处往另一处调度。这也许是“低效率的”，但是它不限制在原则上可以得到的极限4。类似地，利用多于一台并行动作的图灵机――这在近年由于和想更接近地仿照人脑试图相关联而变得很时髦――不能在原则上得到任何新东西（虽然在某种情形下可改善动作的速度）。拥有两台分开的、不直接相互联络的仪器并不比两台相互联络的得到更多，而且如果它们联络，则实际上只不过是一台单独的仪器！关于图灵的对于一维磁带的限制能说些什么呢？如果我们认为该磁带代表“环境”，也许宁愿把它当作一个平面或许一个三维空间，而不当作一维磁带。一个平面似乎比一维磁带更接近于一个“流程图”（正如在上面对欧几里德算法运算的描述） 所需要的①。 然而， 在原则上没有困难以 “一维的”形式（也就是利用流程图的通常术语来描述）写出流程图的运行。在二维平面上显示只是为了我们的便利和容易理解，它对原则上能得到的并没造成什么影响。人们总能把一个二维平面上甚至三维空间上的一个记号或对象的地址，直截了当地在一维磁带上编码。（事实上，使用一个二维平面完全等效于用两根磁带。这两根磁带提供为在二维平面上指明一点所需的两个“座标”；正如三根磁带可作为一个三维空间的一点的“座标”
一样。）这一维的编码再次可能为“低效率的”，但是它在原则上不限制我们的目标。尽管所有这一切，我们仍然可心询问，图灵机的概念是否真的和我们希望叫做“机械的”每一逻辑或数学运算相统一。在图灵写他的开创性文章的时候，这一点比今天模糊得多，所以他觉得有必要把情形解释得更清楚一些。图灵的严密论证从以下事实得到了额外的支持，这就是美国逻辑学家阿伦佐？撤屈（在S。C。克利涅的协助下）完全独立地（并实际上稍早一些）提出了一种方案，也是旨在解决希尔伯特的判决问题的拉姆达计算。尽管它不如图灵的那么明显地为一种完全广泛的机械的方案，但在数学结构上的极端经济性方面有些优点。（我将在本章的结尾描述撤屈的杰出的计算。） 还存在其他一些解决希尔伯特问题的和图灵相独立的设想 （见甘迪1988），尤其是波兰――美国逻辑学家爱弥尔？波斯特的设想（比图灵稍晚些，但其思想和图灵比和撤屈更相像许多）。所有这些方案很快就被证明是完全等效的。 这就给现在称作撤屈――图灵主题的观点增加了许多份量，即图灵机（或等效的）概念实际在数学上定义了我们认为是算法（或有效、或递归、或机械的）步骤的东西。现在，高速电脑已变成我们生活中如此熟悉的部分，很少人似乎觉得有必要去问这些主题的原始形式。相反地，已有不少人转去注意真正的物理系统（假定包括人脑）――精确服从物理定律的东西――是否能够实行比图灵机更多、更少或刚好一样多的逻辑和数学运算。我本人是非常喜欢撤屈――图灵主题的原先的数学形式。另一方面，它和实在物理系统的行为的关系是我们以后在本书主要关注的另外一个单独的问题。① 正如这里所描述的，这一流程图本身实际上是“仪器”的一部分，而不是外部环境的“磁带”。我们在磁带上表示的正是实际的数A，B，A…B 等等。然而，我们还要以一个线性的一维形式来表达该仪器的详细指明。正如我们将要看到的，和普适图灵机相关的，在一台特殊仪器的详细指明和对该仪器可能的“资料”
（或“程序”）的详细指明之间有个密切关系。所以，使这两者都处于一维形式是方便的。不同于自然数的数我们在上述的讨论中考虑了自然数的运算，并且注意到了这一显著的事实，即尽管每台图灵机只有固定的有限数目的不同内态，它却可能处理任意大小的自然数。然而，人们经常需要使用比这更复杂的其他种类的数，诸如负数、分数或无理数。图灵机可以容易地处理负数和分数（例如像…
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）。那些不能的（实际上是绝大多数！）是叫作不可计算的。我们将在后面的章节中回到这件事体及有关的问题上来。按照物理理论，用可计算的数学结构能否足够地描述实在的物理对象（也就是人脑），是我们要关心的问题。
一般地讲，可计算性是数学中的一个重要问题。人们不应该只将其当成只适合于这类数的事体。人们可有直接作用于诸如代数或三角的数学公式上的图灵机，或可进行微积分的形式运算的图灵机。人们所需的一切是某种准确地把所有涉及的数学符号编码成0和1序列的形式，然后再利用图灵机的概念。这毕竟是图灵在着手解决判决问题时心里所想的，即寻求回答具有一般性质的数学问题的算法步骤。我们将很快地回到这上面来。普适图灵机我还未描述普适图灵机的概念。虽然其细节是复杂的，但是它背后的原则并不十分复杂。它的基本思想是把任意一台图灵机T的指令的表编码成在磁带上表示成0和1的串。然后这段磁带被当作某一台特殊的被称作普适图灵机U的输入的开始部分，接着这台机器正如T所要进行的那样，作用于输入的余下部分。普适图灵机是万有的模仿者。“磁带”的开