神谕、计算与哲学

计算机教育 哲学 计算机理论

神谕（Oracle）、计算（Computation）和哲学这个标题显然过于庞大与复杂，其实我的本意只是直白地讨论一个数学问题，得到一个关于计算理论的结论，结果却在人生、宗教和哲学等问题中陷入漩涡。

一般而言，在绝望无助的时候，通常大家就会祈祷，希望得到神的帮助。“如有神助”，定能排除万难，能力无限。无神论者自然是不信神，但这并不足以将神排除在他们的思维框架之中，只不过，他们采用了另一种方式。比如，如果一位数学家碰上了一个函数f：x --> y（x映射到y）无法求解，他也许会假设：如果有一个神存在，把这个问题交给她，就会得到这个函数的一个解（当然，也可以让神做一些我们想她做的事情，看情况而定），也许因此我会得到帮助。把这个愿意帮忙的神称为Oracle。如果这个神愿意帮助，f当然可解。问题是，我们通常假设这些个神（想一想那个只满足他人三个愿望的灯神）只帮忙比较有限的次数（比如，多项式次），而X的值域又比较大（指数规模）。问题：在这个能力无比强大但又比较小气（只计算有限次的f(x)）的神帮助下，数学家能不能自己计算这个函数呢？

比如大整数分解问题：给定一个很大的整数（例如1024比特长），要把它分解成若干小整数的乘积。假设有一个神可以解大整数分解问题，你给他许多的大整数，他都可以帮忙分解。等你听够了神的唠叨（在你得到神足够多的帮助）之后，再给你一个新选取的大整数，你能分解它吗？我想，这个神帮不上什么忙。但是，我并不确定.....

Oracle对计算是否有帮助这是一个非常严肃的难题，我没办法回答，但我可以告诉你们一些线索。首先，大部份数学家都相信，Oracle是没有帮助的，也就是说在上面的例子中，有神的帮助，数学家还是无法自己真正地解决难题。其次，非常矛盾地，数学家们在不同的场合也会认为Oracle会有一定的帮助，利用Oracle来区分不同的计算能力，注意，他们并不能证明Oracle有或者没有帮助。换句话说，数学家们想用神的时候就信神，想不信神的时候就否定神（和那些声称信耶稣基督并且每年都到教堂过圣诞节的教友有异曲同工之妙）。数学家这种矛盾也是值得理解的，毕竟他们碰到的难题特别多。

计算理论中有一大类问题被定义为“NP难题”，数学家们似乎还没有驯服这类问题，他们试图对这类问题进行分类，其做法就是借助Oracle，形成难题类的等级。比如，某类问题（记为A类问题），在P时间下解不了，那就看看给一个Oracle是不是有帮助，就定义出了一个新的类A^Oracle。显然，如果A^Oracle类问题还是无法在P时间下解，我再给一个Oracle，定义新的难题类为A^Oracle^Oracle。这些所谓不同的类其实很有可能是相同的玩意儿，但目前谁都不清楚。（以上内容可参考M. Sipser的ITOC第9.2章。）哲学上似乎也有类似的做法。

Oracle的一种重要用途是用于证明某种问题不能被求解。比如，在密码学的领域，通常借助Oracle来证明某种密码体制不能被破解。思路如下：首先假设某个问题不能在多项式时间内被求解，比如大整数分解问题（factoring问题）。接着，假设某种密码体制可以被Adv破解。然后借助Adv的求解过程构造某个Oracle，借助Oracle则可多项式时间求解factoring问题。结论：因为factoring问题不能多项式求解，所以声称可破解密码体制的Adv不存在，所以，此密码体制是安全的。这种证明思路我们称为：归约。

作为普通人，我们有没有相信神谕呢，或者思考一下，神谕对我们有实质性帮助吗？这似乎非常废话，如果你找到灯神，说，给我来一瓶二锅头，立即就有二锅头，这难道不是非常实质性的帮助吗？情况似乎并不是这样，因为神是不可揣摩与测度的，「因为他打破，又缠裹；他击伤，用手医治。」（圣经：约五18）。因此，只要神的帮助是有限次的，那么神是否有实质性帮助就需要重新考量了。想一想你喝了二锅头之后召回的那个法国人就知道了，神也曾善待于他，可是他只能回来陪你喝二锅头了（读者要是不理解这个笑话可以自行Google一下，关键词：二锅头、神灯、笑话）。

我也如先知一般给了学生们很多的神谕，但我相信，我的神谕并不能实质性地帮助到很多人。我最喜欢挂在嘴边的一句就是，你要跟别人竞争跟别人比，比什么？就比学习能力比阅读能力吧。有一个管理学的名人说过：要保持竞争实力，你要做的就是要保持强劲的学习能力。我不是名人，所以没有名言，不被相信也是正常的。然而，许多大名鼎鼎的名言传播遍及世界的每一个文化角落，知道那些道理的人多如牛毛，但是就我肤浅的目力所见，知道道理的人很多，理解道理的人却少，而践行道理的人更少了！神谕谁听啊......值得注意的是，我并不是说神谕没有帮助，我只是说，这种帮助的实质性值得考量。

好吧，其实，我什么都没讲，结论一个都没有，只是很多玩意儿值得重新考量了。充满矛盾的理论，正如神也自相矛盾一样。考虑到，为了高兴，你每天都必须做几件自己不喜欢的事情，以上这些混乱的文字也就好理解了。

Appendix. (Proposed by Zhijie Li)

• Oracle是什么？能回答某种神奇问题的外部设备。

• Oracle Machine是什么？是一种变种的Turing Machine，它可以访问某种Oracle。

• 谁提出Oracle Machine？图灵在他的Phd论文中提出。

• 为什么提出Oracle Machine？用于定义“规约”，把某种问题的求解规约到某种Oracle的访问。比如我们想知道，假如存在一台可回答图灵停机问题的Oracle，那么是不是某种图灵不可判定问题会变得可判定。结果表明，答案是否定的。

目前，除了经典计算领域，在量子计算、密码学、机器学习等领域都常用到Oracle Machine的概念。可以笼统地认为，Oracle Machine是出于研究需要而假设存在的，具备某种计算能力的计算模型。

--2011年12月写；2016年2月整理.