图灵机

Turing machine

通过有限控制、可读写纸带和移动读写头刻画一般算法计算能力的模型。

领域: 自动机与可计算性
条目类型: 模型

形式陈述

标准确定性单带图灵机可同时视为三种推广模型的特例：在非确定性图灵机中每个配置只保留一个选择，在预言机图灵机中从不调用预言机，在多带图灵机中只使用一条工作带。这里陈述的是语法包含；这些模型在可计算语言层面仍可能等价而在复杂度上有模拟开销。

以下选择双向无限纸带，以避免额外规定左边界行为。确定性单带图灵机可写为

M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\mathrm{acc}},q_{\mathrm{rej}}),

其中 $Q,\Gamma$ 为有限集， $q_0,q_{\mathrm{acc}},q_{\mathrm{rej}}\in Q$ 且 $q_{\mathrm{acc}}\ne q_{\mathrm{rej}}$ ；空白符 $\sqcup\in\Gamma$ ，输入字母表满足 $\Sigma\subseteq\Gamma\setminus\{\sqcup\}$ ，并且转移函数

\delta:(Q\setminus\{q_{\mathrm{acc}},q_{\mathrm{rej}}\})\times\Gamma \to Q\times\Gamma\times\{L,R\}.

纸带内容可写成函数 $t:\mathbb Z\to\Gamma$ 。记有限非空白纸带的集合为

\Gamma_{\sqcup}^{(\mathbb Z)} = \left\{t\in\Gamma^{\mathbb Z}:\{j\in\mathbb Z:t(j)\ne\sqcup\}\text{ 是有限集}\right\}.

配置是三元组

(q,t,i)\in Q\times\Gamma_{\sqcup}^{(\mathbb Z)}\times\mathbb Z,

其中 $q$ 是当前状态， $i$ 是读写头位置。对输入字 $w=w_0\cdots w_{n-1}\in\Sigma^*$ ，初始配置把 $w_j$ 写在位置 $j$ ，其余位置填 $\sqcup$ ，读写头位于位置 $0$ ，状态为 $q_0$ ；空输入时位置 $0$ 仍为空白。

