用户:LynChern/Sandbox：修订间差异

2026年4月11日 (六) 01:05的版本

模板:Distinguish/Confusion 一个图灵机是由艾伦·图灵设计的一种假想机器，用于执行计算。它由一个有限状态自动机（通常称为其“控制机制”或程序）连接到一个无界磁带组成，磁带可以左右移动，从中可以读取符号，并可以在其上写入符号。

一个通用图灵机是一种图灵机，它可以被给予以某种形式编码的任何任意图灵机的描述，在其磁带上初始化，并且有限状态机以这样的方式操作描述，从而模拟被描述的机器。通用机得名于它们能够计算任何可计算序列的事实。

图灵机在计算上具有重要意义，因为尽管许多计算模型已被证明只能解决给定图灵机可以解决的计算问题的一个子集，但尚未有任何可定义为算法集合的计算系统被证明能够解决图灵机不能解决的计算问题。

此外，尚未设计出任何通用图灵机明显无法执行的明确定义算法。这导致了丘奇-图灵论题，它（粗略地）指出图灵机是（我们直观上认为的）有效可计算算法的机械体现。也就是说，图灵机可以进行任何可能精确定义算法的计算。

自从艾伦·图灵的论文中发明图灵机以来，许多其他系统已被证明与它们等价。（事实上，其中一些系统，如λ演算、组合子逻辑和波斯特规范系统，早于图灵机。）通过这种方式，图灵机定义了一个等价系统的计算类别；这些系统被称为图灵完备。

由于所有这些原因，证明一个深奥编程语言是否等价于图灵机通常是一个有趣和/或有价值的任务。

形式上，图灵机通常以元组格式描述， $(Σ, σ_{0}, Q, q_{1}, q_{h}, f)$ ，包括：

符号集合 $Σ$
空白符号 $σ_{0}$
状态集合 $Q$
起始状态 $q_{1}$
停机状态 $q_{h}$
转移函数 f:Q×Σ→Σ×D×Q
- 其中 $D$ 通常是 ${l e f t, c e n t e r, r i g h t}$ 或 ${l e f t, r i g h t}$
- 对于 $q_{h}$ 未定义
- 接受当前状态和当前观察到的符号，然后产生一个新符号来覆盖观察到的符号、一个移动方向以及要转换到的下一个状态

以这种方式描述的图灵机可以被视为一个部分函数 $Φ : Σ^{*} ⇀ Σ^{*}$ ，它接受一个预设的有限长度符号磁带，并（通过机器的变异操作）在磁带上产生一个新的有限符号串。由于集合 $Σ^{*}$ 是可数无限的，图灵机的部分函数也可以写为 $f : ℕ ⇀ ℕ$ ，其中使用自然数和符号串之间的某种编码方案。该函数是部分的，因为机器可能无限循环而不是产生答案。对于在输入磁带 $x$ 上停机的图灵机 $M$ ，记号为 $M (x) ↓$ ，而对于在该输入上不停机的图灵机，记号为 $M (x) ↑$ 。

停机问题

关于图灵机的一些最著名的事实涉及停机状态。机器是否会从给定的起始配置进入停机状态？我们有两个重要结果。

定理。 如果一个图灵机停机，那么在ETCS和ZF中存在证明它停机的证明。

定理（图灵机停机的不可判定性）。 没有有效程序能在ETCS或ZF中产生证明，证明给定图灵机在给定输入磁带上停机。

通俗地说，图灵机是否停机（在选定的输入上）是一个具体的、客观的、野蛮的事实；相应的证明仅仅是机器执行的历史。然而，标准集合论并不总是能够证明这样的事实。根本问题在于强集合论的哥德尔不完备性；当集合论能够编码数论时，它也能够引入哥德尔关于数论不完备性的所有推理。

另一个非正式的教训是，可计算是图灵机做什么，而不是图灵机是什么。关于图灵机的事实可能不是可计算的！

变体

外部资源

参见维基百科上的图灵机
图灵机语言 - 一个用Python编写的图灵机解释器
可视化图灵机 - 动画图灵机模拟器
论可计算数及其在判定问题上的应用 - 图灵介绍其机器的论文
Boolos, G. 和 Jeffrey, R., 可计算性与逻辑, 第二版, 剑桥: 剑桥大学出版社, 1980.
在线图灵机模拟器
另一个模拟器
又一个模拟器
图灵机模拟语言

