图灵机

定义

图灵机是一个 7 元组 $(Q, Σ, Γ, δ, q_{0}, q_{a cce pt}, q_{re j ec t})$ ，其中

$Q$ 是状态集合
$Σ$ 是输入字母表，表示能够处理的输入字符。特别地， $␣ \neq \in Σ$
$Γ \supseteq Σ$ 是工作带字母表，它表示所有能够写在带子上的字母。特别地， $␣, D \in Γ$ ，其中 $D$ 表示输入的起始
$δ : Q \times Γ \to Q \times Γ \times {L, R, S}$ 是转移函数，其中 $L$ 表示向左移动， $R$ 表示向右移动， $S$ 表示不动
$q_{0} \in Q$ 是初始状态
$q_{a cce pt}$ 是接收状态
$q_{re j ec t}$ 是拒绝状态

对于计算问题（而不是判断问题），需要将 $q_{a cce pt}$ 和 $q_{re j ec t}$ 合并为 $q_{e n d}$ 。

用 $⟨ M ⟩$ 表示图灵机 $M$ 的字符串编码。

TIP

图灵机可以通过分叉来记住一个枚举值（例如布尔值）。

如果 $L$ 可以在 $T (n)$ 时间内可以被一个图灵机判定，则它也可以在 $O (T (n) lo g ∣Γ∣)$ 时间内被一个 $Γ = {0, 1, ␣, D}$ 判定。

$k$ 带图灵机的定义跟普通图灵机类似，但是每次的输入是 $Γ^{k}$ 中的元素，状态转移函数也需要同时考虑 $k$ 条带子的状态。

如果 $L$ 可以在 $T (n)$ 时间内被一个 $k$ 带图灵机判定，则 $L$ 可在 $O (k T^{2} (n))$ 时间内被一个单带图灵机判定。

如果 $L$ 可以在 $T (n)$ 时间内被一个双向纸带图灵机判定，则 $L$ 可在 $O (T (n))$ 时间内被一个单带图灵机判定。

增加一个内存带 $A$ 和地址带。在 $Q_{a ccess} \subseteq Q$ 状态下会根据地址带中记载的操作执行操作：

如果 $L$ 可以在 $T (n)$ 时间内被一个 RAM 图灵机判定，则它可以在 $O (T^{3} (n))$ 时间内被一个多带图灵机判定。此外，如果地址的长度为 $O (1)$ 则 $L$ 可以在 $O (T^{2} (n))$ 内被多带图灵机判定。

在图灵机的基础上，可以转移到多个状态。

在非确定性图灵机的基础上，要求转移到至多两个状态。

存在一个通用的图灵机 $U$ 满足对任意 $x, α \in {0, 1}^{*}$ 都有 $U (x, α) = M_{α} (x)$ 。其中， $α$ 表示某个图灵机用 $01$ 串的编码。

如果 $M_{α} (x)$ 在 $T$ 步内结束，则 $U (x, α)$ 在 $O_{M} (T lo g T)$ 步内结束。

NOTE

这里 $O_{M} (T (n))$ 表示 $T (n)$ 之前的系数由选定的图灵机 $M$ 决定。