若 $\delta(q,t(i))=(q',a,D)$ ，一步配置转移会把位置 $i$ 改写为 $a$ ，把状态改为 $q'$ ，并按 $D\in\{L,R\}$ 将头移动到 $i-1$ 或 $i+1$ 。进入 $q_{\mathrm{acc}}$ 或 $q_{\mathrm{rej}}$ 后停机。机器识别的语言为

L(M)=\{w\in\Sigma^*:M\text{ 从 }w\text{ 的初始配置出发最终进入 }q_{\mathrm{acc}}\}.

图灵机一步转移中的读、写、移动与状态变化 — 蓝色标出读写头的当前位置和控制状态；转移把一改写为零、状态从 q 变为 q'，再将读写头右移一格。

若 $w\notin L(M)$ ，识别器可以拒绝，也可以无限运行；若机器对每个输入都停机，并在成员上接受、非成员上拒绝，则称它判定该语言。

直觉

图灵机把算法压缩为三个要素：有限控制、可读写的无界纸带，以及一次只访问一个格子并做局部修改的转移规则。配置是计算在某一瞬间的完整快照，一步语义则把有限转移表真正解释为运行。纸带的无界只表示可以按需要继续使用新格子，不代表某次有限计算会访问无限区域；运行 $T$ 步至多移动 $T$ 次，因此只可能接触有限多个格子。

例子与边界

一台判定回文的机器可以反复标记最左未处理符号，移动到最右未处理符号比较，再返回继续；虽然效率不高，但每个动作都能写成有限转移表。对输入 0110 它最终接受，对 0100 在比较外层字符后拒绝。

改用单向无限带、允许“停留不动”、增加有限条带或引入非确定性，通常只改变描述便利性、编码与效率，不改变可计算语言类；讨论精细时间复杂度时，模拟开销仍须单独计算。接受、拒绝和不停机是三种不同结果：可识别性只要求成员最终被接受，可判定性还要求非成员最终被拒绝。

推论与应用

输入字、有限状态、纸带符号与转移函数先定义机器本身；机器接受哪些输入字，随后才导出它识别的形式语言。把对象层和语言层分开，可以避免把“某台机器停机”与“某个语言可判定”混成同一句话。

Church–Turing 论题把图灵机视为有效计算的标准形式化之一。通用图灵机进一步说明，机器描述本身可以编码成输入，由另一台机器解释执行；程序与数据之间因此没有不可跨越的形式边界。

若把非确定机器的可访问带区限制为输入长度的常数倍，就得到线性有界自动机，其语言刻画见CSL–LBA 等价定理。可计算函数、可判定性、可识别性和资源复杂度类，则分别在图灵机模型上增加输出、全停机或资源上界要求。

参考资料

Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013, Chs. 0–10。
Alan M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, 1936, Full paper。

关系图谱84 个相邻概念 · 2 类关系

正在载入交互图谱…

前置三跳
前置二跳
前置一跳
当前条目
后续一跳
后续二跳
后续三跳

文字版关系按与当前条目的最短距离分组

分类位置

上位 / 更一般

下位 / 直接特例

通用图灵机模型

停机问题不可判定性

“图灵机的停机问题是构造其他不可判定性结果的标准源头：通过映射归约，可把停机行为编码进等价性、可达性或其他程序语义性质，证明它们不可判定。Rice 定理进一步把这种现象概括为所有非平凡语…”

Word-RAM 模型

“与顺序带上的图灵机相比，Word RAM 允许一步访问任意已寻址单元；与不限制整数大小的单位成本 RAM 相比，它又用固定字宽约束每步能处理的信息。涉及溢出时，算术可规定为模 $2^w$，或…”

Post 对应问题

“PCP 是从图灵机计算历史到字符串匹配的经典编码目标，也是证明文法歧义、CFG 交非空、矩阵与字符串系统不可判定性的通用中介；这些证明通常使用映射归约。它与形式语言理论的联系尤其紧…”

预言机图灵机

“预言机模型扩展图灵机，Turing 归约用它刻画可自适应多次查询的计算，并与映射归约的一次性翻译形成对照。复杂度理论借它定义 $P^A,NP^A$ 等相对类、识别证明技术的相对化障碍，…”

通用图灵机

2 处

“通用机建立在图灵机可有效编码的事实上，使“程序分析另一个程序”得到形式化。程序编号与可接受编号把这种解释能力组织成有效枚举，$s$ $m$ $n$ 定理把部分实参固化进新程序代码，Kle…”

“固定一种可有效解析的编码。通用图灵机 $U$ 接收 $\langle M,w\rangle$，其中 $M$ 是一台图灵机、$w$ 是其输入，并逐步模拟 $M$ 在 $w$ 上的运行：若 $M…”

枚举器

“枚举器刻画递归可枚举集合，并与可识别语言给出等价描述：语言可由图灵机识别，当且仅当存在机器枚举其全部成员。这个等价把半判定过程转换为生成过程，也解释了证明搜索、程序生成、程序行为枚举…”

非确定性图灵机

“NTM 为 NP、NPSPACE 和证书验证提供统一模型，把组合搜索中的“猜测—验证”模式转化为精确复杂性定义。图灵机的非确定版本与确定版本在可识别性上等价，却导出 NP 这样的复杂度类；再…”

多带图灵机

“多带模型用于清晰描述通用机、字符串算法和复杂性类，也常用于简洁定义可计算函数和时间复杂度，因为算法可自然分解为多个工作带。它与单带图灵机的等价支撑模型稳健性，而模拟的多项式开销说明…”

映射归约

“对形式语言 $A\subseteq\Sigma^$、$B\subseteq\Gamma^$，若存在全函数 $f:\Sigma^\to\Gamma^$，并且某台图灵机对每个输入 $x$ 都停机…”

时间复杂度

“粗粒度复杂度理论常以图灵机统一编码与步数，再由预算函数定义确定性时间类。合理模型之间通常存在多项式开销的模拟，所以 P、EXP 等多项式或指数尺度的类别较稳定；线性、近线性和常数因子结论则仍…”

确定性时间复杂性类

“固定有限字母表 $\Sigma$ 和标准确定性多带图灵机模型。对函数 $t:\mathbb N\to\mathbb N$，定义”

空间复杂度

“固定一台带只读输入带和有限条可读写工作带的图灵机。对一次运行 $\rho$，记第 $j$ 条工作带上曾被读写头扫描过的格子集合为 $V j(\rho)$，定义”

可识别语言

“语言 $L\subseteq\Sigma^ $ 称为图灵可识别语言，若存在图灵机 $M$ 满足：当 $w\in L$ 时，$M$ 最终接受；当 $w\notin L$ 时，$M$ 可以拒绝，…”

可判定语言

“语言 $L\subseteq\Sigma^ $ 称为可判定语言，当且仅当存在图灵机 $M$，对每个输入 $w$ 都在有限步内停机，并且 $w\in L$ 时接受、$w\notin L$ 时拒…”

可计算函数

“图灵机、递归函数与 λ 演算对有效计算给出等价刻画，并支撑Church–Turing 论题。在具体数学结构上谈“可计算”时，还需随结构一起给出有效表示；仅声明抽象对象之间存在一个集合论函数，…”

电路族一致性

“一致性把布尔电路族与图灵机的统一算法联系起来。P/poly专门承担非一致多项式规模与 advice 的定义；AC⁰再叠加常深、无界扇入和门基，并分别标注 uniform 或 nonunifo…”

Church–Turing 论题

“加法、Euclid 算法和有限字符串搜索都能编成图灵机，也能写成 λ 项或递归方程；模型之间的模拟说明它们在可计算性上没有差别。反过来，停机集合的特征函数不存在图灵机实现，因此论题把它判为…”

形式陈述 ​

反向链接

形式陈述