皇帝新脑-第11部分

快捷操作: 按键盘上方向键 ← 或 → 可快速上下翻页 按键盘上的 Enter 键可回到本书目录页 按键盘上方向键 ↑ 可回到本页顶部! 如果本书没有阅读完，想下次继续接着阅读，可使用上方 "收藏到我的浏览器" 功能 和 "加入书签" 功能！

的确，正如我们很快就要看到的，情况刚好相反。我们关于单独问题的不可解性一点也没提，仅仅是说关于问题的族的算法的不可解性。在任何单独的情形下，答案或者为“是”或者为“非”，所以肯定存在一个决定那个特定情形的算法，也就是在它面临该问题时，依情况而定，会简单地讲“是”或“非”。当然，困难在于我们可能不知道用这些算法中的哪一个。那就是决定一个单独陈述而不是决定一族陈述的数学真理的问题。重要的是要意识到，算法本身不能决定数学真理。一个算法的成立总是必须由外界的手段来建立起来。如何超过算法我们在以后论及哥德尔定理时再回到决定数学陈述的真理性问题（参阅

　　第四章）。我希望在此刻指出，图灵的论证比我迄今仿佛所暗示的更具

　　建设性而更少负面性。我们肯定还没有展示出一台特殊的图灵机，它在某种绝对的意义上不能决定其是否停止的问题。的确，如果我们仔细地考察该论证就会发现，我们步骤本身实际上已经隐含地告诉我们，对这利用图灵步骤建造的似乎“极端荒谬”的机器的答案！我们看看这是怎么来的。假定我们有某一个算法，它有时有效地告诉我们什么时候一台图灵机将不停止。正如在上面概述的，图灵步骤将明白地展现了一台图灵机计算，对这计算那个特殊算法不能决定其是否停止。

　　然而，在这样做的同时，它实际上使我们在这情况下看到了答案！我们展现的特殊的图灵机计算的确不会停止。为了仔细考查这怎么引起的，假定我们具有一个这样有时有效的算法。正如以前那样，我们用H来标志这个算法（图灵机），但是现在允许该算法有时不能告诉我们一台图灵机在实际上将不停止：

　　H（n　m）　=0　T　（m）　=1　T　（m）；　或□如果　□如果　停止。nnìí？这样，当　Tn（m）=□时H（n；m）=□是一种可能性。实际上存在许多这种算法H（n；m）。（例如，只要Tn（m）一停止，H（n；m）就能简单地产生1，尽管那个特殊的算法几乎没有什么实际的用处！）

　　除了不把所有的□用0来取代而留下一些以外，我们可以像上述那样仔细地顺着图灵的步骤。正如以前那样，对角线过程提供了对角线上的第n个元素1＋Tn（n）×H（n；n）。（只要H（n；m）=□，我们就将得到一个□。注意□×□=□，1＋□=□。）

　　这是一个完好的计算，所以它是由某一台，譬如讲第n台图灵机得到的，而且现在我们确实有1＋Tn（n）×H（n；n）=Tk（n）。

　　我们看第k个对角元素，也就是n=k，就会得到1＋Tk（k）×H（k；k）=Tk（k）。如果计算Tk（k）停止，我们就有了一个矛盾　（由于假定只要Tk（k）停止H（k；k）就为1，则方程导致不协调性：1＋Tk（k）=Tk（k）。所以Tk（k）。不能停止，也就是Tk（k）=□。但是，算法不能“知道”这个。因为如果该算法给出H（k；k）=0，则我们应该又导致矛盾（我们得到了在符号上不成立的关系：1＋0=□）。这样，如果我们能找到k，就将知道如何去建造击败我们知道其答案的算法的特别计算！我们怎么找到k呢？这是一项艰巨的工作。我们需要做的是仔细考察H（n；m）和Tn（m）的构造，然后仔细弄清1＋Tn（n）×H（n；n）作为一台图灵机是如何动作的。我们发现这台图灵机的号码为k。要把这一切要弄透彻肯定是复杂的，但它是可以办得到的①。由于这种复杂性，若不是因为我们为了击败H而特地制造Tk（k）的这个事实，　我们对计算Tk（k）

