图灵机简介
图灵机是一种接受设备，它接受由 0 型语法生成的语言（递归可枚举集）。它由艾伦·图灵于 1936 年发明。
定义
图灵机 (TM) 是一种数学模型，它由一条无限长的磁带组成，磁带被分成多个单元，输入信息都通过这些单元输入。它由一个读取输入磁带的磁头组成。状态寄存器存储图灵机的状态。读取输入符号后，该符号被另一个符号替换，其内部状态发生变化，并从一个单元向右或向左移动。如果 TM 达到最终状态，则接受输入字符串，否则拒绝。
TM 可以正式描述为 7 元组 (Q、X、∑、δ、q0、B、F)，其中 −
Q 是一组有限的状态
X 是磁带字母表
∑ 是输入字母表
δ 是转换函数；δ : Q × X → Q × X × {Left_shift, Right_shift}。
q0 是初始状态
B 是空白符号
F 是最终状态集
与之前的自动机的比较
下表显示了图灵机与有限自动机和下推自动机的不同之处。
| 机器 | 堆栈数据结构 | 确定性？ |
|---|---|---|
| 有限自动机 | N.A | 是 |
| 下推自动机 | 后进先出 (LIFO) | 否 |
| 图灵机 | 无限磁带 | 是 |
图灵机示例
图灵机 M = (Q, X, ∑, δ, q0, B, F) 与
- Q = {q0, q1, q2, qf>
- X = {a, b>
- ∑ = {1>
- q0 = {q0>
- B = 空格符号
- F = {qf >
δ 由 − 给出
| 磁带字母符号 | 当前状态'q0' | 当前状态'q1' | 当前状态'q2' |
|---|---|---|---|
| a | 1Rq1 | 1Lq0 | 1Lqf |
| b | 1Lq2 | 1Rq1 | 1Rqf |
这里的转换 1Rq1 意味着写入符号为 1，磁带向右移动，下一个状态为 q1。类似地，转换 1Lq2 意味着写入符号为 1，磁带向左移动，下一个状态为 q2。
图灵机的时间和空间复杂度
对于图灵机，时间复杂度是指机器初始化某些输入符号时磁带移动的次数的度量，而空间复杂度是写入的磁带单元数。
时间复杂度所有合理函数 −
T(n) = O(n log n)
TM 的空间复杂度 −
S(n) = O(n)
