可计算性理论
基础知识
计算机模型
原始递归和递归函数
可计算性
程序的编码
元计算程序
停机问题
证明. 设 h 为递归函数, 则存在程序 P 计算 h.
设计程序 Q(n) 如下. 运行程序 P(n, n), 若返回 0 则停机, 若返回 1 则进入无限循环.
令 m 为 Q 的编号. 假定 P(m, m) 返回 1, 说明 Q(m) 停机, 但是 Q(m) 停机当且仅当 P(m, m) 返回 0, 自相矛盾.
同理，假定 P(m, m) 返回 0, 说明 Q(m) 无限循环, 但是 Q(m) 无限循环当且仅当 P(m, m) 返回 1, 自相矛盾.
以此推定, h 不是递归函数. (证毕)