本文介绍停机问题，网上有一些证明，但是细节方面有点小漏洞，我们这里优化了一下。
停机问题：是否存在一个确定的程序（或者算法）能够判定 任意一个程序， 对于任意输入 是否 能在有限时间内返回 ？
答案是否定的，下面给出一个证明：
我们把所有的程序都看成函数 ,
反证法，假设存在一个程序满足要求，我们可以记该程序为is_halting:
typedef void (*func)(char*) Program;
bool is_halting (Program program, char* input);
我们不清楚内部实现，也不需要写出，只是假设存在，该函数可以正确判定program对于input会不会停机,返回true表示会停机，返回false表示不会停机
现在，构造一个函数
void hack (char* code)
{
Program program = compile(code); //编译code源码
if (is_halting (program , code))
{
while (true);
return;
}
else
return ;
}
然后调用 :
//其中decompile是反编译的意思，把一个函数反编译为源码字符串
bool ok = is_halting(hack,decompile(hack));
那么这个函数将返回 true还是 false?
我们假设它返回true,
那么意味着 :
hack(decompile(hack)) 将会在有限时间内返回
我们设decompile(hack) = hackStr,将其代入hack的源码，
void hack (char* hackStr)
{
//先反编译再编译，则返回的是program == hack
Program program = compile(hackStr);
if (is_halting (program , hackStr)) //这根据假设
//等价于 is_halting(hack, hackStr) ,并且将返回true，死循环
{
while (true);
return;
}
else
return ;
}
根据以上分析，hack(decompile(hack)) 永远不会返回，矛盾。
我们再假设返回false
这意味着:
hack(decompile(hack))将永远不会返回
还是代入hack源码:
void hack (char* hackStr)
{
//先反编译再编译，则返回的是program == hack
Program program = compile(hackStr);
if (is_halting (program , hackStr)) //这根据假设
//等价于 is_halting(hack, hackStr) ,并且将返回false，
{
while (true);
return;
}
else
return ; //程序会走到这里并且返回
}
可以看到hack(decompile(hack))返回了，矛盾。
综上，无论如何都会产生矛盾，注意，我么在证明过程中
只是假设了返回值为 void，输入为char*的程序，也就是对于这一类程序我们证明了不存在满足要求的算法，那么既然对这一类程序都不存在，自然对于任意程序而言，就更不存在了。
至此，我们就证明了图灵停机问题。
