看黑书介绍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程序会正常退出，那么就让程序进入一个死循环，否则立即退出程序。矛盾产生。
//简直是在挑战表达力极限
//做人要厚道，转帖请注明出处
您的表达还是很清楚的嘛
那个反证法太美妙了…
最后一段懂了,很不错的反证…[GoodLuck]
图灵为何不喜欢MM呢?[tea]
证法的确相当经典，ps这题作为NOIP2007提高组初赛题考了。
能否等价为：
输入一段代码A和一个针对A的输入a，能否编程B判断A（a）是否是死循环。
回复：对
我有一个绝妙的程序B，可惜这里空太小写不下了。
终于有个上网的机会，来看看你的地盘。
自我感觉这是个在你给出的BUG程序下会成为悖论的问题。简称program bug 为悖论程序，呵呵。
学数学蛮好玩。我们最近教到叉乘了，还记得在bsy的时候，你来给我们讲了叉乘，那天晚上我在寝室熬夜整理笔记到将近两点。咳……信息竞赛的任何一个回忆的片段总能给我很深的感慨，不知道你是不是呢？
[loo]
那啥。。。我一直想知道。。。黑书是什么？
回复：算法艺术与信息学竞赛
我觉得关于问题的表述
应该换成一种更清晰的不易让人误解的方式
比如：能否存在一种算法，对任意一个给定程序A，以及任意一个针对A的输入，判断出A是否能够终止。
有趣的证明
我不认同这个反证法，这个证明带有自指性（读入自己这段程序）。就像集合论中的某些悖论一样，钻了定义的空子。
@凌晨海风
自指性很正常吧。
如果不认同这个反证法，那可以看看哥德尔不完备性定理以及康托对角线删除方法的证明。
啊。。。我想问。。。你这些东西是在哪找的啊。。。好强啊
类比一下，假设存在上帝，而你现在在梦中。
如果你认为你马上会从梦中醒来，那么上帝就不让你醒来，所以你的‘认为’是错的；如果你认为你不会醒来，那么上帝就让你醒来，所以你的‘认为’依然是错的。因此，无论你怎么认为，上帝都可以判决你的认为是错的。
停机问题于此类似，只不过这里的上帝是程序员，代码是梦中的人。可见停机问题是荒谬的
停机问题与表达式（符号）的任意性：
我把（code，表达式，符号，字母）暂时视为通一个东西。
我们可以任意的输入一段代码，例如“Program Bug”，又比如：
a=”a就是非a”
假定这里的a是同一个东西，那么就会出现‘悖论’：a为真，则a为假;a为假，则a为真。为什么会这样呢？因为它给出的表达式“a就是非a”本身就违反了矛盾律。
我说的这句话是假话；语言结构：
假设“这句话”=a
那么 a=”a是假话”，即a=”a并非a”
反证法确实厉害……
运行BUG程序,会在无限时间之后返回一个类似:此题有限时间内不可解 的东西
悖论就是在没有限制条件下自相矛盾的事，如同理发师说“我将给所有不能自己剪头发的人理发”一样，只有对象是理发师自己时才会出现错误。只要加上一条说明“除了自己以外”就没有问题了。
那么这个证明会不会也是这样，用反证法来证明只是一个对于本身而言的逻辑上的错误，只要在使用Halting函数时避免递归调用，就不会有矛盾产生。
¿Sí?
地下室说的比较好理解。
不明白最后的自我验证程序的原理，为什么是不停机时推出repeat,停机时继续执行？ 既然是判断是否停机，那么当停机时（为true时）就推出并返回真值不就好了吗？
概念的错误，怎么不可解，只不过形式是无穷嵌套，是问题本身的平凡解，不是不可解，是偷换概念，显然问题的非平凡解才是要考虑的，我觉得大家对语言的使用带有歧义性。
和集合论的不存在一个包含所有集合的集合证明有点像
无非是说，“无所不能”的上帝却不能创造出一个连他也搬不动的石头来罢了
楼层: 25楼 | 2010-08-12 17:51 | victor_chia 说：
无非是说，“无所不能”的上帝却不能创造出一个连他也搬不动的石头来罢了
如果同意上帝无所不能，那么是否同意上帝可以是矛盾的？上帝可以是游离于人类逻辑之外的？
很赞!上帝可以自我矛盾,那么上帝是就像正电子和负电子的集合,不讨论上帝时上帝存在,讨论上帝的时候上帝是不存在.因为没有上帝了
MAIN{
IF(PRESULT(*MAIN,0,NULL)!=LOOPEN)WHILE(1);}
我也觉得，bug程序对应的输入 是什么啊？
传说中的自指啊，怎感觉貌似好多问题都是自指给否定了
以子之矛攻子之盾。很好的矛盾啊。。
其实，我自己在想，假如我们把这个halting probleam类比到人脑，那么会不会有什么可取之处呢，对于解决这个停机问题来讲
也许正是因为人脑可以控制自己不去进行这个工作，把这个问题停下来，所以不会有这个奇怪的问题吧。。。表达有点奇怪。。。
(no chinese IME at this time)
is it basicly jsut a paradox?
并不完全认可这个反证法。
最后BUG 可以不用输入BUG程序本身吧 可以 Bug input 也可以吧
典型的理发师问题，集合论里的自指。个人觉得在哲学里这就是一个判断范畴定义的问题，你在做判断前，必须指定判断的过程中不得出现判断本身，因为后者范畴大于前者。用数学语言来说这就是公设。有这个公设，哲学里的判断才存在，否则就像“我正在说的话是假话”一样出悖论。当然我们允许没有公设，非欧几何也有其意义。
首先，可定义并不就意味着一定存在！因为我们也可以定义“上帝”。实际上，塔尔斯基就是用“A=非A”来定义空集的，也即根本不存在满足“A=非A”的A！
Program Bug;
var
code:input_type;
begin
get(code); //读入code
if halting(bug,code) then repeat until false
else halt;
end.