|
|
| 第1行： |
第1行： |
| {{Distinguish/Confusion|Turing-machine}}
| | 一个'''线性有界自动机'''（LBA）是一种抽象机器，它与[[Turing machine|图灵机]]相同，除了在给定输入的计算期间，其磁带头不允许移动到其无限磁带的有界区域之外，可访问的磁带单元数量是输入大小的线性函数。磁带本身具有无限长度以适应任意长度的输入。（这种模型的一个等效替代版本为LBA提供不同长度的有限磁带，每个不同大小的输入对应一个磁带，磁带的长度是输入大小的线性函数。在这个替代版本中，有无限多个有限磁带的供应，每个输入大小对应一个磁带。） |
| 一个'''图灵机'''是由[[Alan Turing|艾伦·图灵]]设计的一种假想机器，用于执行计算。它由一个[[finite-state automaton|有限状态自动机]]（通常称为其“控制机制”或程序）连接到一个[[unbounded|无界]][[tape|磁带]]组成，磁带可以左右移动，从中可以读取符号，并可以在其上写入符号。 | |
|
| |
|
| 一个[[universal Turing machine|通用图灵机]]是一种图灵机，它可以被给予以某种形式编码的任何任意图灵机的描述，在其磁带上初始化，并且有限状态机以这样的方式操作描述，从而模拟被描述的机器。通用机得名于它们能够计算任何可计算序列的事实。
| | 与图灵机类似，LBA是一个配备磁带的[[finite state machine|有限状态机]]。与图灵机系统不同，LBA系统（有限状态机加上其磁带）对于每个输入只有有限多个系统状态；也就是说，对于每个输入，LBA系统表现得像一个有限自动机。LBA和有限状态自动机（FSA）之间的一个相关区别是，FSA的状态数量对于该FSA是固定的，而LBA的状态数量随给定输入量的线性函数变化。 |
|
| |
|
| 图灵机在计算上具有重要意义，因为尽管许多[[:Category: Computational models|计算模型]]已被证明只能解决给定图灵机可以解决的计算问题的一个子集，但尚未有任何可定义为算法集合的计算系统被证明能够解决图灵机不能解决的计算问题。
| | 使用泵引理可以证明，存在一些语言，它们被某些LBA识别，但无法被任何[[push-down automaton|下推自动机]]识别。线性有界自动机识别[[context-sensitive language|上下文有关语言]]类。 |
|
| |
|
| 此外，尚未设计出任何通用图灵机明显无法执行的明确定义算法。这导致了[[Church-Turing thesis|丘奇-图灵论题]]，它（粗略地）指出图灵机是（我们直观上认为的）有效可计算算法的机械体现。也就是说，图灵机可以进行任何可能精确定义算法的计算。
| | ==历史== |
| | Myhill (1960) 引入了LBA，其动机是Rabin和Scott (1959) 对有限自动机的研究。 |
|
| |
|
| 自从艾伦·图灵的论文中发明图灵机以来，许多其他系统已被证明与它们等价。（事实上，其中一些系统，如[[lambda calculus|λ演算]]、[[combinatory logic|组合子逻辑]]和[[Post canonical system|波斯特规范系统]]，早于图灵机。）通过这种方式，图灵机定义了一个等价系统的[[computational class|计算类别]]；这些系统被称为[[Turing-complete|图灵完备]]。
| | ==另见== |
| | * [[:Category:Linear bounded automata|线性有界自动机分类]]（本维基中具有与LBA等效能力的语言列表） |
|
| |
|
| 由于所有这些原因，证明一个[[esoteric programming language|深奥编程语言]]是否等价于图灵机通常是一个有趣和/或有价值的任务。
| | ==外部资源== |
| | * [[Wikipedia:Linear bounded automaton|维基百科：线性有界自动机]] |
|
| |
|
| 形式上，图灵机通常以元组格式描述，<math>(\Sigma, \sigma_0, Q, q_1, q_h, f)</math>，包括：
| | [[Category: Computational models]] |
| * 符号集合 <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> 未定义
| |
| ** 接受当前状态和当前观察到的符号，然后产生一个新符号来覆盖观察到的符号、一个移动方向以及要转换到的下一个状态
| |
| | |
| 以这种方式描述的图灵机可以被视为一个[[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>。
| |
| | |
| == 停机问题 ==
| |
| | |
| 关于图灵机的一些最著名的事实涉及停机状态。机器是否会从给定的起始配置进入停机状态？我们有两个重要结果。
| |
| | |
| '''定理。''' 如果一个图灵机停机，那么在[[wikipedia:Elementary theory of the category of sets|ETCS]]和[[wikipedia:Zermelo–Fraenkel set theory|ZF]]中存在证明它停机的证明。
| |
| | |
| '''定理（图灵机停机的不可判定性）。''' 没有有效程序能在ETCS或ZF中产生证明，证明给定图灵机在给定输入磁带上停机。
| |
| | |
| 通俗地说，图灵机是否停机（在选定的输入上）是一个具体的、客观的、野蛮的事实；相应的证明仅仅是机器执行的历史。然而，标准集合论并不总是能够证明这样的事实。根本问题在于强集合论的[[wikipedia:Gödel's incompleteness theorems|哥德尔不完备性]]；当集合论能够编码数论时，它也能够引入哥德尔关于数论不完备性的所有推理。
| |
| | |
| 另一个非正式的教训是，[[computable|可计算]]是图灵机''做''什么，而不是图灵机''是''什么。关于图灵机的事实可能不是可计算的！
| |
| | |
| == 变体 ==
| |
| | |
| * [[Clockwise Turing machine|顺时针图灵机]]
| |
| * [[Oracle machine|预言机]]
| |
| * [[Near-Turing machine|近图灵机]]
| |
| * [[Swapping Turing Machine|交换图灵机]]
| |
| | |
| == 外部资源 ==
| |
| | |
| * 参见维基百科上的[[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]] | |
一个线性有界自动机（LBA）是一种抽象机器，它与图灵机相同，除了在给定输入的计算期间，其磁带头不允许移动到其无限磁带的有界区域之外，可访问的磁带单元数量是输入大小的线性函数。磁带本身具有无限长度以适应任意长度的输入。（这种模型的一个等效替代版本为LBA提供不同长度的有限磁带，每个不同大小的输入对应一个磁带，磁带的长度是输入大小的线性函数。在这个替代版本中，有无限多个有限磁带的供应，每个输入大小对应一个磁带。）
与图灵机类似，LBA是一个配备磁带的有限状态机。与图灵机系统不同，LBA系统（有限状态机加上其磁带）对于每个输入只有有限多个系统状态；也就是说，对于每个输入，LBA系统表现得像一个有限自动机。LBA和有限状态自动机（FSA）之间的一个相关区别是，FSA的状态数量对于该FSA是固定的，而LBA的状态数量随给定输入量的线性函数变化。
使用泵引理可以证明，存在一些语言，它们被某些LBA识别，但无法被任何下推自动机识别。线性有界自动机识别上下文有关语言类。
历史
Myhill (1960) 引入了LBA，其动机是Rabin和Scott (1959) 对有限自动机的研究。
另见
外部资源
_icon.png
){kind=icon}
_wordmark.png)