目录
一、概念
能不能写出一个程序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)触发矛盾
- 假设self_root(self_root)会结束运行
那么check_halt(self_root, self_root)返回true，self_root会进入死循环，不会结束，与假设矛盾 - 假设self_root(self_root)不会结束运行
那么check_halt(self_root, self_root)返回false，self会结束，又与假设矛盾
综上所述，check_halt不能写出，所以停机问题是无解的