　　毫无兴趣！重要的是，我们有了定义很好的步骤，不管我们的H是哪一个，该步骤都能找到合适的k，使得Tk（k）击败H，因此这样我们可以比该算法做得更好。如果我们认为自己仅仅比算法更好些，也许会给我们带来一些小安慰！事实上，该过程被定义得如此之好，以至于在给定的H下，我们可找到产生k的一个算法。这样，在我们过于得意之前必须意识到，由于这个算法事实上“知道”Tk（k）=□，所以它能改善9H，是不是？在上面提到一个算法时，用拟人化的术语“知道”是有助的。然而，该算法仅仅是跟随我们预先告诉它去跟随的法则，这难道不是我们在“知道”吗？或者我们自己，仅仅是在跟随我们的头脑的构造和我们的环境所预先编排我们去跟随的规则？这问题实在不只是简单的算法问题，而且是人们如何判断何为真何为伪的问题。这是我们必须重新讨论的中心问题。数学真理（以及其非算法性质）的问题将在

　　第四章考虑。现在我们至少对术语“算法”和“可

　　计算性”的意义以及某些相关的问题已有些领略。

　　①　事实上，由于在上面建造普适图灵机U　已使我们能把Tn（n）写成作用于n上的一台图灵机，所以已经得到这个最难的部分。撤屈拉姆达计算法可计算性的概念是一个非常重要和美丽的数学观念。它又是相当近代的，具有这样基本性质的事体进入数学的王国是本世纪三十年代的事。这个观念已经渗透到数学的所有领域中去（虽然这一点确实是真的，但是大多数数学家通常不去忧虑可计算性的问题）。该观念的威力有一部分来自于这一个事实，即数学中一些定义得很好的运算实际上不是可计算的（例如图灵机的停机问题；第四章还可以看到其他例子）。因为如果不存在这

　　种不可计算的事体，则可计算性的概念便没有多少数学的兴趣。数学家毕竟喜欢困惑的东西。让他们决定某些数学运算是否为可计算的可能是非常迷人的困惑。因为那个困惑的一般解答本身是不可计算的，这一点尤其迷人！有一件事要弄清楚。可计算性是一个真正“绝对的”数学概念。它是一种抽象的观念，它完全超越按照我们描述的“图灵机”的任何特别实现之外。正如我在以前所评论的，我们不必对表征图灵的天才而特别的手段的“磁带”和“内态”等等赋予任何特别的意义。还有表达可计算性观念的其他方法，历史上最早的是美国逻辑学家阿伦佐？撤屈在斯蒂芬？C？克利涅协助下提出的杰出的“拉姆达计算法”。撤屈的步骤和图灵的完全不同，并且更为抽象得多。事实上，在撤屈陈述他观念的形式中，在它们和任何可以称作“机械的”东西之间只有一点明显的连接。撤屈步骤背后的关键观念在其最本质上的确是抽象的，实际上撤屈把这步骤称为“抽象化”的一个数学运算。不仅是因为撤屈方案强调可计算性是一个独立于计算机器的任何特别概念的数学观念，而且它阐明了在数学中抽象观念的威力，所以我感到值得花一点时间来简要地描述它。对数学观念不熟悉或者对这件事本身不感好奇的读者，在这一阶段可以跳到下一章去，这不会对论证的过程产生多少损失。尽管如此，这样的读者若愿意和我多忍受一阵会得到好处，并且能见证撤屈方案的某些魔术般的经济性（参见撤屈1941）。人们在此方案中关心的是，譬如由以下表示的对象的“宇宙”

