皇帝新脑-10

结束 （因为它们所有都用R、L或STOP 来结束），所以我们也可把它 （以及假想跟在后面的０的无限序列）删去。这可以算作两个小节约。所得到的二进位数是该图灵机的号码，它在XN+1 的情况下为：１０１０１１０１１０１００１０１１０１０１００１１１０１００１０１１０１０１１１１０１００００１１１０１００１０１０１１１０１０００１０１１１０１０１０００１１０１００１０１１０１１０１０１０１０１０１１０１０１０１１０１０１０１００。这一特殊的数在标准十进位记号下为450813704461563958982113775643437908。我们有时不严格地把号码为 n 的图灵机称为第n 台图灵机，并用T 来表n示。这样，XN+1 是第450813704461563958982113775643437908 台图灵机！我们必须顺着这图灵机的 “表”走这么远，才找到一台甚至只进行如此平凡的 （在扩展二进位记号上）对自然数加一的运算，这真使人印象深刻！ （尽管在我的编码中还可以有很少的改善余地，但我认为自己进行得相当有效率。）实际存在某些更低号码的有趣的图灵机。例如，UN+1 的二进位号码为１０１０１１０１０１１１１０１０１０它只是十进位制的177642！这样，只不过是把一个附加的1加到序列 1 的尾巴上的特别平凡的图灵机 UN+1 是第 177642 台图灵机。为了好奇的原因，我们可以注意在任一种进位制中 “乘二”是在图灵机表中这两个号码之间的某处。我们找到XN×2 的号码为10389728107，而UN×2 的号码为1492923420919872026917547669。人们从这些号码的大小，也许会毫不奇怪地发现，绝大多数的自然数根本不是可工作的图灵机的号码。现在我们根据这种编号把最先的十三台图灵机列出来：T ：0 ０→0 ０R，0 １→0 ０R，----------------------- Page 63-----------------------T ：0 ０→0 ０R，0 １→0 ０L，1T ：0 ０→0 ０R，0 １→0 １R，2T ：0 ０→0 ０R，0 １→0 ０STOP，3T ：0 ０→0 ０R，0 １→1０R，4T ：0 ０→0 ０R，0 １→0 １L，5T ：0 ０→0 ０R，0 １→0 ０R，1０→0 ０R，6T ：0 ０→0 ０R，0 １→？？？，7T ：0 ０→0 ０R，0 １→10０R，8T ：0 ０→0 ０R，0 １→1０L，9T ：0 ０→0 ０R，0 １→1１R，10T ：0 ０→0 ０R，0 １→0 １STOP，11T ：0 ０→0 ０R，0 １→0 ０R，1０→0 ０R。12其中，T 简单地就是向右移动并且抹去它所遇到的每一件东西，永不停止并永不往回退。机器 T 最终得到同样的效应。但它是以更笨拙的方1法，在它抹去磁带上的每个记号后再往后跳回。机器T 也和机器T 一样无2 0限地向右移动，但是它更有礼貌，简单地让磁带上的每一件东西原封不动。由于它们中没有一台会停下，所以没有一台可以合格地被称为图灵机。T3是第一台可敬的机器。它的确是在改变第一个 （最左边）的１为０后便谦虚地停止。T 遭遇了严重的问题。它在磁带上找到第一个１后就进入了一个没有4列表的内态，所以它没有下一步要做什么的指令。T 、T 和 T 遇到同样的8 9 10问题。T 的困难甚至更基本。把它编码的０和１的串涉及到五个接续的１7的序列：１１０１１１１１０。对于这种序列不存在任何解释，所以只要它在磁带上发现第一个1就被绊住。 （我把T 或其他任何机器T ，它的n7 n的二进位展开包含多于四个１的序列称为不是正确指明的。）机器T 、T5 6和 T 遭遇到和T 、T 和 T 类似的问题。它们简单地、无限地、永远不停12 0 1 2地跑下去。所有T 、T 、T 、T 、T 、T 、T 、7 、T 、T 和 T 都是伪品！0 1 2 4 5 6 7 8 9 10 12只有T 和 T 是可工作的，但不是非常有趣的图灵机。T 甚至比T 更谦虚，3 11 11 3它在第一次遇到1时就停止，并且没有改变任何东西！我们应该注意到，在表中还有一个多余。由于T 和 T 从未进入内态6 121，机器T 和 T 等同，并在行为上和T 等同。我们既不必为这个多余，12 6 0也不必为表中的图灵机伪品而烦恼。人们的确可以改善编码以摆脱许多伪品和大大减少重复。所有这些都是以使我们可怜的普适图灵机变得更复杂作为代价。普适图灵机必须把所读到的号码 n解码并假装成图灵机 T 。如n果我们可以把所有伪品 （或者多余量）取走，这还是值得做的。但是，我们很快就会看到，这是不可能的！这样，我们就不触动我们的编码好了。例如，可方便地把具有…０００１１０１１１００１００００…----------------------- Page 64-----------------------接续记号的磁带解释成某个数字的二进位表示。我们记得０在两端会无限地继续下去，但是只有有限个１。我还假定１的数目为非零 （也就是说至少有一个１）。我们可以选择去读在第一个和最后一个 1 （包括在内）之中的有限的符号串，在上述的情况是为一自然数的二进位写法１１０１１１００１，它在十进位表示中为441。然而，这一过程只能给我们奇数 （其二进位表示以１结尾的数）。而我们要能表示所有的自然数。这样，我们采取移走最后的１的简单方案 （这个１仅仅被当作表示这一程序的终止记号），而5把余下来的当成二进位数来读 。因此，对于上述的例子，我们有二进位数１１０１１１００，它是十进位的220。这个步骤具有零也用磁带上的记号代表的好处，也就是…００００００１００００００…我们考虑图灵机T 对我们从右边提供给它的磁带上 （有限的）０和１n的串的作用。根据上面给出的方案，可方便地把这串也考虑作某一个数，譬如m 的二进位代表。我们假定，机器T 在进行了一系列的步骤后最终到n达停止 （即到达STOP）。现在机器在左边产生的二进位数串是该计算的答案。让我们也以同样方式把这当作，譬如是p 的二进位代表来读。我们把表达当第 n 台图灵机作用到m 上时产生p 的关系写成：T (m)=p。n现在，以稍微不同的方式看这一关系。我们把它认为是一种应用于一对数 n和m 以得到数p 的一个特别运算。 （这样，若给定两个数 n和m，视第 n 台图灵机对m 作用的结果而得出 p。）这一特别运算是一个完全算法的步骤。所以它可由一台特殊的图灵机U 来执行。也就是说，U作用到一对(n，m)上产生p。由于机器U 必须作用于n和m 两者以产生单独结果p，我们需要某种把一对(n，m)编码到一条磁带上的方法。为此，我们可假定n 以通常二进位记号写出并紧接着以序列１１１１１０终结。（我们记得，任一台正确指明的图灵机的二进位数都是仅仅由０，１０，１１０，１１１０和１１１１０组成的序列，因此它不包含比四个１更多的序列。这样，如果T 是正确指明的机器，则１１１１１０的发生的确表明数n 的描述已n终结。）按照我们上面的规定，跟着它的每一件东西简单地是代表m 的磁带 （也就是，紧跟二进位数m 的是１０００…）。这样，这第二个部分简单地就是T 假设要作用的磁带。n作为一个例子，如果我们取 n=11和m=6 当作U要作用的磁带，其记号序列为…０００１０１１１１１１１０１１０１００００…这是由以下组成的：----------------------- Page 65-----------------------…００００ （开始的空白带）１０１１（11 的二进位表示）１１１１１０（终结n）１１０…（6 的二进位表示）１００００…（余下的磁带）。在 T 作用到m 上的运算的每一接续的步骤，图灵机U要做的是去考察nn 的表达式中的接续数位的结构，以使得在m 的数位 （也就是T 的磁带）n上可进行适当的代换。在原则上 （虽然在实践中肯定很繁琐）不难看到人们实际如何建造这样的一台机器。它本身的指令表会简单地提供一种，在每一阶段读到被编码到数 n 中的“表”中，应用到m 给出的磁带的位数时，合适元素的手段。肯定在m 和 n 的数位之间要有许多前前后后的进退，其过程会极为缓慢。尽管如此，一定能提供出这台机器的指令表，而我们把它称为普适图灵机。把该机器对一对数n和m 的作用表为U(n,m)，我们得到：U(n,m)=T (m)。n6这儿 T 是一台正确指明的图灵机 。当首先为U提供数 n 时，它准确地摸n拟第 n 台图灵机！因为U 为一台图灵机，它自身也必须有一号码；也就是说，我们有U=Tu此处号码u待定。u 究竟是多少呢？事实上我们可以准确地给出u=7244855335339317577198395039615711237952360672556559631108144796606505059404241090310483613632359365644443458382226883278767626556144692814117715017842551707554085657689753346356942478488597046934725739988582283827795294683460521061169835945938791885546326440925525505820555989451890716537414896033096753020431553625034984529832320651583047664142130708819329717234151056980262734686429921838172157333482823073453713421475059740345184372359593090640024321077342178851492760797597634415123079586396354492269159479654614711345700145048167337562172573464522731054482980784965126988788964569760906634204477989021914437932830019493570963921703904833270882596201301773727202718625919914428275437422351355675134084222299889374410534305471044368695876405178128019437530813870639942772823156425289237514565443899052780793241144826142357286193118332610656122755531810207511085337633806031082361675045635852164214869542347187426437544428790062485827091240422076538754264454133451748566291574299909502623009733738137724162172747723610206786854002893566085696822620141982486216989026091309402985706001743006700868967590344734174127874255812015493663938996905817738----------------------- Page 66-----------------------591654055356704092821332221631410978710814599786695997045096818419062994436560151454904880922084480034822492077304030431884298993931352668823496621019471619107014619685231928474820344958977095535611070275817487333272966789987984732840981907648512726310017401667873634776058572450369644348979920344899974556624029374876688397514044516657077500605138839916688140725455446652220507242623923792115253181625125363050931728631422004064571305275802307665183351995689139748137504926429605010013651980186945639498（或者至少是这等数量级的其他的可能性）。这个数无疑是极其巨大，但是我似乎没有办法使它变小许多。虽然我的图灵机编码步骤和号码指定是相当合理和简单的，但是在一台实际的普适图灵机的编码中仍然不可避免7地导向这么大的一个数 。我曾说过，实际上所有现代通用电脑都是普适图灵机。我并不是说，这种电脑的逻辑设计必须在根本上和我刚刚给出的普适图灵机的描述非常相似。其要点可以简述为，首先为任一台普适图灵机提供一段适当的程序（输入磁带的开始部分）可使它摸拟任何图灵机的行为！在上面的描述中，程序简单地采取单独的数 （数n）的形式。但是，其他的步骤也是可能的，图灵原先方案就有许多种变化。事实上，在我自己的描述中，已经有些偏离图灵的原型。但是对于我们当前目的，这些差别中没有一个是重要的。----------------------- Page 67-----------------------希尔伯特问题的不可解性我们现在回到当初图灵提出其观念的目的，即解决希尔伯特的范围广泛的判决问题：是否存在某种回答属于某一广泛的、但是定义得很好的集合的所有数学问题的机械步骤？图灵发现，他可以把这个问题重述成他的形式，即决定把第 n 台图灵机作用于数m 时实际上是否会停止的问题。该问题被称作停机问题。很容易建造一个指令表使该机器对于任何数m 不停。（例如，正如上面的 n=1或2 或任何别的在所有地方都没有STOP 指令的情形）。也有许多指令表，不管给予什么数它总停 （例如n=11）；有些机器对某些数停，但对其他的数不停。人们可以公正地讲，如果一个想象中的算法永远不停地算下去，则并没有什么用处。那根本不够格被称作算法。所以一个重要的问题是，决定T 应用在m 时是否真正地给出答案！如n果它不能 （也就是该计算不停止），则就把它写成T (m)=□。n（在这记号中还包括了如下情形，即图灵机在某一阶段由于它找不到合适的告诉其下一步要做什么的指令而遇到麻烦，正如上面考虑的伪品机器T4和 T 。还有不幸得很，我们粗看起来似乎成功的机器T 现在也必须被归于7 3伪品：T (m)=□，这是因为T 作用的结果总是空白带，而为使计算的结果3 3可赋予一个数，在输出上至少有一个 1！然而，由于机器T 产生了单独的111，所以它是合法的。这一输出是编号为0 的磁带，所以对于一切m，我们都有 T (m)=0。）11能够决定图灵机何时停止是数学中的一个重要问题。例如，考虑方程：w+3 w+3 w+3(x+1) +(y+1) =(z+1) 。