[计算理论]停机问题

是否存在一个程序，可以判断任意其他程序是否会陷入死循环，也就是是否停机？

“停机问题”，可以反证出来的，也就是
假定“有一个程序可以判断所有其他程序是否停机，也就是是否陷入死循环”，
那么会得出一个矛盾的东西；最后反推出“不存在这样的判定程序”。
跟√2 是无理数的判定是类似的，假定“√2 是有理数”，然后“得出矛盾”，然后反推...

证明如下：
假定“存在一个程序 halt 可以判定任意程序 P 对于输入 I 的停机问题”，也就是
function halt(P, I)
{
正确地返回是否停机, 即 P 对于输入 I 停机返回"halt", P 不停机返回"loop";
}
毫无疑问，halt 应该可以判定 halt 对于 halt 的停机问题，而且应该返回"halt"；
------------------------------------------------------------------
我们构造一个新的程序：
function halt-x (P)
{
if (halt(P, P)=="loop") return "halt";
else if (halt(P, P)=="halt") while(true); // loop forever
}
新的程序 halt-x 是在 halt 的基础上构造出来的，如果 halt 存在，那么 halt-x
自然也存在；问题就出在如果 halt-x 去判定 halt-x，会出现神马情况 ?
------------------------------------------------------------------
(1)假定 halt-x 对于输入 halt-x 会停机，那么，让 halt-x 去测试 halt-x，执行的是
else if (halt(P, P)=="halt") while(true); // loop forever
也就是实际上，halt-x 测试 halt-x 时死循环了，并没有停机；
(2)假定 halt-x 对于输入 halt-x 不停机，那么，让 halt-x 去测试 halt-x，执行的是
if (halt(P,P)=="loop") return "halt";
也就是 halt-x 测试 halt-x 竟然停机了 ！
猪八戒照镜子——里外不是人！
所以反推，halt 这样的程序根本就不能存在！

大佬，计算理论题目可以帮忙做不，有偿