　　a，b，c，d，…，z，a′，b′，…，z′，a′′，b′′，…，a′′′，…，a′′′′，…其中每一元素代表一个数学运算或函数。（带撇字母的原因简单地是，无限地提供以表示这种函数的符号。）这些函数的“自变量”，即它们所作用的东西，是同一类型的其他东西，也就是函数。此外，一个这种函数作用于另一个函数的结果（或“值”）仍是一个函数。（在撤屈的系统中的确具有美妙的概念经济性。）这样，当我们写a=bc①　一种更熟悉的记号是写成a=b（c），但这些特别的括号不是真正必要的，在习惯上把它们忽略去更好些。时，我们是指函数b作用于函数c的结果为另一函数a。要在这个方案中表达两个或更多变量的函数的观念并没有困难。如果我们希望把f认为两个变量，譬如讲p和q的函数，我们可以简单地写（fp）q（这是函数fp作用于q的结果）。对于三变量函数我们考虑（（fp）q）r，等等。让我们引进抽象化的有力的运算。为此我们使用希腊字母λ（拉姆达），而且有它后面紧跟着的是代表一个撤屈函数的一个字母，譬如讲x，我们把它当成“哑变量”。任何发生于紧跟在这后面的方括号内的表达式中的变量x是仅仅被当作一个“口”，可以往里面代入任何跟在整个表达式后的任何东西。这样，如果我们写λx．〔fx〕，我们是说，当它作用到譬如讲函数a上时，就产生结果fa。那就是（λx．〔fx〕）a=fa。换言之，λx．〔fx〕简单地就是函数f；即λx．〔fx〕=f。这里只用一点思维就够了。数学的一个美妙在于，初看起来是如此卖弄学识的、琐碎的东西，也是人们非常容易完全失去要点的东西。让我们考虑从中学数学取来的一个熟悉的例子。我们取函数f为对一个角度取正弦的三角运算，这样抽象的函数“sin”被定义为λx．〔sinx〕=sin。

　　（不必为何以“函数”x可当作一个角度而忧虑。我们很快就会看到数可被当成函数的某种方法；而一个角度只是一个数。）迄今为止的一切的确是相当无聊的。让我们设想，记号“sin”还没被发明，但是我们熟悉sinx的级数展开表达式x　x　x　－　…。　1611203　5＋　…然后我们可以定义sin　。＇　＇　=　…　＋　lx　x　x　x1611203　5－…　。请注意，我们甚至可以更简单地定义，譬如讲“六分之一立方”的运算，它并没有标准的“函数”记号Q　x　x　=　l　。＇　＇

　　163，而且发现，例如如果把它们一律都保留着，就会导致相当的繁琐，诸如表达式（f（p））（q）和（（f（p））（q））（r）可分别简化成（fp）q　和（（fp）q）r。Q　a　a　a　a　a　（　）　（　）　＋　=　＋　=　＋　＋　＋　1161161212163　3　2。从撤屈的基本函数运算简单地构造的表达式对于现在的讨论更为贴切，例如λf。〔f（fx）〕。

　　这是一个函数，当它作用于另一函数，譬如讲g时，产生g两次递归地作用于x上的函数，也就是（λf。〔f（fx）〕）g=g（gx）。

　　我们也可以首先“抽象化走”x以得到λf。〔λx。〔f（fx）〕〕；此式可以缩写成λfx〔f（fx）〕。这是当作用于g时产生“g被递归两次”的函数。事实上，这正是撤屈将其和自然数2相等同的函数。2=λfx．〔f（fx）〕，这样，（2g）y=g（gy）。他类似地定义：3=λfx．〔f（f（fx））〕，4=λfx〔f（f（f（fx））〕，等等，以及1=λfx．〔fx〕，0=λfx，〔x〕。撤屈的“2”真的更像“两次”，它的“3”是“三次”等等。这样3在一个函数f上的作用，也就是3f是“把f递归三次”的运算。因此，3f在y上的作用是（3f）y=f（f（f（y）））。

　　让我们看看，一个非常简单的算术运算，也就是如何把1加到一个数上的运算在撤屈方案中表达出来。定义S=λabc．〔b（（ab）c）〕。

　　为了阐明S的确简单地把１加到用撤屈记号表示的一个数上，让我们做这样的检验：S3=λabc．　〔b（（ab）c）〕3=λbc．　〔b（（3b）c）〕=λbc。〔b（b（b（bc）））〕

　　=4，这是由于（3b）c=b（b（bc））。很清楚，这可同样好地适用于任何其他自然数。（事实上λabc．〔（ab）（bc）〕可以和S一样好地做到。）

　　把一个数乘二又如何呢？这种加倍可由D=λabc．〔（ab）（（ab）c）〕获得，它可再次由作用于３上而得到验证：

　　D=λabc。〔（ab）（（ab）c）〕3=λabc。〔（3b）（（3b）c）〕

　　=λabc。〔（3b）（b（b（bc）））〕=λabc。〔b（b（b（b（b（bc）））））〕=6。

