跳转至

4 Turing Machine

4.1 The Definition of Turing Machine

虽然 PDA 比 FA 强大，但它仍然有局限性；而图灵机通过“可读写”的带子克服了这些限制。

定义：一个图灵机是一个五元组 \((K, \Sigma, \delta, s, H)\)，其中：

  • \(K\) 是一个有限的状态集合
  • \(\Sigma\) 是一个字母表，满足：
  • 包含空白符号 \(\sqcup\) 和左端标记 \(\triangleright\)
  • 不包含移动符号 \(\rightarrow\) 和 \(\leftarrow\)
  • \(s \in K\) 是初始状态
  • \(H \subseteq K\) 是停机状态集合
  • \(\delta: (K - H) \times \Sigma \to K \times (\Sigma \cup \{\leftarrow, \rightarrow\})\) 是转移函数，且满足以下约束：
  • 对任意 \(q \in K - H\)，若 \(\delta(q, \triangleright) = (p, b)\)，则必有 \(b = \rightarrow\)
  • 对任意 \(q \in K - H\) 和 \(a \in \Sigma\)，若 \(\delta(q, a) = (p, b)\)，则 \(b \neq \triangleright\)

Graph Representation

注意图灵机是确定性的

Definition: A configuration of a TM \(M=(K,Σ,δ,s,H)\) is a member of

\[ K × ▹Σ^∗×(Σ^∗(Σ−\{⊔\})∪{e}) \]

  • \(x\)：从左端标记 \(▹\) 到读写头当前位置之间的符号串（含读写头所在位置）
  • \(y\)：从读写头右侧第一个非空白符号开始到最右非空白符号之间的内容
  • 若右边全为空白，则 \(y=e\)（空串）

A simplified notation of configuration

Example

还是和之前一样用 \(\vdash_M\) 代表一次推导，$ \vdash_M^*$ 和 $ \vdash_M^n$ 的含义也是类似的

为之后叙述图灵机简单一些，引入基本图灵机的概念

\[ M_a = ({s, h}, Σ, δ, s, {h}) \]

其中对于任意 \(b\in\Sigma-\{▹\}\)，\(\delta(s,b) = (h,a)\)，同时, \(𝛿(𝑠, ⊳) = (𝑠, →)\)。只要碰到不是 \(▷\) 的符号（比如 \(a\)、\(b\)、空白等），就把那个格子改成 \(a\)，然后停下。

缩写

\(𝑎\) instead of \(𝑀_𝑎\), \(𝐿\) instead of \(𝑀_←\), and \(𝑅\) instead of \(𝑀_→\).

利用基本图灵机组装一个大的图灵机

Example

设 \(M_i = (K_i, \Sigma, \delta_i, s_i, H_i)\)，其中 \(i = 1,2,3\)，均为图灵机（TMs）。组合后的机器为 \(M = (K, \Sigma, \delta, s, H)\)，其中：

\[ K = K_1 \cup K_2 \cup K_3 \]
\[ s = s_1 \]
\[ H = H_2 \cup H_3 \]

对于每个 \(\sigma \in \Sigma\) 和 \(q \in K - H\)，转移函数 \(\delta(q, \sigma)\) 定义如下：

  • 若 \(q \in K_1 - H_1\)，则 \(\delta(q, \sigma) = \delta_1(q, \sigma)\)。
  • 若 \(q \in K_2 - H_2\)，则 \(\delta(q, \sigma) = \delta_2(q, \sigma)\)。
  • 若 \(q \in K_3 - H_3\)，则 \(\delta(q, \sigma) = \delta_3(q, \sigma)\)。
  • 若 \(q \in H_1\)，则：
  • 当 \(\sigma = a\) 时，\(\delta(q, \sigma) = s_2\)
  • 当 \(\sigma = b\) 时，\(\delta(q, \sigma) = s_3\)
  • 否则，\(\delta(q, \sigma) \in H\)

4.2 Computing with Turing Machine

图灵机通过进入两个特殊的“停机状态”来表示对输入的判断结果——“是”或“否”。

对于一个输入来说，若图灵机进入接受状态则接受输入；若图灵机进入拒绝状态则拒绝输入。

我们称一个图灵机可以决定某个语言，当且仅当对每一个输入 \(w\)，\(M\) 都能在有限步内做出判断：

  • 若 \(w∈L\) → 接受
  • 若 \(w\notin L\) → 拒绝

