##### 图灵机 - 图灵机 - **图灵机**是一种比[[有限自动机]]和[[下推自动机]]更强大的[[自动机]], 它通过引入一个无限长的磁带和可以左右移动读写头进行读写存储, 可以模拟任何算法过程, 是通用[[计算模型]]的基础. 能够识别和处理[[递归可枚举语言]]. 图灵机可以定义为一个七元组 $M = (Q, \Sigma, \Gamma, \delta, q_0, q_\text{accept}, q_\text{reject})$, 其中 - $Q$ 有限状态集合 - $\Sigma$ 输入字母表 - $\Gamma$ 带字母表, 且 $\Sigma \subseteq \Gamma$ - $\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$ 是状态转移函数 - $q_0 \in Q$​ 初始状态 - $q_\text{accept} \in Q$​ 接受状态 - $q_\text{reject} \in Q$​ 拒绝状态