　　事实上，加法、乘法和升幂的基本算术运算可分别定义为A=λfgxy。〔（（fx）（gx））y〕；M=λfgx。〔f（gx）〕；P=λfg。〔fg〕。

　　读者也许介意使自己或他人信服，我们的确有如下结果：

　　（Am）n=m＋n，（Mm）n=M×n，（Pm）n=nm，这儿m是n是撤屈的两个自然数的函数，m＋n是它们和的相应函数，等等。　最后那个公式是最令人惊异的。　让我们仅仅检验其m=2，　n=3的情形：

　　（p2）3=（（λfg。〔fg〕）2）3=（λg。〔2g〕）3=（λg。〔λfx。〔f（fx）〕g〕）3=λgx。〔g（gx）〕3=λx。〔3（3x）〕

　　=λx。〔λfy。〔f（f（fy））〕（3x）〕

　　=λxy。〔（3x）（（3x）（（3x）y））〕

　　=λxy。〔（3x）（（3x）（x（x（xy）））））〕

　　=λxy。〔（3x）（x（x（x（x（xy）））））〕

　　=λxy。〔x（x（x（x（x（x（x（x（xy））））））））〕

　　=9=32减法和除法不是这么容易定义的（我们的确需要某种当m比n小时“m…n”以及当m不能被n整除时“m÷n”的惯例。事实上，二十世纪三十年代早期克利涅发现如何在撤屈的方案中表达减法运算被认为是这一学科的重要里程碑！后来接着又有其他的运算。最后，撤屈和图灵在1937年独立地指出，不管什么样的可计算的（或算法的）运算（现在在图灵机的意义上）都可以按照撤屈的一种表达式获得（而且反之亦然）。

　　这是一个真正惊人的事实，它被用来强调可计算性思想的基本客观性以及数学特征。初看起来，撤屈的可计算性概念和计算机器没有什么关系。然而，它和实际计算具有某些基本关系。尤其是，有力而灵活的电脑LISP语言以一种根本的方式参与到撤屈计算法的基本结构中来。正如我早先指出的，还有其他定义可计算性概念的方法。波斯特的计算机器的概念和图灵的非常接近，并且几乎是同时独立提出的。近世还有更有用的可计算性（递归性）的定义，这是J？赫伯拉德和哥德尔提出的。

　　H？B？邱雷在1929年，以及M？轩芬克勒在1924年稍早些时候提出了不同的方法，撤屈计算法就是部分地由此发展而来（参见甘迪1988）。现在研究可计算性的手段（诸如在（卡特兰1980）中描述的一台无限记录机器）在细节上和图灵原先的相差甚多，而且它们更实用得多。然而，不管采用那种不同的手段，可计算性的概念仍然相同。

　　正如许多其他的数学观念，尤其是更美丽的、更基本的那些，可计算性的观念似乎自身具有某种柏拉图的实在性。在下面两章，我们应该探讨的正是数学概念的柏拉图实在性的这个神秘问题。

　　注　释1．我是采用当代通常的术语，它现在把零包括在“自然数”之中。

　　2．还有许多把一对、三个等等数编码成单独一个数的其他方法。虽然它们对于我们现在的目的不甚方便，数学家却熟知这些方法。例如，公式　便是用一个单独的自然数来代表一对自然数　。　12（（a　＋　b）　＋　3a　＋　b）　（a；　b）

　　2试试看！3．我在上面没花工夫去引进某种表示起始一个数（或指令等等）的序列的记号。这对于输入没有必要，由于当遭遇到第一个1时事情刚刚开始。然而，对于输出需要某些其他东西，这是由于人们预先为了达到第一个（也就是最左边的）1不知道要沿着输出磁带看多远。尽管在往左看时会遇到0的很长的串，这并不能保证在左边更远处不再有1。人们对此可采用不同的观点。其中一种总是用特殊记号（譬如，在收缩步骤中用6来编码）去启始整个输出。但是为了简单起见，我在自己的描述中将采用不同的观点，也就是总“知道”仪器实际上已遭遇到了多长的“磁带”（例如，人们可以想象，它留下了某种痕迹），在原则上不必去检查无限长的磁带，就能肯定整个输出已被查过。4．一种把两盘磁带的信息编码到单独一盘磁带上的方法是插入法。这样，这盘单独磁带上的奇数号码的记号可代表第