问题描述
是否存在一个过程能做这件事:该过程以一个计算机程序以及该程序的一个输入作为输入,并判断该过程在给定输入运行时是否最终能停止。问题解答
1936年图灵证明这样的过程是不存在的。证明
(反证法)
假设:存在一个这样的过程H(P,I),P为计算机程序,I为该程序的一个输入,H可以根据P和I返回true(该过程在给定输入运行时能停止)或者false(该过程在给定输入运行时不能停止)。
推出矛盾:再构造一个过程K(P),它的实现原理如下
K(P)if H(P,P)while(true);elsereturn;
如果把K最为K的输入,
1)H(K,K)返回true(程序K在输入为K时可以停止),会进入”while(true);”死循环,此时程序K并没有停止,矛盾。
2)H(K,K)返回false(程序K在输入为K时不能停止),会直接返回,此时程序已经停止,矛盾。
结论:因此不存在这样的一个过程能解决停机问题。