1 历史背景
1.1 可判定性问题与希尔伯特纲领
20世纪初，德国数学家大卫·希尔伯特提出了一项雄心勃勃的计划——希尔伯特纲领，旨在为全部数学建立一个完备且一致的公理化体系。其核心问题之一是可判定性问题：是否存在一种机械化的算法，能够判断任何给定的数学命题是否成立？这一问题的探索直接催生了图灵机概念的诞生。
1.2 图灵的原著《论可计算数》
1936年，年仅24岁的艾伦·图灵发表了经典论文《论可计算数及其在判定问题上的一个应用》。在这篇论文中，他构想了一种抽象的计算模型——图灵机，用以精确刻画“什么能被机械计算”。图灵受纸带、打字机等物理设备的启发，设计了由读写头在无限长纸带上依规则移动的简单装置，并证明该模型能够执行任何直觉上可计算的任务。论文还首次提出了通用图灵机的概念，为后来的通用计算机埋下了理论种子。
1.3 与λ演算、递归函数的等价性
几乎同一时期，阿隆佐·丘奇提出了λ演算，哥德尔与克利尼等人发展了递归函数理论。图灵很快证明，图灵机能够模拟λ演算和递归函数，反之亦然，三者定义了完全相同的可计算函数集合。这一等价性被称为丘奇-图灵论题，奠定了“算法”的数学基础。
2 定义与构成
2.1 形式化定义
图灵机是一个七元组 \( (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}}) \)，其中：
- \(Q\) 为有限状态集；
- \(\Sigma\) 为输入字母表（不含空白符号）；
- \(\Gamma\) 为纸带字母表（包含空白符号 \(B\) 且 \(\Sigma \subseteq \Gamma\)）；
- \(\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}\) 为转移函数；
- \(q_0\) 为初始状态；
- \(q_{\text{accept}}\) 为接受状态；
- \(q_{\text{reject}}\) 为拒绝状态（通常 \(q_{\text{accept}} \neq q_{\text{reject}}\)）。
2.1.1 纸带（Tape）
纸带是一条两端无限延伸的带子，被划分为等宽的方格。每个方格内可以书写一个来自纸带字母表 \(\Gamma\) 的符号。初始时，输入字符串占据纸带的连续若干方格，其余方格全部为空白符号 \(B\)。
2.1.2 读写头（Head）
读写头每次对准纸带上的一个方格，能够执行三种动作：
- 读取当前方格中的符号；
- 在方格中写入一个新的符号（覆盖原有符号）；
- 向左或向右移动一个方格。
2.1.3 状态集与控制规则（Transition Function）
状态集 \(Q\) 包含了图灵机可能处于的所有内部状态（如“等待输入”“比较中”“结束”等）。控制规则由转移函数 \(\delta\) 给出：根据当前状态 \(q\) 和读取的符号 \(a\)，决定下一状态 \(q'\)、写入符号 \(b\) 以及移动方向 \(d\)（左 \(L\) 或右 \(R\)）。若无对应规则，图灵机在下一时刻停止。
2.1.4 初始状态与接受/拒绝状态
图灵机从初始状态 \(q_0\) 开始，读写头位于输入字符串最左端的方格。若经过一系列操作后进入接受状态 \(q_{\text{accept}}\)，则接受输入；若进入拒绝状态 \(q_{\text{reject}}\)，则拒绝输入。若永不进入接受或拒绝状态（即无限循环），则输入不被判定为本机可判定的。
2.2 工作步骤示例
2.2.1 符号与转移表
假设一台图灵机设计用于识别形如 \(0^n 1^n\) 的字符串（例如 “0011”），其一个简化的转移表如下（状态 \(q_0\) 为初始，\(q_4\) 为接受）：
| 当前状态 | 读取符号 | 写入符号 | 移动方向 | 下一状态 | |
|---|---|---|---|---|---|
| \(q_0\) | 0 | X | R | \(q_1\) | |
| \(q_0\) | Y | Y | R | \(q_3\) | |
| \(q_1\) | 0 | 0 | R | \(q_1\) | |
| \(q_1\) | Y | Y | R | \(q_1\) | |
| \(q_1\) | 1 | Y | L | \(q_2\) | |
| \(q_2\) | Y | Y | L | \(q_2\) | |
| \(q_2\) | X | X | R | \(q_0\) | |
| \(q_3\) | Y | Y | R | \(q_3\) | |
| \(q_3\) | B | B | — | \(q_4\) |
该规则会成对地消去一个0和一个1，直到所有0和1都被匹配。
2.2.2 模拟简单加法
考虑一台在一元表示下执行加法的图灵机：输入形如 “111+111” （即数字3+3），纸带符号集为 \(\{1, +, =\}\)。机器从左向右扫描，每次将最左侧的“1”替换为“X”并向右找到最右侧的“1”，将其替换为“1”后继续。最终得到 “111111” （即6个1）。尽管过程繁琐，但该模型展示了任何算术运算均可通过有限规则实现。
3 关键类型
3.1 确定型图灵机（DTM）
确定型图灵机是指转移函数 \(\delta\) 为单值函数：对于每一状态-符号组合，有且只有一个下一动作。任何时候，机器只会面临唯一可能的选择。这是最经典、最基础的图灵机形式。
3.2 非确定型图灵机（NTM）
非确定型图灵机的转移函数允许从同一状态-符号组合出发有多条可选规则。机器在每一步“猜测”一条合法路径，若存在某条路径最终进入接受状态，则接受输入。非确定型图灵机并不对应现实中的物理装置，而是一种重要的理论工具，用于定义NP问题等复杂度类。丘奇-图灵论题指出：NTM的计算能力与DTM完全相同（尽管效率可能不同）。
3.3 通用图灵机（UTM）
3.3.1 自指与编码思想
通用图灵机（UTM）是一种特殊的图灵机，其输入包含两部分：一台任意图灵机 \(M\) 的编码（描述其状态集、转移规则等）以及 \(M\) 的输入数据。UTM能够模拟 \(M\) 在给定输入上的运行过程。图灵在论文中展示了如何将机器自身当作数据来处理，这一“自指”思想是现代计算机能够执行任意程序的理论基础。
3.3.2 现代计算机的原型
通用图灵机本质上是一台存储程序计算机：程序（机器的描述）和数据（输入）都存储在同一条纸带上。冯·诺依曼体系中的“存储程序概念”正是受此启发。因此，今天任何通用计算机（包括智能手机）都被称为图灵完备——它们可以模拟任何图灵机（忽略内存限制）。
3.4 带特殊约束的变体
3.4.1 带任意多纸带的图灵机
某些变体拥有多条纸带，每条各有一个独立的读写头。多纸带图灵机在计算速度上可能优于单纸带机器，但理论证明它们在计算能力上等价于标准单纸带图灵机——任何多纸带机器都可以被一台单纸带机器模拟（不过可能要花费更多时间）。
3.4.2 双向无限纸带图灵机
标准定义中的纸带可以向左右两端无限延伸。另一种变体是双向无限（即左右两端均无起点）纸带，实际上与标准定义等价，因为我们可以将标准纸带“蜷曲”成双向无限而不影响计算能力。
4 能力与边界
4.1 可计算性：图灵可计算函数
一个函数被称为图灵可计算，如果存在一台图灵机，对于所有输入都能在有限步后停机，并输出正确的函数值。所有直觉上可计算的东西（如加减乘除、排序、编译器等）都被证明是图灵可计算的。无法被任何图灵机计算的函数称为不可计算的。
4.2 停机问题与不可判定性
4.2.1 对角化论证
图灵通过对角线法证明了不存在一台通用图灵机能够判定任何给定图灵机在给定输入上是否会停机。假设存在这样一台判定机器 \(H\)，则可以构造一个新机器 \(D\)：当 \(H\) 判定自身会停机时，\(D\) 就进入死循环；当 \(H\) 判定自身不会停机时，\(D\) 就停机——导致矛盾。因此停机问题是不可判定的。
4.2.2 对数学与逻辑的冲击
停机问题的不可判定性直接宣告了希尔伯特纲领中“可判定性问题”的否定答案：不存在能判定所有数学命题真伪的通用算法。这一结果与哥德尔不完备定理相互呼应，深刻揭示了形式系统的内在局限性。
4.3 与丘奇-图灵论题的关系
丘奇-图灵论题是对可计算性本质的一种断言：所有能被机械计算或由算法完成的事情，都可以在一台图灵机上实现。该论题并非一个严格的数学定理（因为它关联了“机械计算”这个直觉概念），但经受住了近百年的挑战，被广大学者接受为可计算性的定义标准。
5 应用与延伸
5.1 算法复杂度理论中的角色
5.1.1 时间与空间复杂度
图灵机成为衡量算法复杂度最底层的模型。时间复杂度定义为图灵机执行步骤数关于输入长度的函数；空间复杂度定义为纸带访问过的非空白方格数。尽管现代计算机有更精细的RAM模型，但复杂度理论的核心结果（如层次定理）大多建立在多带图灵机之上。
5.1.2 P与NP问题的背景
P（多项式时间可解）定义为那些可由确定型图灵机在多项式时间内解决的判定问题；NP定义为那些可由非确定型图灵机在多项式时间内解决的判定问题。\(P \neq NP\) 猜想是当代计算机科学最著名的未解难题，其假设至今仍悬而未决。
5.2 在计算教学中的常见梗
5.2.1 “图灵完备”的调侃（如《我的世界》红石计算机）
在编程圈和玩家社区中，凡是一个系统能够模拟任意图灵机，就会被戏称为图灵完备。例如《我的世界》中的红石电路、Excel中的公式（不含尾递归限制）、甚至是卡片游戏《万智牌》的某些规则组合，都被玩家们证明可以造出图灵机。每当有人吐槽“这个系统居然图灵完备了”，往往伴随着一种“为什么要把简单的东西搞这么复杂”的幽默感。
5.2.2 哲学家与图灵机段子
另一个经典笑话是：“哲学家说，人的大脑也是图灵机。物理学家说，不，大脑不只是图灵机。计算机科学家说，那我们先把哲学家的大脑模拟出来试试。” 实际上，图灵机是计算模型而非认知模型，这种比喻常被用于调侃哲学争论中的无限循环。
5.3 现代计算机体系结构的类比
现代计算机与通用图灵机的对应关系：
关键区别在于：真实计算机的内存是有限的，而图灵机的纸带是无限的，因此图灵机理论上可以解决任何可计算问题，而真实计算机受物理内存限制只能解决规模足够小的问题。
6 相关概念与辨析
6.1 与有限状态自动机的关系
有限状态自动机（FSA）是更弱的计算模型：它只有有限状态和有限输入，没有纸带，无法“记住”任意长的信息。图灵机可以看作在FSA的基础上增加了无限存储的纸带，因此计算能力远超FSA。FSA只能识别正则语言，而图灵机能识别所有递归可枚举语言。
6.2 与递归函数、λ演算的等势
这三者在数学上是等价的：一个函数是部分递归函数当且仅当它是图灵可计算的，当且仅当它在λ演算中可定义。这种等价性奠定了可计算性理论的统一框架。
6.3 与真实计算机的差异（无限纸带 vs 有限内存）
最重要的差异：
- 纸带无限性：图灵机假设有无限存储，真实计算机的任何内存、硬盘都有上限。
- 计算时间：图灵机不计步骤数，只要有限步完成即可；真实计算机要求时间在可接受范围内。
- 确定性：真实计算机是确定型的（忽略硬件错误），而非确定型图灵机仅存在于理论。
- 物理实现：图灵机是抽象模型，不关注功耗、并行度等现实约束；但现代计算机的设计原则仍然受其深刻影响。