SEP：可计算性与复杂性（一） (5-4)

与内存(随机存取存储器，random access memory)相比，存储磁带的线性性质是一个对运算速度的限制，但并没有限制其运算力：图灵机可以寻找到任意存储位置，即，磁带单元格，只是这可能会花些时间，因为其必须一步步地沿着磁带移动其探头。

图灵机的美妙之处在于，这是一个极其简单的模型，然而运算力却十分强大。图灵机具有潜无穷的工作空间，使其能够处理任意大的输入，比如，两个大数相乘，然而其每一步只能读取或者记录有限量的信息，即，一个符号。甚至在图灵机被证明，与其他关于计算的数学模型等价之前，以及丘奇图灵论题被表述之前，图灵就令人信服地表明了，他的机器和其他任何可能的计算设备一样强大。

2.1 Universal Machines

每一台图灵机都可以被唯一地描述为其转换表：对每一个状态q，以及每一个符号，σ，δ(q，σ)是一个新状态，新符号，以及探头位移。这些转换表可以被记作有限的符号串，以给出了每一台图灵机的完整指令集。进一步，这些符号串可以被如下地以词典顺序列出，M₁，M₂，M₃ . . .，在这里Mᵢ是转换表，即，完整指令集，对每个图灵机编号i，转换表Mᵢ就是图灵机的程序，或者更准确地说是iᵗʰ的程序。

图灵展示了他可以构造一台*通用的(universal)*图灵机，U，其可以运行任何其他图灵机的程序。更明确地，对于任意i，以及任意输入w，U在输入i与w时，将完全按照M_i在输入w时那样运行，用符号表示就是，

U(i，ω)＝Mᵢ(ω)

图灵对通用机的构造给我们了一个关于计算的最基础性的启示，一台机器就能运行其他任何程序。无论我们需要在未来执行什么样的计算任务，仅需一台机器就能够执行所有它们。图灵的这个见解使得搭建与销售计算机成为可能。一台计算机就能运行所有程序。我们不需要在要解决新任务的时候每次都买台新计算机。当然，在个人电脑的时代，这个事实已是个基本假定，以至于我们很难退后一步去重新审视它。

2.2 The Halting Problem

因为其被设计出来去体现所有可能的计算，图灵机有一个不可避免的缺陷，图灵机进行某些输入后将永远不会停机。其不能停机的某些原因十分愚蠢，比如我们可以对图灵机做出一个错误的编程，致使其进入一个紧凑循环(tight loop)，例如，在状态17中若读取到1，其可能会进入状态17并写下1，然后将探头移到0。不那么傻的是，我们可以到达一个空白符，其右边也全是空白符，同时也保持一直处在同一个状态——向右移动一格寻找一个“1”。这两个不能停机的例子，都可以被一个像样的编译器简单地检测到与修正。然而，考虑图灵机Mғ，输入“0”并系统性地搜索费马大定理(Fermat's last theorem)的第一个反例，当找到它时便输出这个反例并停机。而这直到最近安德鲁·怀尔斯(Andrew Wiles)证明了费马大定理之前，所有数学家工作了超过三个世纪都没能决定，Mғ输入0后，最终是否停机。现在我们知道了它永远不会停。

2.3 Computable Functions and Enumerability

既然图灵机在一定输入上可能不会停机，那么我们对于如何通过图灵机来定义可计算函数上便必须十分小心。让自然数N为一个集合{0，1，2，. . .}，并让我们把图灵机考虑作一个从N到N的部分函数

设M为一台图灵机，n为一个自然数，我们称M的磁带包含数字n，当，M的磁带以一个数的二进制表达开始(没有不必要的前导0)，而在这之后全是空白。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。