如果存在一台图灵机能决定某个语言，则该语言是递归的（即可判定的）。

Example

对于一个图灵机 \(M = (K,\Sigma,\delta,s,H)\)，然后字母表 \(\Sigma_0 \subseteq \Sigma-\{\sqcup, \triangleright\}\) 然后语言 \(L \subseteq \Sigma_0^*\) 。称 \(M\) 半决定（Semidecides) \(L\) 如果对于任意的 \(w\in \Sigma^*\) 来说，下面的论断是对的

\[ w\in L \Leftrightarrow M 在输入为 w时可以停机 \]

此时也称 \(L\) 是 recursively enumerable 的

If 𝐿 is a recursive language, then it is R.E.

这样就可以让错误的一直不停机

总结一下 Regular Language, CFL， R.E. language 的关系

Recursive Language 的补是 Recursive 的（交换接受和拒绝这两种停机状态即可）并和交也是 Recursive 的

设 \(M=(K,\Sigma,\delta,s,H)\) 是一台图灵机。令 \(\Sigma_0\subseteq\Sigma-\{\triangleright,\sqcup\}\) 为一个字母表，且 \(w\in\Sigma_0^*\)。

  • 假设 \(M\) 在输入\(w\)上停机，且 \((s,\triangleright\underline{\sqcup} w)\Rightarrow_M^*(h,\triangleright\underline{\sqcup} y)\) 对某个\(y\in\Sigma_0^*\) 成立。则称 \(y\) 是 \(M\) 在输入\(w\)上的输出，记作 \(M(w)\)。

  • 设 \(f\) 是一个函数 \(f:\Sigma_0^*\to\Sigma_0^*\)。若对所有 \(w\in\Sigma_0^*\)，都有 \(M(w)=f(w)\)，则称图灵机 \(M\) 计算函数 \(f\)。

  • 若存在一台图灵机 \(M\) 能计算函数 \(f\)，则称函数 \(f\) 是递归的（recursive）。

用人话讲一下就是原先磁带上的是输入，然后经过一番操作之后指针回到原点，然后磁带上的就是输出，这就是一个函数

4.3 Extension of Turing Machine

图灵机可以做一些扩展，但是我们发现这些看似扩展，实则并没有提升图灵机的能力

  • 多条磁带
  • 双向无限的磁带
  • 多个读写头
  • 多维磁带
  • 不确定性图灵机

这些扩展可以更好地帮我们构建图灵机，下面我们将阐述一下为什么这些扩展并没有提升图灵机的能力

下面阐述多条磁带的图灵机

定义：设 \(k \geq 1\) 为一个整数。一个 \(k\) 带图灵机 \((K,\Sigma,\delta,s,H)\)，其中 \(K,\Sigma,s\) 和 \(H\) 与普通图灵机定义中的相同，而 \(\delta\) 是转移函数：

\[ \delta:(K-H)\times\Sigma^k\to K\times(\Sigma\cup\{\leftarrow,\rightarrow\})^k \]

定义：设 \(M=(K,\Sigma,\delta,s,H)\) 是一个 \(k\) 带图灵机。\(M\) 的一个configuration如下：

\[ K\times\left(\triangleright \Sigma^*\times\left(\Sigma^*(\Sigma-\sqcup)\right)\cup\{e\}\right)^k \]

同时我们规定：

  • 输入字符串放在第一条带上
  • 其他磁带初始为空白，读写头位于最左侧空白格
  • 计算结束时，输出在第一条带上，其他磁带忽略

Example

定理：设 \(M=(K,\Sigma,\delta,s,H)\) 是一个 \(k\)-带图灵机（\(k \geq 1\)）。则存在一个标准图灵机 \(M'=(K',\Sigma',\delta',s',H)\)，其中 \(\Sigma \subseteq \Sigma'\)，使得以下结论成立：

  • 对任意输入字符串 \(x \in \Sigma^*\)，\(M\) 在输入 \(x\) 上停机，并在第一条带上输出 \(y\)，当且仅当 \(M'\) 在输入 \(x\) 上停机于相同的停机状态，且在其磁带上输出相同的 \(y\)。
  • 如果 \(M\) 在输入为 \(x\) 后 \(t\) 步停机了，那么 \(M'\) 会在 \(O(t(|x|+t))\) 步后会停机

证明思路是：构造一个标准图灵机 \(M′\)，模拟 \(k\)-带图灵机 \(M\) 的行为。

Phase 1 将 k 带图灵机的初始配置编码到单带图灵机的一条磁带上：每个磁带格子存储一个 2k 元组，前 k 项表示各带在该位置的符号，后 k 项用 0/1 标记各读写头是否位于此处。

Phase 2 就是模拟 M 的计算过程。首先从左到右（或从当前头位置）扫描，收集所有 k 个虚拟头当前读取的符号，形成 k-元组；然后根据 M 的转移函数确定新状态、要写入的符号和各头的移动方向，并更新 M′ 的内部状态；接着再次扫描磁带，将新符号写入对应位置，并通过在头标志位（0/1）上修改来反映各虚拟头的新位置。虽然 M′ 只有一个物理读写头，但通过多次遍历和标记，能准确模拟多个头的“同时”移动与操作。

最后停机的时候

  • 解码：将磁带上每个复合元组（如 (a,⊔,0,0)）替换为其第一条带的符号（如 a），还原输出内容；
  • 定位：根据头标志位找到第一个头的位置，将自身读写头移至对应列；
  • 同步：进入与 M 相同的接受或拒绝状态，确保行为等价。

对于时间复杂度 \(O(t(|x| + t))\) 来说，由两个阶段决定：

  • Phase 1: \(O(|x|)\)
  • Phase 2: 对于 M 的每一步，M' 需要 \(O(|x|+2+t)\)

对于由两边无限延长的磁带的图灵机来说，很容易将其转换为双磁带的图灵机

对于单磁带多头的图灵机，可以用多带图灵机对其进行模拟，除去原先的单磁带，其他几条磁带用于模拟每个头的状态。

对于多维图灵机也可以用多带图灵机对其模拟，记录坐标即可。

4.4 Nondeterministic Turing Machines

定义：一台非确定型图灵机（NTM）是一个五元组 \(M = (K,\Sigma,\Delta,s,H)\)，其中 \(K\)、\(\Sigma\) 和 \(H\) 与标准图灵机相同，而 \(\Delta\) 是以下集合的一个子集：

\[ ((K - H) \times \Sigma) \times (K \times (\Sigma \cup \{ \leftarrow, \rightarrow \})) \]

与图灵机类似，但 \(\Delta\) 现在是一个关系而非函数。

Configuration以及关系 \(\vdash_M\) 和 \(\vdash_M^*\) 的定义与标准图灵机类似。 - \(\vdash_M\) 不必是单值的：一个 Configuration 在一步中可能产生多个其他格局

半判定： - 给定 NTM \(M\) 其输入符号集为\(\Sigma_0\) - \(M\) semidecides \(L\subseteq\Sigma_0^*\) if for any \(w\in\Sigma_0^*\) ,\(w\in L\) iff \((s,\triangleright\sqcup w)\vdash_M^*(h,\cdots)\)forsome \(h\in H\) - 如果 \(w\in L\) 则NTM有分支可以停机，否则没有分支可以停机

判定：令\(M=(K,\Sigma,\Delta,s,\{y,n\})\)，输入符号集 \(\Sigma_0\)，\(M\) decides a language \(L\subseteq\Sigma_0^*\) if

  • for any \(w\in\Sigma_0^*\) ,exists an a tural number \(N\),s.t.no configuration \(c\) satisfying \((s,\triangleright\sqcup w)\vdash_M^N c\) 说明在\(N\)步内都可以停机，非确定产生的树高度小于\(N\)
  • \(w\in L\) iff \((s,\triangleright\sqcup w)\vdash_M^*(y,\cdots)\) 非确定执行的树上有一条分支可以停机到 \(y\) 状态

半判定就是有一个可停机，判定就是所有可能情况都可停机（注意停机状态只有 Y/N）但是有情况停机状态是 Y

构造 NTM 判定所有合数（非质数）的二进制编码构成的语言

利用NTM可以“猜测”的特性，目标是猜测有没有两个数相乘等于输入。

假设输入字符串为 $w$，则先猜测两个数，得到 $\triangleright\sqcup p\sqcup q$，然后将$p$和$q$相乘，如果等于 $w$ 则停机到 $y$，否则停机到 $n$，满足第二个条件。

因为 $p,q$ 都小于 $w$，所以猜测是有限的，而且都可以有限步停机，满足第一个条件。

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！