介绍停机问题相关证明。
停机问题
令H(P, I)，返回对于程序P在输入I的情况下是否可停机，假如P(I)能停机，则H停机，否则H死循环。
不妨假设U(X) = H(X, X)。现在考虑U(X)的定义：
- 如果
H(X, X)停机，则U(X)死循环。 - 如果
H(X, X)死循环，则U(X)停机。
也就是U(X)是对H(X, X)取反。
下面考虑U(U)的结果：
- 如果
H(U,U)停机，那么U(U)应该输出死循环。 - 但是考虑
H(U,U)的定义是U在输入为U的情况下是否停机，如果H(U,U)停机了，说明U(U)是可以停机的。
于是上面两者矛盾。
其实这个证明的 intuition 很简单，比如女朋友说“我觉得你对我有意见”时：
- 如果你说“你说的对”，那说明你对女朋友有意见，你就完蛋了。
- 如果你说“你说的不对”，那你居然反对女朋友，你完蛋了。
