图灵机（Turing Machine）

艾伦·图灵提出的理论计算模型，定义了"可计算"的概念，是现代计算机科学的理论基础。

🧮 标准公式

标准单带确定型图灵机通常定义为一个七元组，其中每一项都对应机器运行时不可缺少的一部分：

$$M=\langle Q,\Sigma,\Gamma,\delta,q_0,B,F\rangle$$

它的核心是转移函数。给定当前状态和读写头看到的纸带符号，机器必须唯一地决定写入什么符号、读写头如何移动、以及进入哪个新状态：

$$\delta:(Q\setminus F)\times\Gamma \rightharpoonup Q\times\Gamma\times\{L,R,N\}$$

这里的 $\rightharpoonup$ 表示“部分函数”：如果某个 $(q,a)$ 没有定义转移，机器就在该配置上停机。$L$ 表示左移，$R$ 表示右移，$N$ 表示不移动。

$Q$ 状态集合：机器内部可能处于的有限状态，如 $q_0,q_1,\text{ACCEPT}$。
$\Sigma$ 输入字母表：允许出现在原始输入中的符号集合，并且不包含空白符 $B$。
$\Gamma$ 纸带字母表：纸带格子可能保存的符号集合，满足 $\Sigma\subseteq\Gamma$ 且 $B\in\Gamma$。
$\delta$ 转移函数：描述一步计算规则：$\delta(q,a)=(q',b,D)$。
$q_0$ 初始状态：机器开始运行时的状态，必须满足 $q_0\in Q$。
$B$ 空白符：表示纸带上尚未写入有效内容的空格，且 $B\notin\Sigma$。
$F$ 终止状态集合：机器进入这些状态后停止，常细分为接受状态和拒绝状态。
配置：一次运行瞬间可写作 $\alpha q\beta$，表示状态 $q$、读写头位置和纸带内容共同组成的完整快照。

📖 标准介绍

图灵机是英国数学家艾伦·图灵（Alan Turing）于1936年提出的抽象计算模型。它由一条无限长的纸带、一个读写头和一个状态寄存器组成。

核心组件：

  • 纸带：无限长，分成格子，每个格子可以写符号
  • 读写头：可以读取、写入、左移、右移
  • 状态：机器当前的内部状态
  • 转移规则：根据当前状态和读取的符号决定下一步

更严格地说，单带确定型图灵机可写成七元组： $M=\langle Q,\Sigma,\Gamma,\delta,q_0,B,F\rangle$。下面的模拟器按这个数学定义执行，而不是只播放固定动画。

💬 通俗介绍

想象一个人拿着笔和橡皮，在一条无限长的纸带上工作。他按照一本规则手册，根据当前看到的符号和自己的"心情"（状态），决定写什么、往哪走、下一个"心情"是什么。这就是图灵机！

🎮 标准单带确定型图灵机模拟器

这里不再是固定脚本动画，而是按转移函数逐步执行： 读当前格、写符号、移动读写头、进入下一状态。纸带使用整数坐标按需展开，向左和向右都视为无限。

DTM / 单带 / 双向无限纸带

机器定义

格式：当前状态 读取符号 -> 写入符号 移动方向 下一状态。移动方向支持 L、R、N（或 S / - 表示不动），# 后为注释。
等待装载机器定义。

运行控制台

当前状态q0
读写头坐标0
读取符号_
步数0
结论未运行
装载后即可单步或自动运行。
非空纸带内容（去掉两侧空白）
最后一次转移 尚未执行

七元组视图

转移规则表

当前状态 读取 写入 移动 下一状态

执行日志

等待装载机器定义...

🧠 理论意义

定义了"可计算"的概念，证明了某些问题是不可计算的（停机问题）

💻 实践影响

现代计算机的理论基础，所有编程语言的计算能力都等价于图灵机

🎯 Church-Turing论题

任何可以被算法解决的问题都可以被图灵机解决