皇帝新脑-第12章
按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
湟行矶嗲扒昂蠛蟮慕耍涔袒峒郝＞」苋绱耍欢芴峁┏稣馓ɑ鞯闹噶畋恚颐前阉莆帐释剂榛０迅没鞫砸欢允齨和m的作用表为U（n；m），我们得到：
U（n；m）=Tn（m）。
这儿Tn是一台正确指明的图灵机6。当首先为U提供数n时，它准确地摸拟第n台图灵机！因为U为一台图灵机，它自身也必须有一号码；也就是说，我们有U=Tu此处号码u待定。u究竟是多少呢？事实上我们可以准确地给出u=7244855335339317577198395039615711237952360672556559631108144796606505059404241090310483613632359365644443458382226883278767626556144692814117715017842551707554085657689753346356942478488597046934725739988582283827795294683460521061169835945938791885546326440925525505820555989451890716537414896033096753020431553625034984529832320651583047664142130708819329717234151056980262734686429921838172157333482823073453713421475059740345184372359593090640024321077342178851492760797597634415123079586396354492269159479654614711345700145048167337562172573464522731054482980784965126988788964569760906634204477989021914437932830019493570963921703904833270882596201301773727202718625919914428275437422351355675134084222299889374410534305471044368695876405178128019437530813870639942772823156425289237514565443899052780793241144826142357286193118332610656122755531810207511085337633806031082361675045635852164214869542347187426437544428790062485827091240422076538754264454133451748566291574299909502623009733738137724162172747723610206786854002893566085696822620141982486216989026091309402985706001743006700868967590344734174127874255812015493663938996905817738591654055356704092821332221631410978710814599786695997045096818419062994436560151454904880922084480034822492077304030431884298993931352668823496621019471619107014619685231928474820344958977095535611070275817487333272966789987984732840981907648512726310017401667873634776058572450369644348979920344899974556624029374876688397514044516657077500605138839916688140725455446652220507242623923792115253181625125363050931728631422004064571305275802307665183351995689139748137504926429605010013651980186945639498（或者至少是这等数量级的其他的可能性）。这个数无疑是极其巨大，但是我似乎没有办法使它变小许多。虽然我的图灵机编码步骤和号码指定是相当合理和简单的，但是在一台实际的普适图灵机的编码中仍然不可避免地导向这么大的一个数7。我曾说过，实际上所有现代通用电脑都是普适图灵机。我并不是说，这种电脑的逻辑设计必须在根本上和我刚刚给出的普适图灵机的描述非常相似。其要点可以简述为，首先为任一台普适图灵机提供一段适当的程序（输入磁带的开始部分）可使它摸拟任何图灵机的行为！在上面的描述中，程序简单地采取单独的数（数n）的形式。但是，其他的步骤也是可能的，图灵原先方案就有许多种变化。事实上，在我自己的描述中，已经有些偏离图灵的原型。但是对于我们当前目的，这些差别中没有一个是重要的。希尔伯特问题的不可解性我们现在回到当初图灵提出其观念的目的，即解决希尔伯特的范围广泛的判决问题：是否存在某种回答属于某一广泛的、但是定义得很好的集合的所有数学问题的机械步骤？图灵发现，他可以把这个问题重述成他的形式，即决定把第n台图灵机作用于数m时实际上是否会停止的问题。该问题被称作停机问题。很容易建造一个指令表使该机器对于任何数m不停。 （例如，正如上面的n=1或2或任何别的在所有地方都没有STOP指令的情形）。也有许多指令表，不管给予什么数它总停（例如n=11）；有些机器对某些数停，但对其他的数不停。人们可以公正地讲，如果一个想象中的算法永远不停地算下去，则并没有什么用处。那根本不够格被称作算法。所以一个重要的问题是，决定Tn应用在m时是否真正地给出答案！如果它不能（也就是该计算不停止），则就把它写成Tn（m）=□。
（在这记号中还包括了如下情形，即图灵机在某一阶段由于它找不到合适的告诉其下一步要做什么的指令而遇到麻烦，正如上面考虑的伪品机器T4和T7。还有不幸得很，我们粗看起来似乎成功的机器T3现在也必须被归于伪品：T3（m）=□，这是因为T3作用的结果总是空白带，而为使计算的结果可赋予一个数，在输出上至少有一个1！然而，由于机器T11产生了单独的1，所以它是合法的。这一输出是编号为0的磁带，所以对于一切m，我们都有T11（m）=0。）
能够决定图灵机何时停止是数学中的一个重要问题。例如，考虑方程：
（x＋1）w＋3＋（y＋1）w＋3=（z＋1）w＋3。
（如果专门的数学方程使你忧虑，不要退缩！这一方程只不过是作为一个例子，没有必要详细地理解它。）这一特殊的方程和数学中著名的或许是最著名的未解决的问题相关。该问题是：存在任何满足这方程的自然数集合w，x，y，z吗？这个著名的称作“费马最后定理”的陈述被伟大的十七世纪法国数学家皮埃尔？德？费马（1601―1665）写在丢番都的《代数》一书空白的地方。费马宣布这方程永远不能被满足①8。虽然费马以律师作为职业（并且是笛卡尔的同时代人），他却是那个时代最优秀的数学家。他宣称得到了这一断言的“真正美妙的证明”，但那里的空白太小写不下。可惜迄今为止既没有人能够重新证明之，也没有人能找到任何和费马断言相反的例子①！很清楚，在给定了四个数（w；x；y；z）后，决定该方程是否成立是计算的① 记住我说的自然数是指0，1，2，3，4，5，6，…。我写成“x＋1” 和“w＋3” 等等，而不写成费马断言的更熟知的形式（xw＋yw=xw，x，y，z＞0，w＞2）的原因是，我们允许x；w等等为从零开始的所有自然数。
① 普林斯顿大学的英籍数学家安德鲁？怀尔斯在1993年6月23日宣布证明了费马最后定理（译者）。事体。这样，我们可以想象让一台电脑的算法一个接一个地跑过所有的四数组，直到方程被满足时才停下。（我们已经看到，存在于一根单独磁带上，把数的有限集合以一种可计算方式编码成为一个单独的数的方法。这样， 我们只要跟随着这些单独的数的自然顺序就能 “跑遍” 所有的四数组。）如果我们能够建立这个算法不停的事实，则我们就有了费马断言的证明。
可以用类似的办法把许多未解决的数学问题按图灵机停机问题来重述。“哥德巴赫猜想”即是这样的一个例子，它断言比2大的任何偶数都是两个质数之和②。决定给定的自然数是否为质数是一个算法步骤，由于人们只需要检验它是否能被比它小的数整除，所以这只是有限计算的事体。我们可以设计跑遍所有偶数6，8，10，12，14，…的一台图灵机，尝试把它们分成奇数的对的所有不同的方法：6=3＋3，8=3＋5，10=3＋7=5＋5，12=5＋7，14=3＋11=7＋7，…对于这样的每一个偶数检验并确认其能分成都为质数的某一对数。 （我们显然不需要去检验除了2＋2之外的偶的被加数对，由于除了2之外所有质数都是奇的。）只有当我们的机器达到一个由它分成的所有的任何一对数都不是质数对的偶数为止才停止。我们在这种情形就得到了哥德巴赫猜想的反例，也就是说一个（比2大的）偶数不是两个质数之和。这样，如果我们能够决定这台图灵机是否会停，我们也就有了决定哥德巴赫猜想真理性的方法。
这里自然地产生了这样的问题：我们如何决定任何特殊的图灵机（在得到特定输入时）会停止否？对于许多图灵机回答这个问题并不难：但是偶尔地，正如我们上面得到的，这答案会涉及到一个杰出的数学问题的解决。 这样， 存在某种完全自动地回答一般问题， 即停机问题的算法步骤吗？图灵指出这根本不存在。
他的论证的要点如下所述，我们首先假定，相反地，存在这样的一种算法①。那么必须存在某台图灵机H，它能“决定”第 n台图灵机作用于数m时，最终是否停止。我们假定，如果它不停的话，其输出磁带编号为0，如果停的话为1：H（n m） =0 T （m） =1 T （m） n； 如果 □如果 停止。n ìí？在这里人们可采取对普适图灵机U用过的同样规则给对（n；m）编码。然而，这会引起如下技术问题，对于某些数n（例如n=7），Tn不是正确指定的，② 我们记得，质数2，3，5，7，11，13，17，…是那些只能分别被它们自己和1整除的自然数。0和1都不认为是质数。① 这是熟知的并且有力的被称为反证法的数学步骤。利用这种办法，人们首先假定所要证明的东西是错的，然后从这里推出一个矛盾，就这样证明所需要的结果实际上是对的。而且在磁带上记号111110不足以把n从m分开。为了排除这一个问题，让我们假定n是用扩展二进位记号而不仅仅是二进位记号来编码，而 m正和以前一样用通常的二进位记号。那么记号110实际上将足够以把n和m区分开来。在H（n；m）中用分号，而在U（n；m）中用逗号就是为了表明这个改变。现在让我们想象一个无限的阵列，它列出所有可能的图灵机作用于所有可能的不同输入的所有输出。阵列的n行展现当第n台图灵机应用于不同的输入0，1，2，3，4，……时的输出：
我在上表中稍微有些欺骗，并且没有把图灵机按它们的实际编号列出。由于所有n比11小的机器除了□外没有得到任何东西，而对于n=11只得到0，所以那样做的话就会得到一张一开始就显得过于枯燥的表。为了使此表一开始就显得更有趣，我假定已得到某种更有效得多的编码。事实上我只是相当随机地捏造这张表的元素，仅仅是为了给出有关它的外表的大体印象。我不要求用某一个算法实际计算过这一个阵列。（事实上，正如我们很快就要看到的，不存在这样的算法。）我们仅仅是假想，真正的表不知怎么搞的已经摆在我们面前，也许是由上帝吧！如果我们试图计算这一个阵列，正是□的发生引起了困难。因为既然那些计算简单地一直永远算下去，我们也许弄不清什么时候把□放在某一位置上！
然而，如果我们允许使用假想的H，由于H会告诉我们□实际上在什么地方发生，我们就可以提供一种产生该表的计算步骤。但是相反地，我们用0来取代每一次□的发生，就这样地利用H把□完全除去。这可由把计算H（n；m）叫放在Tn对m作用之前而作到；然后只有如果H（n；m）=1时（也就是说，只有如果计算Tn（m）实际上给出一个答案时），我们才允许Tn作用到m上，而如果H（n；m）=0（也就是如果Tn（m）=□），则简单地写为0。我们可把新的步骤（也就是把H（n； m）的作用放在Tn（m）之前得到的）写成Tn（m）×H（n；m）。（我在这里使用数学运算顺序的普通习惯：在右边的先进行。请注意，我们在符号运算上有：□×0=0。）现在这张表变成：
我们注意到，假定H存在，该表的行由可计算的序列组成。（我用一个可计算序列表明一个其接连的值可由一个算法产生出来的一个无限序列；也就是存在一台图灵机，当它依序地应用于自然数m=0，1，2，3，4，5，…
上时，就得到了这个序列的接续元素。）现在，我们从该表中可以注意到两个事实。首先自然数的每一可计算序列必须在它的行中出现在某处（也许出现好几回）。这个性质对于原先的带有□的表已经是真的。我们只不过是简单地加上一些行去取代“伪品”的图灵机（也就是至少产生一个□的那些）。其次，我们已经假定，图灵机H实际上存在，该表已被计算地（也就是用某个确定的算法）由步骤Tn（m）×H（n；m）产生。换言之，存在某一台图灵机Q，当它作用于一对数（n；m）时就会在表中产生合适的元素。
为此我们可以在Q的磁带上以和在H中一样的方式对n和m编码。我们得到Q（n；m）=Tn（m）×H（n；m）。
现在我们应用乔治？康托的“对角
