2005-12-07 22:31| 
20 Comments | 本文内容遵从 看黑书介绍NP的时候有一个“不可解问题”，非常不可思议，费劲周折在网上查到了些英文资料，搞明白了，非常有意思，在这里说一下。
不可解问题(Undecidable Decision Problem)指的是这样一种问题：他无论如何也不可能有一个正确的算法来解决。虽然不可思议，但这种问题被证明确实是存在的。图灵在1936年（那时还没电脑，我们的父亲是在没有设备支持的纯理论基础上提出来的，致敬）提出了第一个不可解问题的实例：The Halting Problem。
The Halting Problem是问，输入一段程序代码和一个针对此程序的输入，能否编程判断运行这个程序后程序是否会终止。
这个问题的答案是否定的。也就是说，不可能有一种算法可以正确判断一个指定的程序运行后，给予指定的输入，程序最后出不出得来。换句话说，The Halting Problem是一个不可解问题。
虽然这感觉似乎不可能，但在严格的证明下谁也无法发言反对。
证明过程非常简单，假设The Halting Problem是有解的，并且已经用程序实现了，那么我们只需要再编写一个程序Program Bug，就会发现存在矛盾。
反证：既然解决The Halting Problem的算法已经实现了，那么我们一定能定义一个函数
Function Halting(a,b:input_type):boolean;
其中，a是读入的程序源码，b是输入数据。这个函数的功能就是返回对于指定的程序源码和输入数据，程序是否能顺利退出。
下面编写一个程序：
Program Bug;
var
code:input_type;
begin
get(code); //读入code
if halting(code,code) then repeat until false
else halt;
end.
好，现在运行Bug这个程序，并且输入Bug这个程序本身的代码。这样，halting(code,code)其实质就是在判断这个Bug程序本身了。如果The Halting Problem认为Bug程序会正常退出，那么就让程序进入一个死循环，否则立即退出程序。矛盾产生。
//简直是在挑战表达力极限
//做人要厚道，转帖请注明出处
20 条回复
您也随便说几句吧：
您的表达还是很清楚的嘛
那个反证法太美妙了...
最后一段懂了,很不错的反证...[GoodLuck]
图灵为何不喜欢MM呢?[tea]
证法的确相当经典，ps这题作为NOIP2007提高组初赛题考了。
能否等价为：
输入一段代码A和一个针对A的输入a，能否编程B判断A（a）是否是死循环。
回复：对
终于有个上网的机会，来看看你的地盘。
自我感觉这是个在你给出的BUG程序下会成为悖论的问题。简称program bug 为悖论程序，呵呵。
学数学蛮好玩。我们最近教到叉乘了，还记得在bsy的时候，你来给我们讲了叉乘，那天晚上我在寝室熬夜整理笔记到将近两点。咳……信息竞赛的任何一个回忆的片段总能给我很深的感慨，不知道你是不是呢？
[loo]
那啥。。。我一直想知道。。。黑书是什么？
回复：算法艺术与信息学竞赛
我觉得关于问题的表述
应该换成一种更清晰的不易让人误解的方式
比如：能否存在一种算法，对任意一个给定程序A，以及任意一个针对A的输入，判断出A是否能够终止。
[...] 还是从幻想中清醒过来吧，能判断一个程序能否无限运行下去的程序是否真的存在我们还不知道呢。不过仔细回想一下上面的讨论，你会意识到这种程序的存在该是多么的不可思议啊。即使这样的程序真的存在，实现它的难度也绝对不亚于解决上述的任何一个数学猜想，不然的话大家都转而向这个神奇的“万能证明方法”进攻了。 而事实上，科学家们已经从理论上证明了，这种程序是永远不可能实现出来的。这就是著名的停机问题(The Halting Problem)，它是一个不可解问题。停机问题不可解的证明并不复杂，并且非常有趣。你可以在这里看到整个证明过程。我们刚才那些美好的梦想被这一个简短的证明摔成了碎片。 [...]
有趣的证明
我不认同这个反证法，这个证明带有自指性（读入自己这段程序）。就像集合论中的某些悖论一样，钻了定义的空子。
@凌晨海风
自指性很正常吧。
如果不认同这个反证法，那可以看看哥德尔不完备性定理以及康托对角线删除方法的证明。
啊。。。我想问。。。你这些东西是在哪找的啊。。。好强啊
类比一下，假设存在上帝，而你现在在梦中。
如果你认为你马上会从梦中醒来，那么上帝就不让你醒来，所以你的‘认为’是错的；如果你认为你不会醒来，那么上帝就让你醒来，所以你的‘认为’依然是错的。因此，无论你怎么认为，上帝都可以判决你的认为是错的。
停机问题于此类似，只不过这里的上帝是程序员，代码是梦中的人。可见停机问题是荒谬的
停机问题与表达式（符号）的任意性：
我把（code，表达式，符号，字母）暂时视为通一个东西。
我们可以任意的输入一段代码，例如“Program Bug”，又比如：
a="a就是非a"
假定这里的a是同一个东西，那么就会出现‘悖论’：a为真，则a为假;a为假，则a为真。为什么会这样呢？因为它给出的表达式“a就是非a”本身就违反了矛盾律。
我说的这句话是假话；语言结构：
假设“这句话”=a
那么 a="a是假话"，即a="a并非a"
反证法确实厉害……
运行BUG程序,会在无限时间之后返回一个类似:此题有限时间内不可解 的东西
悖论就是在没有限制条件下自相矛盾的事，如同理发师说“我将给所有不能自己剪头发的人理发”一样，只有对象是理发师自己时才会出现错误。只要加上一条说明“除了自己以外”就没有问题了。
那么这个证明会不会也是这样，用反证法来证明只是一个对于本身而言的逻辑上的错误，只要在使用Halting函数时避免递归调用，就不会有矛盾产生。
¿Sí?
[...] 今天学到一个好玩的东西。仿照停机问题的研究方法，我们可以想出很多有趣的不可解问题。Gregory Chaitin曾经提出过下面这个问题。如果两段代码运行之后能够输出相同的结果，我们就称较短的代码比长一点的那个更简洁（注意，如果程序需要读入数据，读入数据也算进代码长度）。对于一个指定的输出，一定存在一个“最简的”代码，它是所有能输出此内容的程序代码中最短的一个。你能否编写一个程序，使得该程序能够判断任意一段代码是否是最简的？ Chaitin定理指出，上述问题是一个不可解问题，再牛的人也不可能编写出这样的程序。证明方式与大多数此类问题一样，都是采用反证加构造的方法证明的。你能想到这个证明方法吗？ [...]