Halting Problem
题意
令 $\langle\cdot\rangle$ 是一个从图灵机到自然数的双射。是否存在一个图灵机 $H(\cdot,\cdot)$ 使得：
（其中 $\to$ 表示图灵机的输出）即 $H$ 判定（decide）一个图灵机关于一个输入是否停机。注意根据定义，$H$ 始终停机。
题解/证明
题解
不存在。
证明
假设存在这样的 $H(\cdot)$，定义 $D(\cdot)$ 如下：
令 $x\in\mathbb N$ 为输入，计算 $y\leftarrow H(x,x)$（注意 $H$ 始终停机，且 $y\in\{0,1\}$）。
若 $y=0$，则立刻停机；
若 $y=1$，则进入一个无限循环。
考虑 $D(\langle D\rangle)$：
若 $D(\langle D\rangle)$ 停机，则 $H(\langle D\rangle,\langle D\rangle)=1$，根据 $D$ 的定义导出 $D(\langle D\rangle)$ 不停机，矛盾；
若 $D(\langle D\rangle)$ 不停机，则 $H(\langle D\rangle,\langle D\rangle)=0$，根据 $D$ 的定义导出 $D(\langle D\rangle)$ 停机，矛盾。
因此不存在这样的 $H(\cdot)$。
这种证明方法被称为对角线法（diagonalization）。考虑一个无限大二维网格，$(\langle x\rangle,\langle y\rangle)$ 格显示了 $x(\langle y\rangle)$ 是否停机。$\langle D\rangle$ 这一行即将对角线相应元素取反得到，因此在 $D(\langle D\rangle)$ 这一格得到矛盾。