@@ 第1行： / 第1行： @@
-'''有限状态自动机'''，简称 FSA，是一种简单的假想机器。它有时也被称为''有限状态机''、''有限自动机''或''有限状态转换器''。
+{{Distinguish/Confusion|Turing-machine}}
+一个'''图灵机'''是由[[Alan Turing|艾伦·图灵]]设计的一种假想机器，用于执行计算。它由一个[[finite-state automaton|有限状态自动机]]（通常称为其“控制机制”或程序）连接到一个[[unbounded|无界]][[tape|磁带]]组成，磁带可以左右移动，从中可以读取符号，并可以在其上写入符号。
-==定义==
+一个[[universal Turing machine|通用图灵机]]是一种图灵机，它可以被给予以某种形式编码的任何任意图灵机的描述，在其磁带上初始化，并且有限状态机以这样的方式操作描述，从而模拟被描述的机器。通用机得名于它们能够计算任何可计算序列的事实。
-（注意：FSA 用于各种目的——识别形式语言、建模系统的动态行为、表示视频游戏中的实体等——这些应用通常使用适合其问题域的略微不同的定义。我们将尝试在本页面上使用非常通用的定义，然后描述常见的变体。）
+图灵机在计算上具有重要意义，因为尽管许多[[:Category: Computational models|计算模型]]已被证明只能解决给定图灵机可以解决的计算问题的一个子集，但尚未有任何可定义为算法集合的计算系统被证明能够解决图灵机不能解决的计算问题。
-在任何给定时间，FSA 可以处于有限数量的''状态''中的任何一种。它从外部源一个接一个地接收''输入信号''。当每个信号被接收时，FSA 根据输入信号和 FSA 的当前状态''转换''到另一个（可能相同的）状态。当没有更多输入信号需要处理时，可以认为 FSA 处于一个''最终状态''。
+此外，尚未设计出任何通用图灵机明显无法执行的明确定义算法。这导致了[[Church-Turing thesis|丘奇-图灵论题]]，它（粗略地）指出图灵机是（我们直观上认为的）有效可计算算法的机械体现。也就是说，图灵机可以进行任何可能精确定义算法的计算。
-FSA 也可以被认为会产生''输出信号''，这些信号指向某个外部接收器。它可能在特定转换发生时（如在 Mealy 机中）或达到特定状态时（如在 Moore 机中）产生这些信号。（这两种情况是等价的，除了所需的状态数量。）输出信号可能与输入信号性质相同或不同。
+自从艾伦·图灵的论文中发明图灵机以来，许多其他系统已被证明与它们等价。（事实上，其中一些系统，如[[lambda calculus|λ演算]]、[[combinatory logic|组合子逻辑]]和[[Post canonical system|波斯特规范系统]]，早于图灵机。）通过这种方式，图灵机定义了一个等价系统的[[computational class|计算类别]]；这些系统被称为[[Turing-complete|图灵完备]]。
-FSA 可以被认为能够在每次转换或状态时产生多个输出信号。或者，某些转换可能根本不依赖于输入信号，自动移动到新状态。（这两种情况也是等价的，除了所需的状态数量。）
+由于所有这些原因，证明一个[[esoteric programming language|深奥编程语言]]是否等价于图灵机通常是一个有趣和/或有价值的任务。
-所有状态对所有可能的输入信号都有转换。如果输入信号被认为是“非法的”，它不能被拒绝——FSA 仍然必须转换到某个状态。这通常通过拥有一个''非接受状态''来处理，所有状态在接收到“非法”输入信号时都转换到该状态，并且 FSA 永远无法“逃脱”该状态。这个状态通常从图中省略，只是隐含的。
+形式上，图灵机通常以元组格式描述，<math>(\Sigma, \sigma_0, Q, q_1, q_h, f)</math>，包括：
+* 符号集合 <math>\Sigma</math>
+* 空白符号 <math>\sigma_0</math>
+* 状态集合 <math>Q</math>
+* 起始状态 <math>q_1</math>
+* 停机状态 <math>q_h</math>
+* 转移函数 <math>f: Q \times \Sigma \rarr \Sigma \times D \times Q</math>
+** 其中 <math>D</math> 通常是 <math>\lbrace left, \ center, \ right \rbrace</math> 或 <math>\lbrace left, \ right \rbrace</math>
+** 对于 <math>q_h</math> 未定义
+** 接受当前状态和当前观察到的符号，然后产生一个新符号来覆盖观察到的符号、一个移动方向以及要转换到的下一个状态
-FSA 的行为可以是确定性的或非确定性的；一个非确定性的 FSA 可以同时处于多个状态；如果存在''某种''选择路径导致接受状态，它就接受输入。对于识别器，有一种算法可以消除非确定性，但通常会大大增加状态数量（最多 2<sup>''n''</sup>，其中 ''n'' 是非确定性自动机中的状态数）。
+以这种方式描述的图灵机可以被视为一个[[partial function|部分函数]] <math>\Phi: \Sigma^{\ast} \rightharpoonup \Sigma^{\ast}</math>，它接受一个预设的有限长度符号磁带，并（通过机器的变异操作）在磁带上产生一个新的有限符号串。由于集合 <math>\Sigma^{\ast}</math> 是可数无限的，图灵机的部分函数也可以写为 <math>f: \mathbb{N} \rightharpoonup \mathbb{N}</math>，其中使用自然数和符号串之间的某种编码方案。该函数是部分的，因为机器可能无限循环而不是产生答案。对于在输入磁带 <math>x</math> 上停机的图灵机 <math>M</math>，记号为 <math>M(x)\darr</math>，而对于在该输入上不停机的图灵机，记号为 <math>M(x)\uarr</math>。
-==描述==
+== 停机问题 ==
-FSA 可以描述为转换表，或者更直观地，描述为有向图，其中顶点是状态，边是从状态到状态的转换。边用转换发生的输入信号标注。输出信号可以标注在边上、顶点上，或两者上。
+关于图灵机的一些最著名的事实涉及停机状态。机器是否会从给定的起始配置进入停机状态？我们有两个重要结果。
-==语言识别==
+'''定理。''' 如果一个图灵机停机，那么在[[wikipedia:Elementary theory of the category of sets|ETCS]]和[[wikipedia:Zermelo–Fraenkel set theory|ZF]]中存在证明它停机的证明。
-为了识别一个字符串是否属于形式语言（如[[regular expression|正则表达式]]）的一部分，信号是字符串的符号，最终状态决定 FSA 是否“接受”该字符串——即，与 FSA 关联的形式语言是否包含该字符串。这种 FSA 通常不产生输出，而只是以“接受”或“拒绝”状态结束，被称为'''接受器'''或'''识别器'''。
+'''定理（图灵机停机的不可判定性）。''' 没有有效程序能在ETCS或ZF中产生证明，证明给定图灵机在给定输入磁带上停机。
-FSA 足够强大以识别某些字符串集合，但不能识别其他。例如，可以构造一个 FSA，它可以告诉你一个字符串是否以开括号开头并以闭括号结尾，无论该字符串有多长。然而，没有 FSA 可以告诉你这些括号是否正确嵌套（正则表达式也不能）——为此，你需要一个[[push-down automaton|下推自动机]]。
+通俗地说，图灵机是否停机（在选定的输入上）是一个具体的、客观的、野蛮的事实；相应的证明仅仅是机器执行的历史。然而，标准集合论并不总是能够证明这样的事实。根本问题在于强集合论的[[wikipedia:Gödel's incompleteness theorems|哥德尔不完备性]]；当集合论能够编码数论时，它也能够引入哥德尔关于数论不完备性的所有推理。
-==计算能力==
+另一个非正式的教训是，[[computable|可计算]]是图灵机''做''什么，而不是图灵机''是''什么。关于图灵机的事实可能不是可计算的！
-FSA 具有较小但并非微不足道的计算能力——如上所述，它足以识别正则表达式。例如，它可以相加两个无界整数。
+== 变体 ==
-许多更强大的计算模型在施加了简单限制后，被证明在计算上等同于 FSA。例如，只能向右移动的[[Turing machine|图灵机]]在计算上等同于 FSA。
+* [[Clockwise Turing machine|顺时针图灵机]]
+* [[Oracle machine|预言机]]
+* [[Near-Turing machine|近图灵机]]
+* [[Swapping Turing Machine|交换图灵机]]
-许多[[esoteric programming language|深奥编程语言]]属于与 FSA 相同的[[computational class|计算类别]]。
+== 外部资源 ==
-==历史==
+* 参见维基百科上的[[Wikipedia:Turing machine|图灵机]]
+* [https://github.com/florton/Turing-Machine-Compiler 图灵机语言] - 一个用Python编写的图灵机解释器
+* [http://sourceforge.net/projects/visualturing/ 可视化图灵机] - 动画图灵机模拟器
+* [http://www.abelard.org/turpap2/tp2-ie.asp ''论可计算数及其在判定问题上的应用''] - 图灵介绍其机器的论文
+* Boolos, G. 和 Jeffrey, R., ''可计算性与逻辑'', 第二版, 剑桥: 剑桥大学出版社, 1980.
+* [https://turingmachinesimulator.com/ 在线图灵机模拟器]
+* [http://people.irisa.fr/Francois.Schwarzentruber/recursive_functions_to_turing_machines/ 另一个模拟器]
+* [http://morphett.info/turing/turing.html 又一个模拟器]
+* [http://www.cs.columbia.edu/~sedwards/classes/2008/w4115-fall/reports/TMSL.pdf 图灵机模拟语言]
-可以在有限数量的内部状态之间转换的系统早已为人所知，但直到计算机科学早期历史相对较晚时才被正式研究。
+[[Category:Computational models]]
-以下引文来自 Rabin 和 Scott[1959, “Finite automata and their decision problems,” IBM Journal of Research and Development 3,2 (April, 1959), 114]：
-：“图灵机被广泛认为是数字计算机的抽象原型；然而，该领域的工作者越来越感到图灵机的概念过于笼统，无法作为实际计算机的准确模型。众所周知，即使是简单计算，也无法为图灵机在任何给定计算中所需的磁带量给出先验上界。正是这一特性使得图灵的概念不切实际。”
-：“在过去几年中，有限自动机的概念出现在文献中。这些机器只有有限数量的内部状态，可用于内存和计算。有限性的限制似乎能更好地近似物理机器的概念。当然，这样的机器不能像图灵机那样做那么多事情，但能够计算任意一般递归函数的优势是值得怀疑的，因为在实际应用中很少出现这些函数。”
-[[Category:Computational models|分类:计算模型]]