Theory of computation

导航

• 导航
• introduction
• chapter1 Sets,relations,and languages
  • 1.4 Finite and infinite sets
  • 1.5 Three Fundamental Proof Tech.
  • 1.6 closure
  • 1.7 Alphabet and Language
  • 1.8 finite representation of languages
• chapter2 Regular language and automata
  • 2.1 Determinitic Finite Automata
  • 2.2 Nondeterministic Finite Automata
  • 2.3 有穷自动机与正则表达式
    • example
  • 2.4 正则语言与非正则语言
• chapter 3 上下文无关语言
  • 3.1 上下文无关文法
    • 定义
  • 3.2 语法分析树
  • 3.3 下推自动机
    • 巧妙的设计
  • 3.4 上下文无关语言与下推自动机
  • 3.5 上下文无关语言与非上下文无关语言
• chapter 4–图灵机
  • 4.1 图灵机的定义
    • 定性描述
    • 形式化表达
    • 格局的定义
  • 4.2 图灵机的计算
    • 图灵机计算的定义
    • 递归可枚举语言 (Recursively Enumerable, R.E.)
    • 递归语言的性质
    • 图灵机的核心用途
  • 4.3 图灵机的扩展
    • Multiple Tapes
  • 4.4 非确定性图灵机
    • The definition of a non-deterministic TM
    • NTM半判定语言
    • NTM判定语言
    • NTM计算函数
    • equal of NTM and TM
  • 4.5 Grammer

introduction

chapter1 Sets,relations,and languages

1.4 Finite and infinite sets

• Countable Infinite:
  • 一个集合如如果是可数无穷的等价于它与正整数集等势
  • 可数个可数无穷集合是可数无穷的
• Cantor’s Theorem
  • Let f be a map from set A to its power set $P(A)$.Then card(A)$\le$card(P(A)) holds for any set A.(card为元素数量)
  • 证明构造基于讨论是否存在满射，需要构造一个很特殊的集合进行证明:$B={x \in A | x \notin f(x)}$，再通过反证法进行证明。

1.5 Three Fundamental Proof Tech.

• The Principle of Mathematical Induction
• The Pigeonhole Principle
• The Diagonalization Principle
  • Let R be a binary relation on a set A,and let D,the diagonal set for R,$D = {a | a \in A \land (a,a) \notin R}$. For each $a \in A$,let $R_a = {b | (a,b) \in R}$
  • Then D is distinct from $R_a$.
  • 上述的principle能够比较直观的证明cantor定理。将映射具象为上述的矩阵表示。可以发现之前的集合B的构造就和上面的D集合的构造相同。

1.6 closure

1.7 Alphabet and Language

• Alphabet
  • Any finite set is called an alphabet.Elements of an alphabet are called symbols.
• Strings
  • we call finite sequences of the alphabet $\Sigma$ words or strings over $\Sigma$
  • we denote by e the empty string over $\Sigma$
• Language: Set of Strings
  • Alphabet:$\Sigma$
  • The set of all strings:$\Sigma^* = {e,a,ab,abc,abcd,….}$
  • Language:$L$
  • Finite Language:by listing all the strings
  • Infinite Language:specify by the following scheme:$L = {w \in \Sigma^* | w has property P}$

1.8 finite representation of languages

• regular expression
  • 正则表达式构建于字母表上的基本元素和三种核心运算
  • 基本元素:a(字母表中的任意一个符号)，空集。空字符串e
  • 三种核心运算
    • 连接:语言$L_1L_2 = {w_1w_2 | w_1 \in L_1 \land w_2 \in L_2}$
    • 联合:包含$R_1,R_2$描述的所有字符串
    • Kleene:表示R描述的字符串连接零次或多次
• 正则表达式的运算规则
  • 联合的性质
    • 结合律
    • 交换律
    • 幂等性 $R + R = R$
  • 连接的性质
    • 结合律
    • 分配律
  • Kleene星号的性质

chapter2 Regular language and automata

2.1 Determinitic Finite Automata

• 定义:A deterministic finite automata (DFA) is a
  quintuple (𝐾, Σ, 𝛿, 𝑠, 𝐹), where(K is a finite set of states,$\Sigma$ is an alphabet,𝑠 ∈ 𝐾 is the initial state,𝐹 ⊆ 𝐾 is the set of final states,𝛿 : transition function, 𝐾 × ∑ → 𝐾.)
• A configuration of a DFA 𝐾, Σ, 𝛿, 𝑠, 𝐹 is in 𝐾 × Σ∗
  • 配置 ∈K×Σ∗：一个配置是一个有序对 (q,w)，其中 q∈K当前状态，而 w∈Σ∗是待处理的剩余输入字符串。
  • A configuration of a finite automaton 𝑴 tells the current state and the inputs to be read in the future
• 单步转移关系 (⊢M) 的定义
  • 自动机 M 可以从配置 (q,w) 一步转移到配置 (q′,w′)，当且仅当：输入消耗：待处理的字符串 w 可以分解为一个输入符号a∈Σ 和剩余部分 w′，即 w=aw’。状态转移： 当前状态 q 在读入输入符号 a 后，根据转移函数 δ 移动到新的状态 q′，即 δ(q,a)=q′。

2.2 Nondeterministic Finite Automata

• 定义:与前面的确定性finite automata最大的区别如下:Δ :transition relation, is thesubset of 𝐾 × (Σ ∪ {𝑒} )× K
• 等价的定义:两台有穷自动机$M_1$,$M_2$等价，当且仅当$L(M_1)=L(M_2)$,L(M)是自动机M接受的字符串的集合
• 定理2.2.1:对于每一台非确定性有穷自动机，有一台等价的确定型有穷自动机
  • 证明思路:因为非确定性有穷自动机的特点，所有的状态应该作为状态集合来看待，也就是说从某个开始状态读了字符串后能达到唯一的状态集合，而不是这个集合的某一个不确定成员，构造等价的确定型有穷自动机就是把这个想法形式化。$M^\prime$的状态集合为$K^\prime$，其中$K^\prime$为$K$的幂集;$M^\prime$的终结状态集合由K中至少包含M的一个终结状态的所有子集组成。而对于$M^\prime$的转移函数的定义，我们在形式化之前需要引入以下的关键概念。
  • 对于任一状态$q \in K$,令$E(q) = { p \in K:(q,e)⊢M (p,e)}$，有了上述的概念，我们就能形式化地定义与M等价的确定型有穷自动机$M^\prime$的转移函数。
  • 对于每一个$Q \subseteq K$和$a \in \Sigma$，定义$\delta ^ \prime (Q,a) = \bigcup${$E(p):p \in K 且对某个q \in Q ,(q,a,p)\in \Delta$}
  • 下面提出一个最关键的断言:对任一字符串$w \in Σ^*$和任意状态 $p,q \in K$,$(q,w)⊢M(p,e)$当且仅当对某个包含p的集合P,$(E(q),w)⊢M’(P,e)$。根据这个断言我们来证明等价:考虑任一字符串w,根据定义$w \in L(M)$当且仅当对某个$f \in F$,$(s,w)⊢M(f,e)$;那么根据上面的断言我们知道当且仅当对某个包含f的Q,$(E(s),w)⊢M’(Q,e)$,换句话说，当且仅当对某个$Q\in F^\prime$,$(s^\prime,w)⊢M’(Q,e)$,这就是$w \in L(M^\prime)$的定义，那么我们根据断言成功证明等价。
  • 下面进行断言的证明:
    • 我们使用归纳假设进行证明
    • 基础步骤,|w|=0时，此时第一个命题等价于$p \in E(q)$,又因为$M^\prime$是确定型的，所以第二个命题等价于P=E(q),且$p \in P$,则可说明这两个命题等价。
    • 归纳假设:假设对于某个k，当字符串长度小于等于k时假设成立。要证明对任意长度为k+1的字符串w=va,断言成立。
    • 从左到右:设$(q,w)⊢M(p,e)$,那么存在状态r1,r2使得$(q,w)⊢M(r1,a)⊢M(r2,e)⊢M(p,e)$。也就是有$(q,v)⊢M(r1,e)$,因为|v|=k,由归纳假设知道对某个包含r1的集合R1,$(E(q),v)⊢M’(R1,e)$.由于$(r1,a)⊢M(r2,e)$，根据$M’$的构造$E(r2) \subseteq \delta ^ \prime (R1,a)$,同样有$p \in E(r2)$,因此$p \in \delta ^ \prime (R1,a)$，那么根据$M’$的定义:$(R1,a)⊢M’(P,e)$,进而有$(E(q),va)⊢M’(R1,a)⊢M’(P,e)$得证。
    • 从右到左:证明思路类似。

2.3 有穷自动机与正则表达式

• 定理2.3.1:有穷自动机接受的语言类在下述运算下是封闭的。
  • 并:相当于我们想要构造出一个自动机$M^\prime$,使得$L(M1) \cup L(M2) = L(M^\prime)$。构造思路就是构造一个都不存在于这两个自动机的起始点，它能够不确定性地到达两个自动机的起始点。
  • 连接:先模拟M1,然后非确定性地从M1的一个终结状态转移到M2的初始状态。
  • Kleene星号:M包含M1的所有状态和所有转移，M1的终结状态也是M的终结状态，此外M还有一个新的初始状态s，这个新初始状态也是终结状态，并且这个新初始状态转移到M1的初始状态，同时所有的终结状态都可以接受e转移到M1的初始状态。
  • 补:只用交换它们的终结状态和非终结状态。
  • 交
• 定理2.3.2:一个语言是正则的当且仅当它被有穷自动机接受。
  • 证明:M是一台有穷自动机，要构造一个正则表达式R，使得$L(M) = L(R)$。我们将$L(M)$表示为许多简单语言的并，设 K ={q1,…qn},且s=q1.令R(i,j,k)为$\Sigma^*$中可以使M从状态qi转移到状态qj且不经过编号大于k的所有字符串。两端的状态qi和qj的编号可以大于k。因此我们能得到以下的形式：$L(M)=\cup ${$R(i,j,n):q_j \in F$}。
• 常见的一个题型是构造一个有穷自动机接受的语言的正则表达式。首先可以先把这个自动机构造为，具有唯一终结状态且没有进入初始状态的转移和没有离开终结状态的转移。那么接下来我们需要做的就是一个”消节点”的操作，也就是说所有经过状态q接受的字符串都已经考虑过(这里通常就是加上一个该状态自循环的klnee星号)。
• 另外一个题型就是反方向的，给定正则语言利用定理2.3.1的证明方法构造一台自动机接受这个语言。

example

• L = {$w \in $ {a,b}$^*$:𝑤 has neither 𝑎𝑎 nor 𝑏𝑏 as a substring} is regular
  • 解释:我们可以构造一个有穷自动机，它只有一个起始状态，从起始状态接受a到达q1，从q1如果再接受a那么就进入一个非法状态不会终止，接受b到达q2。从q2接受a返回q1。这样的设计我们使q1只有接受a才能到达，q2只有接受b才能到达。
• 虽然正则语言在连接上是封闭的，但是不意味着𝐿1 ∘ 𝐿2 is regular, then either 𝐿1 or 𝐿2 is regular.
• 一个结论是如果L是正则的，那么$L^{R}$是正则的。我们要构造一个新的NFA，记为 $N^R$，它能接受 $L^R$。构造 $N^R$我们将通过以下三个步骤来“反转” $N$：步骤 1：反转所有转移；步骤 2：交换初始和接受状态；步骤 3：处理多初始状态（技术点）一个标准的NFA只有一个初始状态，但 $N$ 可能有多个接受状态，这导致 $N^R$ 有了多个初始状态。我们可以轻松解决这个问题：创建一个全新的唯一初始状态 $q’{new}$。从 $q’{new}$ 添加 $\epsilon$-转移（空转移）到所有 $N$ 的原接受状态（即 $F$ 中的所有状态）。

2.4 正则语言与非正则语言

• 泵定理:
  • 性质： 如果一个语言 $L$ 是正则的，那么存在一个常数 $p$（泵长度），对于 $L$ 中任何长度 $\ge p$ 的字符串 $s$，都可以将 $s$ 分解为 $s = xyz$，并满足：$y$ 不是空串 ($|y| > 0$)。$s$ 开头的 $p$ 个字符内必定包含 $y$（$|xy| \le p$）。（关键） $xy^iz$ 对于所有 $i \ge 0$ 都属于 $L$。

chapter 3 上下文无关语言

3.1 上下文无关文法

定义

• 一个上下文无关文法 $G$ 是一个四元组 $G = (V, T, P, S)$，其中：
  1. $V$：非终结符集合 (Variables / Non-terminals)这是一个有限集合，包含了所有可以被替换的“语法变量”。它们通常用大写字母表示，如 $A, B, C, S$。它们代表了语言中的抽象语法结构（例如 “表达式”、”语句”、”名词短语”）。
  2. $T$：终结符集合 (Terminals)这是一个有限集合，包含了构成语言最终字符串的基本符号或“词汇”。它们通常用小写字母、数字或符号表示，如 $a, b, c, 0, 1, +, *$。$V$ 和 $T$ 必须是不相交的 ($V \cap T = \emptyset$)。
  3. $P$：产生式规则集合 (Productions)这是一个有限集合，定义了非终结符如何被替换（或“展开”）。每个产生式的形式为： $A \to \alpha$左侧 $A$：必须是 $V$ 中的一个非终结符。右侧 $\alpha$ (alpha)：是由 $V$ 和 $T$ 中符号组成的任意字符串（即 $\alpha \in (V \cup T)^*$）。$\alpha$ 可以是空字符串 ($\epsilon$)。
  4. $S$：起始符号 (Start Symbol)这是 $V$ 中的一个特殊非终结符 ($S \in V$)，它代表整个语言（或程序、句子）的最高层语法结构，是所有推导的起点。

3.2 语法分析树

1. 🌲 什么是语法分析树？语法分析树是一个有序的、有根的树，它具有以下几个关键属性：

   1. 根节点 (Root)： 根节点的标号必须是文法的起始符号 ($S$)。
   2. 内部节点 (Internal Nodes)： 所有的内部节点（非叶子节点）的标号必须是非终结符 ($V$)。
   3. 叶子节点 (Leaf Nodes)： 所有的叶子节点（没有子节点的节点）的标号必须是终结符 ($T$) 或者是空字符串 ($\epsilon$)。
   4. 产生式规则 (Production Rule)： 这是最关键的一条。如果一个内部节点 $A$ 有 $n$ 个子节点，从左到右依次为 $X_1, X_2, \dots, X_n$，那么在文法 $G$ 中必须存在一个产生式 $A \to X_1 X_2 \dots X_n$。如果一个节点 $A$ 只有一个子节点 $\epsilon$，那么必须存在产生式 $A \to \epsilon$。
   5. 树的产物 (Yield):将语法分析树的所有叶子节点从左到右拼接起来，得到的字符串就是该树所推导出的终结符字符串。

2. 推导 (Derivations) 与语法分析树

   • 一个语法分析树是“推导”过程的结果。有两种主要的推导方式：
   • 最左推导 (Leftmost Derivation): 在推导的每一步，总是选择最左边的非终结符进行替换。
   • 最右推导 (Rightmost Derivation): 在推导的每一步，总是选择最右边的非终结符进行替换。
   • 关键点： 对于一个明确的 (Unambiguous) 语法分析树，它唯一对应一个最左推导，也唯一对应一个最右推导。但一个字符串可能存在多种推导（例如先推导左子树再推导右子树，或者反过来），但只要它们最终构成了同一棵树，它们在语法上就是等价的。

3. 歧义性

   • 一个文法 $G$ 被称为歧义的 (Ambiguous)，如果对于 $L(G)$ 中至少一个字符串 $w$，存在两棵或更多不同的语法分析树。

3.3 下推自动机

巧妙的设计

• 为了解决”有限内存”问题，PDA在NFA的基础上只增加了一个无限的，但受限的内存设备:一个栈。这个栈（Stack）具有“后进先出”(Last-In, First-Out, LIFO) 的特性。Push (压入)： 将一个符号放到栈顶。Pop (弹出)： 移除栈顶的符号。

3.4 上下文无关语言与下推自动机

3.5 上下文无关语言与非上下文无关语言

chapter 4–图灵机

4.1 图灵机的定义

定性描述

• ⚙️ 图灵机的驱动 (工作原理)图灵机是一个抽象的计算设备，它由三个核心部件驱动：
  1. 无限长的纸带 (Infinite Tape)这是图灵机的“内存”。它被分成一个个连续的“单元格 (cell)”。每个单元格可以写入一个符号（比如 ‘0’, ‘1’, ‘a’, ‘b’ 或空白符 ‘$\sqcup$’）。在计算开始时，输入字符串被写在纸带上，其余所有单元格都是空白。关键： 内存是无限的。这解决了 FA (有限内存) 和 PDA (一个栈) 的局限性。
  2. 读写头 (Read/Write Head)这是图灵机的“处理器”。在任意时刻，读写头都指向纸带上的一个单元格。它可以做三件事：读取 (Read)：查看当前单元格中的符号。写入 (Write)：擦除当前单元格的符号，并写入一个新符号（可以是同一个）。移动 (Move)：向左移动一个单元格，或向右移动一个单元格。
  3. 有限状态控制器 (Finite State Control)这是图灵机的“程序”或“大脑”。它和 FA (有穷自动机) 一样，是一个有限的状态机。在任意时刻，机器都处于一个“当前状态” (e.g., $q_4$)。

形式化表达

• 图灵机被形式化地定义为一个五元组 $M = (K, \Sigma, \delta, s, H)$，其中：
  • $K$：一个有限的状态集合（finite set of states）。
  • $\Sigma$：一个字母表（alphabet），并具有以下性质：包含 ⊔（空白符号）和 $\lhd$（左端符号）。不包含 $\to$（右移）和 $\leftarrow$（左移）这两个符号。
  • $s$：初始状态（initial state），其中 $s \in K$。
  • $H$：停机状态的集合（set of halting states），其中 $H \subseteq K$。
  • $\delta$：转移函数（transition function）。它将一个非停机状态和当前带上符号映射到一个新状态和（一个新符号或一个移动方向）。其定义域和值域为：$$\delta: (K - H) \times \Sigma \to K \times (\Sigma \cup {\leftarrow, \to})$$

格局的定义

• 一个”格局”就是图灵机在某一时刻的完整“快照”。这个定义使用一个三元组 $(q, u, v)$ 来表示这个快照：
  • $q \in K$这是机器当前的状态。
  • $u \in \lhd\Sigma^*$这是在读写头左侧的纸带内容。它始终以左端符号 $\lhd$ 开头。
  • 一个更清晰的、等价的定义 $V$ (代表 $v$ 所在的集合) 应该是：$$V = (\Sigma^+ \setminus {\sqcup}) \cup {\epsilon}$$我们来分解这个修正后的、更规范的定义：$\Sigma^+$：这代表 $\Sigma^*\Sigma$，即“所有长度至少为1的非空字符串”的集合。${\sqcup}$：这是一个只包含“空白符号 $\sqcup$”这一个字符串的集合。$\Sigma^+ \setminus {\sqcup}$：这是“所有非空字符串”的集合，减去（排除掉）那个仅由一个空白符号 $\sqcup$ 组成的字符串。$\cup {\epsilon}$：最后，我们再并上“空字符串 $\epsilon$” (你笔记中的 $e$)。

4.2 图灵机的计算

图灵机计算的定义

• 用于“计算”或“判定”的图灵机 $M = (K, \Sigma, \delta, s, H)$ 有一个特定结构：专门的停机状态：停机状态集 $H = {y, n}$。$y$ 代表“yes”（接受）。$n$ 代表“no”（拒绝）。两种停机格局：接受格局 (Accepting Configuration)：当前状态 $q = y$ 的停机格局。拒绝格局 (Rejecting Configuration)：当前状态 $q = n$ 的停机格局。
• 下面是机器 $M$ 如何处理一个输入字符串 $w$ 的过程：
  • 输入字母表 (Input Alphabet)：$\Sigma_0 \subseteq \Sigma - {\sqcup, \lhd}$。这是 $M$ 接受的“真正”的输入符号，它不包括空白符 $\sqcup$ 和左端符 $\lhd$。
  • 初始格局 (Initial Configuration)：对于输入 $w \in \Sigma_0^*$，机器从格局 $(s, \lhd\sqcup w)$ 开始运行。
  • 接受 (Accepts)：$M$ 接受 (accepts) $w$，如果 $(s, \lhd\sqcup w)$ 最终产生 (yields) 一个接受格局。
  • 拒绝 (Rejects)：$M$ 拒绝 (rejects) $w$，如果 $(s, \lhd\sqcup w)$ 最终产生 (yields) 一个拒绝格局。
  • 判定 (Decides)：这是最关键的一步，它结合了“接受”和“拒绝”。机器 $M$ 判定 (decides) 一个语言 $L \subseteq \Sigma_0^*$，如果对于所有字符串 $w \in \Sigma_0^*$ 都满足：如果 $w \in L$，那么 $M$ 接受 $w$（即停机在 $y$ 状态）。如果 $w \notin L$，那么 $M$ 拒绝 $w$（即停机在 $n$ 状态）。
• A language $L$ is recursive if $\exists$ (there exists) a TM that decides $L$.（如果存在一个图灵机能够判定语言 $L$，那么 $L$ 就是递归的。）

递归可枚举语言 (Recursively Enumerable, R.E.)

• 这是一个新的语言类别。定义：一个语言 $L$ 被称为递归可枚举的 (Recursively Enumerable, R.E.)，如果存在一个图灵机 $M$ 能够半判定 (semidecide) $L$。
• “半判定” (Semidecides)，有时也称为“识别” (Recognizes)，它的要求比我们之前谈到的“判定” (Decides) 要弱。
  • 判定 (Decides) - (我们上次讨论的递归语言):如果 $w \in L$，$M$ 停机并回答 Yes ($y$ 状态)。如果 $w \notin L$，$M$ 停机并回答 No ($n$ 状态)。关键： 无论如何，机器总会停机。
  • 半判定 (Semidecides) - (本次讨论的 R.E. 语言):如果 $w \in L$，$M$ 停机 (进入一个停机状态)。如果 $w \notin L$，$M$ 永不停机 (它会无限循环，或无限向右读写)。
• 定理：递归语言 必定是 R.E. 的Theorem: If $L$ is a recursive language, then it is R.E.(如果一个语言是递归的，那么它一定是递归可枚举的。)
  • 证明思路 (来自你的笔记)：这个定理说明“判定”是一种“半判定”的特殊情况。我们可以把任何“判定机” $M$ 轻松地转换成“半判定机” $M’$。

递归语言的性质

图灵机的核心用途

• 用途一：作为语言判定器 (Deciding Languages)这是图灵机作为“识别器”的角色。
  • 目标: 回答一个判定性问题，即 “Is $w \in L$?” (字符串 $w$ 是否在语言 $L$ 中?)。
  • 约定 (Convention):给定一个输入字符串 $w$，该字符串由不包含 $\sqcup$ (空白) 和 $\lhd$ (左端) 的符号组成，即 $w \in (\Sigma - {\sqcup, \lhd})^*$。$M$ 在输入 $w$ 上的初始格局 (initial configuration) 被统一定义为 $(s, \lhd\sqcup w)$。
  • (然后，机器会像我们之前讨论的那样，通过进入 $y$ 或 $n$ 状态来“接受”或“拒绝”这个 $w$。)
• 用途二：作为函数计算器 (Computing Functions)这是图灵机作为“计算机”的角色。
  • 目标: 计算一个函数 $f: \Sigma_0^* \to \Sigma_0^*$，即把一个输入字符串 $w$ 转换为一个输出字符串 $y$。
  • 输出的定义 (Output):$M$ 同样从初始格局 $(s, \lhd\sqcup w)$ 开始运行 (其中 $w \in \Sigma_0^*$ )。机器运行后，最终停机。如果停机时的格局是 $(h, \lhd\sqcup y)$，其中 $h \in H$ 是一个停机状态，$y$ 也是一个 $\Sigma_0^*$ 中的字符串。那么，这个留在纸带上的字符串 $y$ 就被称为 $M$ 在输入 $w$ 上的输出 (output)，记作 $M(w)$。
  • “M 计算 f” (M computes f):如果对于所有可能的输入 $w \in \Sigma_0^*$，图灵机 $M$ 的输出 $M(w)$ 总是等于 $f(w)$，我们就说 $M$ 计算 (computes) 了函数 $f$。
  • A function $f$ is recursive if $\exists$ a TM $M$ computes $f$.(如果存在一个图灵机 $M$ 能够计算 $f$，那么函数 $f$ 就是递归的。)

4.3 图灵机的扩展

Multiple Tapes

• 形式化定义

  • 一个 $k$-带图灵机 (k-tape TM) 仍然是一个五元组 $M = (K, \Sigma, \delta, s, H)$，其中 $K, \Sigma, s, H$ 的定义与普通（单带）图灵机相同。关键区别在于转移函数 $\delta$：输入：它在 $(K-H)$（非停机状态）中读取所有 $k$ 个读写头当前指向的符号 ( $\Sigma^k$ )。输出： 它决定一个新的状态 ( $K$ )，以及为 $k$ 条带中的每一条指定一个动作（写入新符号，或向左/右移动）。

• 多带图灵机的格局 (Configuration)

  • 一个 $k$-带图灵机的“格局”（瞬时快照）需要包含：当前状态 $q \in K$。$k$ 对纸带描述（每对描述一条纸带的读写头左侧内容 $u$ 和右侧内容 $v$）。

• 当使用 $k$-带图灵机进行计算时，有如下标准约定：

  • 输入：输入字符串 $w$ 被放置在第一条纸带 (Tape 1) 上。
  • 初始化：所有其他的纸带（Tape 2 到 Tape k）初始时都是空白，并且它们的读写头都位于最左端的 $\lhd\sqcup$ 处。
  • 输出：计算结束后，第一条纸带 (Tape 1) 上的内容被视为机器的输出。其他纸带的内容将被忽略。

• 定理：在多带、多带头、双向无穷带或多维带的图灵机，它们判定或半判定的任何语言以及计算的任何函数，都分别可用标准Turing机判定、半判定计算。

4.4 非确定性图灵机

The definition of a non-deterministic TM

• 一个非确定性图灵机 $M$ 是一个五元组 $M = (K, \Sigma, \Delta, s, H)$：$K$: 有限状态集合。$\Sigma$: 磁带字母表（包含 $\sqcup$ 空白符和 $\lhd$ 初始标志符）。$H$: 停机状态集合，$H \subseteq K$。$s$: 初始状态，$s \in K - H$。$\Delta$: 转移关系。$\Delta \subseteq (K - H) \times \Sigma \times (K \times \Sigma \cup {\leftarrow, \rightarrow})$与标准 TM 的转移函数 $\delta$ 不同，$\Delta$ 是一个关系而非函数，这意味着对于一个给定的 $(q, a) \in (K-H) \times \Sigma$，可能存在零个、一个或多个满足关系的下一步动作。

NTM半判定语言

• 定义 4.5.1：NTM $M$ 接受一个输入 $w \in \Sigma - {\lhd, \sqcup}^*$ 当且仅当至少存在一条从初始配置 $s, \lhd \sqcup w$ 开始的计算路径能够到达某个停机配置 $(h, ua v)$，其中 $h \in H$。
  • 核心思想：只要计算树中有一条路径成功停机，机器就接受输入，即使可能存在许多不接受或不终止的计算路径。
  • 如果一个 NTM $M$ 半判定一个语言 $L$，则对所有输入 $w$，满足 $w \in L$ 当且仅当 $M$ 接受 $w$。

NTM判定语言

• 定义 4.5.2：NTM $M = (K, \Sigma, \Delta, s, y, n)$ 判定一个语言 $L \subseteq \Sigma - {\lhd, \sqcup}^*$ 必须满足以下两个条件：停机性 (Termination)：对于任何输入 $w$，存在一个自然数 $N$ (取决于 $M$ 和 $w$)，使得不存在一个配置 $\mathbf{C}$ 满足初始配置 $s, \lhd \sqcup w$ 经过 $N$ 步转移到达 $\mathbf{C}$ (即所有计算路径都在有限步内停机)。正确性 (Correctness)：$w \in L$ 当且仅当存在一条从 $s, \lhd \sqcup w$ 到达接受状态 $y$ 的路径，即 $s, \lhd \sqcup w \vdash_M^* (y, u a v)$。
  • 核心思想：判定要求所有计算路径都必须在有限步内停机，并且 $w \in L$ 当且仅当至少有一条路径到达接受状态 $y$。

NTM计算函数

• 一个 NTM $M$ 计算一个函数 $f: \Sigma - {\lhd, \sqcup}^* \to (\Sigma - {\lhd, \sqcup})^*$ 必须满足以下两个条件：停机性 (Termination)：对于任何输入 $w$，存在一个 $N$ (取决于 $M$ 和 $w$)，使得所有计算路径都在有限步内停机。正确性 (Correctness)：存在一条从 $s, \lhd \sqcup w$ 到达停机配置 $(h, u a v)$ 的路径，当且仅当 $u a = \lhd \sqcup$ 且 $v = f(w)$。
  • 核心思想：计算函数要求所有计算路径都必须停机，并且对于任何输入 $w$，所有停机的路径都必须产生唯一的正确输出 $f(w)$。

equal of NTM and TM

• 定理：NTM 与 TM 的等价性定理
  • 如果一个非确定性图灵机 (NTM) $M$ 能够：半判定一个语言 $L$，判定一个语言 $L$，或者计算一个函数 $f$，那么就存在一个标准（确定性）图灵机 (TM) $M’$，能够：半判定同一个语言 $L$，判定同一个语言 $L$，或者计算同一个函数 $f$。
• 证明：这个证明的目的是构造一个标准（确定性）图灵机 $M’$，使其能模拟非确定性图灵机 $M$ 的所有计算路径，从而证明 NTM 在计算能力上不强于 TM。
  • 🎯 证明目标构造一个标准 TM $M’$，使其在输入 $w$ 上半判定语言 $L$，即：$$w \in L \iff M’ \text{ 接受并停机}$$根据 NTM 的半判定定义，这等价于 $M’$ 必须确定 $M$ 在输入 $w$ 上是否存在一条停机并接受的计算路径。
  • 🌳 NTM 计算的本质计算树： NTM $M$ 在输入 $w$ 上的计算是一个分支过程，形成一棵计算树。非确定性限制： 假设对于 $M$ 的任何状态-符号组合 $(q, a)$，最多只有 $r$ 种可能的转移（即分支度 $\le r$）。我们将这 $r$ 种转移分别编号为 $1, 2, \ldots, r$。路径编码： $M$ 的任何一个 $k$ 步计算序列（一条路径）都可以用一个长度为 $k$ 的序列 $i_1, i_2, \ldots, i_k$ 来唯一确定，其中 $1 \le i_j \le r$。
  • 确定性 TM $M’$ 的构造（三磁带模型）$M’$ 是一个多磁带 TM，它将系统地使用广度优先搜索 (BFS) 策略探索 $M$ 的计算树。$M’$ 使用三条磁带：
    • Tape 1：输入带，始终保存原始输入 $w$（永不改变）。
    • Tape 3：地址/路径带，存储当前正在模拟的计算路径的编码 $\langle i_1 i_2 \ldots i_k \rangle \in {1, \ldots, r}^*$。用于引导模拟。
    • Tape 2：模拟带，用于模拟 NTM $M$ 在当前路径 $\langle i_1 \ldots i_k \rangle$ 下的磁带内容和磁头位置。

4.5 Grammer