SimLabs

📖 标准介绍

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

核心组件：

• 纸带：一条无限长的纸带，被划分为连续的小方格。每个方格可以记录一个来自有限字母表的符号（例如 0、1，以及一个特殊的“空白”符号 B）。纸带的无限长提供了理论上无上限的存储空间。
• 读写头：一次对准一个方格，能执行三种基本操作：读取当前方格中的符号、写入一个新符号（覆盖原有符号，包括擦除为空白）、左移或右移一格到相邻方格。
• 状态寄存器：记录机器当前的“状态”，来自一个有限的状态集合。其中包含一个特殊的起始状态（机器开始运行时的状态）和一个或多个停机状态（进入后机器立即停止运行）。
• 转移规则（程序）：一个有限的规则表，每条规则的格式为：(当前状态, 当前读到的符号) → (要写入的符号, 移动方向, 下一个状态)

机器运行时，每一步都根据当前状态和读写头所指的符号查找规则，然后执行“写入→移动→更新状态”。如果某一步进入停机状态，或找不到匹配的规则，机器便停止，此时纸带上的内容即为计算结果。

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

💬 通俗介绍

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

图灵机本质上是一个抽象的计算模型，你可以把它想象成一个人拿着笔和橡皮，在一条被划分为无数小格子、向两端无限延伸的纸带上工作。这个人的“当前心情”代表机器的有限内部状态，而他手中的笔则充当读写头，一次只能聚焦于纸带上的一个格子。他必须严格遵守一本固定的“规则手册”（即转移函数），根据当前所处的“心情”和眼前格子里的符号，机械地执行三个动作：擦除旧符号并写下新符号、将注意力向左或向右移动一格，以及切换到下一个“心情”。他就这样不断重复“看、写、移、换心情”的简单循环，直到触发手册中的停止条件。正是这种将复杂计算拆解为最基本机械动作的机制，用最简单的组件刻画了所有可计算过程的边界，从而奠定了现代计算机的理论基础。

💬 图灵机解决了什么问题？

1. 给出了“计算”的精确数学定义：它将模糊的“算法”概念彻底机械化，证明任何有明确步骤的问题都可被图灵机计算，奠定了计算机科学的基础。

2. 提出了“通用图灵机”：一台机器通过读取不同的“规则手册”（即软件），就能模拟任何其他图灵机。这是“硬件与软件分离”的思想源头，也是冯·诺依曼架构的先声。

3. 划定定了“可计算”的理论边界：图灵机证明了“停机问题”不可判定——不存在通用算法能预判任意程序是否会死循环。这打破了用机械方法解决所有数学问题的幻想，也引出了“丘奇-图灵论题”：任何直觉上可计算的东西，图灵机都能算（迄今未被推翻）。

💬 图灵机的缺陷（理论局限）？

1. 无法解决“停机问题”：不存在一个通用的图灵机，能判断任意给定的程序和输入是否会在有限步内停止。

2. 效率不现实：图灵机的“纸带”是顺序读写的，实际解决问题极慢（比如排序可能需要 O(n^2) 步移动），不能直接代表现实计算机的“可行”计算（即时间/空间复杂度）。

3. 无限纸带只存在于理论：现实计算机内存有限，本质上是有限自动机，但通常用图灵机近似。