停机问题

图灵机

图灵机是艾伦・图灵（Alan Turing）于 1936 年提出的抽象计算模型，用于精确定义 “可计算性”。其核心组成包括：

1. 无限长纸带：划分为单元格，存储符号（如 0 / 1）。

2. 读写头：读取 / 修改当前单元格内容，并左右移动。

3. 状态寄存器：记录当前状态（如开始、接受、拒绝状态）。

4. 转移规则表：基于当前状态和读取的符号，决定下一步操作（写符号、移动方向、状态变更）。

图灵的证明

图灵通过反证法证明停机问题不可解：

1. 假设存在判定程序 H (P, I)：

输入程序 和输入 ， 输出 “停机”(Halt) 或 “不停机”(Loop)。

2. 构造自指悖论程序 D (I)：

的行为与 的预测相反：

若 输出 “停机”(Halt)，则 无限循环 (Loop)；

若 输出 “不停机”(Loop)，则 立即停机 (Halt)。

3. 矛盾产生：

若 判断 停机 (Halt) → 实际无限循环 (Loop) [矛盾]；

若 判断 不停机 (Loop) → 实际停机 (Halt) [矛盾]。

故假设不成立，不存在通用的 。