停机问题,逻辑数学初探

停机问题是逻辑数学中可计算性理论中的一个问题,简单的说,就是判断一个程序能否不陷入死循环的问题;具体可以描述为:是否存在一个方法,对于给定的函数和入参,能判断该函数会执行有限次还是会死循环。

在往下看之前,不妨凭借经验猜测一下,这样的一个方法是否存在呢,能给出一个证明吗?

关于为什么会有人提出这样的问题,原因只能是,如果这样的一个判断停机的方法存在的话,那实在是能解决太多问题了。举个例子:对于哥德巴赫猜想(是否任意大于2的偶数都能写作两个质数之和),我们可以设计一个方法:遍历所有的大于2的偶数,然后对于每一个偶数进行判断,如果可以写作两个素数之和,则继续执行,否则就跳出循环。把这个方法用判断停机算法跑一边,如果停机算法说,这个方法只会执行有限次,那我们不就成功证伪了哥德巴赫猜想!

你可能已经凭经验得出了结果,这样的一个停机算法是不存在的,不知道你有没有想到怎么进行证明,用反证法可以很简洁地证明:

假设存在一个停机程序 P,对于方法 F,和入参 i 可以判断,H(F, i) 会执行有限次则返回 true ,执行无限次则返回 false
我们构造一个新方法 K
function K(F){
if( P(F, F) ){
while(1){ console.log( ‘我在无限循环’) } // 单纯的构造一个会无限循环的方法
}else{
return
}
}

你说我们用停机程序P 去运行一下这个 方法K(F),结果是什么呢
假如返回了 true ,就说明 K(F) 不是无限循环的,也就是说,P(F,F) 返回了 false;但是P(F,F)返回了 false,就说明了 F 方法是无限循环的,逻辑矛盾
假如返回了 false ,就说明 K(F) 是无限循环的,也就是说, P(F,F) 返回 true;同样的,根据定义 P(F,F)返回 true 说明 F 不是一个会无限循环的方法,逻辑矛盾
综上所述,停机程序 P 不存在 。