图灵机简介
图灵机是一个接受设备，它接受由0型语法生成的语言（递归可枚举集）。它是由阿兰·图灵于 1936 年发明的。
定义
图灵机 (TM) 是一种数学模型，由无限长度的磁带组成，磁带被划分为多个单元，在单元上给出输入。它由一个读取输入磁带的磁头组成。状态寄存器存储图灵机的状态。读取输入符号后，它会被替换为另一个符号，其内部状态会发生变化，并且会从一个单元格向右或向左移动。如果 TM 达到最终状态，则接受输入字符串，否则拒绝。
TM 可以正式描述为 7 元组 (Q, X, Σ, δ, q 0 , B, F)，其中 -
Q是有限状态集
X是磁带字母表
Σ是输入字母表
δ是过渡函数；δ : Q × X → Q × X × {左移，右移}。
q 0是初始状态
B是空白符号
F是最终状态的集合
与之前的自动机的比较
下表显示了图灵机与有限自动机和下推自动机的区别。
| 机器 | 堆栈数据结构 | 确定性？ |
|---|---|---|
| 有限自动机 | 不适用 | 是的 |
| 下推自动机 | 后进先出（LIFO） | 不 |
| 图灵机 | 无限磁带 | 是的 |
图灵机示例
图灵机 M = (Q, X, Σ, δ, q 0 , B, F) 其中
- Q = {q 0 , q 1 , q 2 , q f }
- X = {a, b}
- Σ = {1}
- q 0 = {q 0 }
- B = 空白符号
- F = {q f }
δ 由下式给出 -
| 磁带字母符号 | 当前状态“q 0 ” | 当前状态“q 1 ” | 当前状态“q 2 ” |
|---|---|---|---|
| A | 1Rq 1 | 1Lq 0 | 1Lqf _ |
| 乙 | 1Lq 2 | 1Rq 1 | 1Rqf _ |
这里，转变 1Rq 1意味着写入符号为 1，磁带向右移动，下一状态为 q 1。类似地，转变1Lq 2意味着写入符号为1，磁带向左移动，并且下一个状态是q 2。
图灵机的时间和空间复杂度
对于图灵机来说，时间复杂度是指当机器针对某些输入符号初始化时磁带移动的次数的度量，而空间复杂度是写入磁带的单元数。
所有合理函数的时间复杂度 -
T(n) = O(n log n)
TM 的空间复杂度 -
S(n) = O(n)