皇帝新脑-第12部分
按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
单独的问题。① 正如这里所描述的，这一流程图本身实际上是“仪器”的一部分，而不是外部环境的“磁带”。我们在磁带上表示的正是实际的数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所要进行的那样，作用于输入的余下部分。普适图灵机是万有的模仿者。“磁带”的开始部分赋予该普适机器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简单地用1来取代，这样得到R1１RR10１R11０L10１R１STOP100０L101１L100１L110０R10１RR111１R11１R111０R如下是在磁带上的相应的码：１１０１０１０１１０１１０１００１０１１０１０１００１１１０１００１０１１０１０１１１１０１００００１１１０１００１０１０１１１０１０００１０１１１０１０１０００１１０１００１０１１０１１０１０１０１０１０１１０１０１０１０１１０１０１０１００１１０我们总是可以把开始的１１０（以及它之前的无限的空白磁带）删去。由于它表示0０R，这代表开头的指令0０→0０R。而我已隐含地把它当作所有图灵机共有的。这样仪器可从磁带记号左边任意远的地方向右跑到第一个记号为止。而且，由于所有图灵机都应该把它们的描述用最后的１１０结束（因为它们所有都用R、L或STOP来结束），所以我们也可把它（以及假想跟在后面的０的无限序列）删去。这可以算作两个小节约。所得到的二进位数是该图灵机的号码，它在XN＋1的情况下为：
１０１０１１０１１０１００１０１１０１０１００１１１０１００１０１１０１０１１１１０１００００１１１０１００１０１０１１１０１０００１０１１１０１０１０００１１０１００１０１１０１１０１０１０１０１０１１０１０１０１１０１０１０１００。这一特殊的数在标准十进位记号下为450813704461563958982113775643437908。我们有时不严格地把号码为n的图灵机称为第n台图灵机，并用Tn来表示。这样，XN＋1是第450813704461563958982113775643437908台图灵机！我们必须顺着这图灵机的“表”走这么远，才找到一台甚至只进行如此平凡的（在扩展二进位记号上）对自然数加一的运算，这真使人印象深刻！（尽管在我的编码中还可以有很少的改善余地，但我认为自己进行得相当有效率。）实际存在某些更低号码的有趣的图灵机。例如，UN＋1的二进位号码为１０１０１１０１０１１１１０１０１０它只是十进位制的177642！这样，只不过是把一个附加的1加到序列1的尾巴上的特别平凡的图灵机UN＋1是第177642台图灵机。 为了好奇的原因，我们可以注意在任一种进位制中“乘二”是在图灵机表中这两个号码之间的某处。我们找到XN×2的号码为10389728107，而UN×2的号码为1492923420919872026917547669。
人们从这些号码的大小，也许会毫不奇怪地发现，绝大多数的自然数根本不是可工作的图灵机的号码。现在我们根据这种编号把最先的十三台图灵机列出来：
T0：0０→0０R，0１→0０R，T1：0０→0０R，0１→0０L，T2：0０→0０R，0１→0１R，T3：0０→0０R，0１→0０STOP，T4：0０→0０R，0１→1０R，T5：0０→0０R，0１→0１L，T6：0０→0０R，0１→0０R，1０→0０R，T7：0０→0０R，0１→？？？，T8：0０→0０R，0１→10０R，T9：0０→0０R，0１→1０L，T10：0０→0０R，0１→1１R，T11：0０→0０R，0１→0１STOP，T12：0０→0０R，0１→0０R，1０→0０R。其中，T0简单地就是向右移动并且抹去它所遇到的每一件东西，永不停止并永不往回退。机器T1最终得到同样的效应。但它是以更笨拙的方法，在它抹去磁带上的每个记号后再往后跳回。机器T2也和机器T0一样无限地向右移动，但是它更有礼貌，简单地让磁带上的每一件东西原封不动。由于它们中没有一台会停下，所以没有一台可以合格地被称为图灵机。T3是第一台可敬的机器。它的确是在改变第一个（最左边）的１为０后便谦虚地停止。
T4遭遇了严重的问题。它在磁带上找到第一个１后就进入了一个没有列表的内态，所以它没有下一步要做什么的指令。T8、T9和T10遇到同样的问题。T7的困难甚至更基本。把它编码的０和１的串涉及到五个接续的１的序列：１１０１１１１１０。对于这种序列不存在任何解释，所以只要它在磁带上发现第一个1就被绊住。（我把T7或其他任何机器Tn，它的n的二进位展开包含多于四个１的序列称为不是正确指明的。）机器T5、T6和T12遭遇到和T0、T1和T2类似的问题。它们简单地、无限地、永远不停地跑下去。所有T0、T1、T2、T4、T5、T6、T7、78、T9、T10和T12都是伪品！只有T3和T11是可工作的， 但不是非常有趣的图灵机。 T11甚至比T3更谦虚，它在第一次遇到1时就停止，并且没有改变�
