一、概念

能不能写出一个程序check_halt，传入程序program和参数params，返回这个程序是否会结束？

比如，求和函数sum计算[1,2]，check_halt(sum, [1, 2])应该返回true

虽然我们特别想要这样的功能，让我们提前做灾备工作，避免重大的程序风险，但是这是一个不可解的问题，可以用反证法来证明。

什么是反证法
就是先假设“命题的否定形式”成立，再根据假设推导出矛盾的结果驳倒假设。

举个例子
证明“不存在最大的正整数”。

这个问题其实问出来，一般人会觉得你无聊吃饱了撑着，只会傻不拉几的说：“这TM不是常识吗？这还用证明？”
No，科学是要证明的，你觉得正常的东西不一定就是可验证的真理。

我们用反证法证明一下：

1. 假设“存在最大的正整数”，这个数为M
2. 那么M+1比M大，这与假设矛盾

所以，“不存在最大的正整数”

二、证明

1. 假设能写出停机函数check_halt(program, params)

如果能停止，返回true；如果不能停止，返回false

以下是伪代码

def check_halt(program, params):
    return True Or False

2. 定义一个调用了check_halt的会触发死循环的函数self_root

如果check_halt(program, program)返回true，就进入死循环；
如果check_halt(program, program)返回false，就返回0

def self_root(program):
    if check_halt(program, program):
        while True:
            # 如果停机就进入死循环
            pass
    else:
        return 0

注意：check_halt的两个参数都是program

3. self_root(self_root)触发矛盾

1. 假设self_root(self_root)会结束运行
   那么check_halt(self_root, self_root)返回true，self_root会进入死循环，不会结束，与假设矛盾
2. 假设self_root(self_root)不会结束运行
   那么check_halt(self_root, self_root)返回false，self会结束，又与假设矛盾

综上所述，check_halt不能写出，所以停机问题是无解的

计算机中的不可解问题——停机问题

原文：https://www.cnblogs.com/chenqionghe/p/15001498.html