行间公式索引

这个问题要求我们证明可识别语言类对于一个名为 "9/10" 的运算是封闭的。

1. 理解问题:
   • 可识别语言 (Recognizable Language): 一个语言 $L$ 是可识别的，如果存在一台TM $M$（称为识别器），对于任何输入 $w$：
   • 如果 $w \in L$，那么 $M$ 在 $w$ 上运行后会停机并接受。
   • 如果 $w \notin L$，那么 $M$ 在 $w$ 上运行时永不停机或停机并拒绝。关键是，对于不属于语言的输入，它不保证停机。
   • 封闭性 (Closure): 一个语言集合（如所有可识别语言）在某个运算下是封闭的，意味着对集合中的任何语言应用该运算，得到的结果仍然在该集合中。这里，我们要证明如果 $L$ 是可识别的，那么 $9/10(L)$ 也一定是可识别的。
   • 9/10 运算: 这个运算接受一个语言 $L$，生成一个新语言 $9/10(L)$。新语言的成员是形如 $x_1\#x_2\#...\#x_{10}$ 的字符串，其中至少有9个子串 $x_i$ 是属于原始语言 $L$ 的。
2. 证明思路:
   • 要证明 $9/10(L)$ 是可识别的，我们需要构造一台TM $M'$，它能识别 $9/10(L)$。
   • 我们已知存在一台TM $M$ 用于识别 $L$。我们的新机器 $M'$ 可以使用 $M$ 作为“子程序”。
   • 输入给 $M'$ 的是 $w = x_1\#...\#x_{10}$。$M'$ 的任务是判断这10个子串中，是否至少有9个被 $M$ 接受。
3. 分析实现级别描述:
   • 这个描述提出构建一个11纸带的TM $M'$。
   • 纸带分工:
   • 纸带1到10：每条纸带上放一个子串 $x_i$。这10条纸带将作为模拟 $M$ 的工作区。
   • 纸带11：作为“记分牌”或“状态记录器”，用来跟踪哪些子串已经被 $M$ 接受。
   • 步骤1：分配任务: $M'$ 首先解析输入 $w$，将10个子串 $x_1, ..., x_{10}$ 分别复制到纸带1到纸带10上。
   • 步骤2：并行模拟 (Dovetailing): 这是最关键的一步。我们不能一个接一个地在每个 $x_i$ 上完整地运行 $M$，因为如果某个 $x_i \notin L$，$M$ 可能会在它上面永不停机，导致 $M'$ 卡住，永远无法检查其他的 $x_j$。
   • 解决方法是并行模拟，也叫燕尾榫 (dovetailing)。$M'$ 以一种“轮询”或“分时”的方式在所有10条纸带上模拟 $M$。
   • 描述中的 "模拟 $M$ 的 1 步" 正是此意。$M'$ 在纸带1上模拟 $M$ 一步，然后在纸带2上模拟 $M$ 一步，...，直到在纸带10上模拟 $M$ 一步。完成一轮后，再回到纸带1开始下一轮。
   • 如果 M 在纸带 i 上接受，则将其记录在纸带 11 上：在每一轮模拟中，如果任何一个模拟实例（比如在纸带 $i$ 上的）进入了 $M$ 的接受状态，$M'$ 就在它的记分牌（纸带11）上做个标记，比如在第 $i$ 个位置写个'1'。
   • 步骤3：检查条件并决定:
   • 每完成一轮模拟后，$M'$ 都会检查记分牌（纸带11）上'1'的数量。
   • 如果'1'的数量达到了9个，意味着已经有9个子串被 $M$ 接受了。此时满足了 $9/10(L)$ 的条件，$M'$ 就可以立刻停机并接受输入 $w$。
   • 如果'1'的数量不足9个，就回到步骤2，继续进行下一轮的并行模拟。
4. 正确性分析:
   • 如果 $w \in 9/10(L)$：这意味着至少有9个 $x_i$ 属于 $L$。由于 $M$ 是 $L$ 的识别器，对于这9个（或更多）子串，模拟 $M$ 最终都会停机接受。因此，随着 $M'$ 一轮一轮地模拟下去，记分牌上的'1'的数量迟早会达到9。到那时，$M'$ 就会停机接受 $w$。
   • 如果 $w \notin 9/10(L)$：这意味着属于 $L$ 的子串数量少于9个（比如是8个或更少）。$M'$ 会持续地并行模拟。对于那8个属于 $L$ 的子串，模拟会最终接受，并在记分牌上记下8个'1'。但对于剩下的、不属于 $L$ 的子串，模拟 $M$ 可能会永不停机。因此，记分牌上的'1'的数量永远也达不到9。$M'$ 将会无限地执行步骤2和3的循环，永不停机。
   • 结论: $M'$ 对属于 $9/10(L)$ 的输入停机接受，对不属于的输入永不停机。根据定义，$M'$ 是 $9/10(L)$ 的识别器。因此，$9/10(L)$ 是可识别的。

高层描述 (High-level description) 是对TM算法最抽象的描述。它不关心读写头如何移动、纸带有几条等实现细节，只说明算法的逻辑。

1. 在输入 w=x1#x2#...#x10 上: 明确算法的输入。
2. 并行运行 M 在所有十个输入上: 这是描述的核心。"并行运行"是一个高层概念，它直接抓住了Dovetailing的精髓，即同时推进多个计算过程。在实现级别，我们用多纸带TM的分时模拟来实现它。在高层描述中，我们直接使用这个强大的概念。
3. 如果至少有 9 个接受，则接受: 这是算法的终止和接受条件。一旦并行模拟中的9个分支报告了“接受”，整个机器就接受。
4. 我们通过定义看到...: 这是一个简短的正确性论证。
   • 如果 $w \in 9/10(L)$，那么定义就保证了至少有9个 $x_i \in L$。由于 $M$ 识别 $L$，这9个并行分支最终都会接受，从而触发整台机器的接受。
   • 如果 $w \notin 9/10(L)$，那么接受的分支数量将永远少于9。因此，接受条件永远不会被满足。由于某些分支可能会永远运行，整台机器也可能永远运行，即“不接受”（这符合识别器的定义，不接受可以是拒绝或循环）。

这个问题是问题4的泛化版本。

1. 理解 m/n 运算:
   • 输入不再是固定的10个子串，而是 $n$ 个子串，其中 $n$ 是输入的一部分。
   • 接受条件也不再是固定的9个，而是 $m$ 个，其中 $m$ 也是输入的一部分。
   • 输入格式为 <(m, n, x1#...#xn)>，它编码了阈值 $m$、子串总数 $n$ 以及 $n$ 个子串本身。
2. 新挑战:
   • 正如“注意”部分指出的，问题4的方法（使用11条纸带）在这里失效了。因为一台图灵机的纸带数量是固定的，是在设计时就确定好的。我们不能设计一台“有 $n+1$ 条纸带”的TM，因为 $n$ 是输入，是可变的。
   • 我们需要一个更通用的方法来实现并行模拟，这个方法不能依赖于有足够多的纸带。
3. 分析高层实现:
   • 这个实现描述了一种在单条纸带上（或固定数量纸带上）模拟任意多个并行计算的方法。
   • 核心思想: 用一个逐步增加的“步数限制”来代替分时轮询。
   • 步骤1：初始化计数器: 将计数器变量设置为 1。这个计数器（我们称之为 s）代表本轮模拟中，每个子任务被允许运行的总步数。
   • 步骤2：有限步数的并行模拟:
   • 在每个 xi 上模拟 M ... "计数器" 步: 这一步是算法的关键。$M'$ 会依次对每个 $x_i$ (从 $i=1$ 到 $n$) 进行模拟。
   • 对于 $x_1$，模拟 $M$ 最多 $s$ 步。
   • 然后，清空现场，对于 $x_2$，从头开始模拟 $M$ 最多 $s$ 步。
   • ...
   • 对于 $x_n$，从头开始模拟 $M$ 最多 $s$ 步。
   • 在这一大轮中，如果任何一个模拟在 $s$ 步内接受了，就记录下来。
   • 步骤3：检查条件: 在完成对所有 $n$ 个子串的 $s$ 步模拟后，检查记录下来的已接受的子串数量。如果数量达到 $m$，则整台机器接受。
   • 步骤4：增加资源并重试: 如果接受数量不足 $m$，说明当前的步数限制 $s$ 可能太小了，那些需要更多步数才能被接受的计算还没有完成。于是，我们将计数器 s 加一，然后回到步骤2，用更大的步数限制（$s+1$）重新进行所有模拟。
4. 正确性分析:
   • 如果 $w \in m/n(L)$: 意味着至少有 $m$ 个子串 $x_i$ 属于 $L$。对于每个这样的 $x_i$，识别器 $M$ 会在有限步数内接受它。假设这 $m$ 个子串分别需要 $s_1, s_2, ..., s_m$ 步。令 $S_{max} = \max(s_1, ..., s_m)$。当 $M'$ 的计数器 s 增长到 $S_{max}$ 时，在第 $S_{max}$ 轮大循环中，对这 $m$ 个子串的模拟都将在给定的 $S_{max}$ 步数限制内完成并接受。此时，$M'$ 在步骤3会发现已有 $m$ 个接受，于是停机并接受 $w$。
   • 如果 $w \notin m/n(L)$: 意味着属于 $L$ 的子串数量少于 $m$ 个。无论计数器 s 变得多大，最多也只能有少于 $m$ 个模拟会报告接受。因此，步骤3的接受条件永远不会满足。$M'$ 将无限地增加计数器 s 并重复模拟过程，即永不停机。
   • 结论: $M'$ 是 $m/n(L)$ 的识别器。因此该语言是可识别的。

这个问题要求我们为语言 CYCLE 设计一个非确定性图灵机 (Nondeterministic Turing Machine, NTM)。

1. 理解语言 CYCLE:
   • 语言的成员是图 $G$ 的编码 $\langle G \rangle$。
   • 条件是图 $G$ 包含至少一个循环 (cycle)。
   • 一个循环是一个非空的路径，其起点和终点是同一个顶点。这意味着图中有某个顶点 $v$，存在一条从 $v$ 出发，经过一个或多个其他顶点（或不经过），最终能回到 $v$ 的路径。
   • 换句话说，一个图有环，当且仅当存在一个顶点 $v$ 可以到达它自身。
2. 非确定性图灵机 (NTM):
   • 与确定性TM（DTM）不同，NTM的转移函数 $\delta(q, a)$ 可以返回一个状态、写入符号和移动方向的组合的集合。
   • 这意味着在计算的某一步，NTM可以有多种选择，可以同时走向多个不同的计算分支。
   • NTM接受一个输入，如果至少有一个计算分支进入接受状态。
   • NTM的强大之处在于它的“猜测”能力。我们可以把它看作是：NTM可以非确定性地（即靠运气或魔法）“猜”一个东西，然后确定性地“验证”这个猜测是否正确。
3. 分析所给的 NTM $N'$ 的设计:
   • 输入: $\langle G \rangle$，一个图的编码。
   • 步骤1：非确定性选择 (猜测): 非确定性地选择 G 中的一个顶点 v。
   • 这是NTM的核心能力。想象NTM在这一步分裂成多个并行的宇宙。如果图 $G$ 有 $k$ 个顶点 $\{v_1, ..., v_k\}$，NTM就分裂成 $k$ 个计算分支。第一个分支选择了 $v_1$，第二个分支选择了 $v_2$，以此类推。每个分支都“猜”了一个不同的顶点。
   • 步骤2：确定性验证: 运行...用于 REACHABILITY 的 NTM N 在 上。
   • REACHABILITY 是一个语言，定义为 $\{\langle G, s, t \rangle \mid \text{图 } G \text{ 中存在一条从顶点 } s \text{到顶点 } t \text{ 的路径}\}$。
   • 我们假设已经有一个NTM $N$ 可以判定（或识别）REACHABILITY。（实际上REACHABILITY是可判定的）。
   • 在每个计算分支中，我们都调用这个 $N$ 作为子程序，来检查我们猜测的顶点 $v$ 是否能到达它自己。也就是说，我们检查 $\langle G, v, v \rangle$ 是否在 REACHABILITY 语言中。
   • 步骤3：输出结果: 并输出 N 的输出。
   • 如果某个分支（比如猜测了顶点 $v_i$）发现 $v_i$ 可以到达自身，那么这个分支上的 $N$ 就会接受。根据NTM的接受定义，整个NTM $N'$ 也就接受了输入 $\langle G \rangle$。
4. 正确性分析:
   • 如果 $G$ 包含一个循环:
   • 根据循环的定义，必然存在某个顶点 $v^*$，它位于一个环上，因此 $v^*$ 可以到达自身。
   • 在 $N'$ 的非确定性选择步骤中，必然有一个计算分支会“猜”中这个正确的顶点 $v^*$。
   • 在这个分支上，调用 $N$ 来检查 $\langle G, v^*, v^* \rangle$。因为 $v^*$ 确实可以到达自身，所以 $N$ 会接受。
   • 由于至少有一个分支接受了，所以 $N'$ 最终会接受 $\langle G \rangle$。
   • 如果 $G$ 不包含循环:
   • 这意味着图中没有任何顶点可以到达自身。
   • 无论 $N'$ 在步骤1中非确定性地选择了哪个顶点 $v$，当它调用 $N$ 来检查 $\langle G, v, v \rangle$ 时，由于 $v$ 无法到达自身，$N$ 都将拒绝（或不接受）。
   • 因为所有的计算分支都最终走向了拒绝，所以 $N'$ 最终会拒绝 $\langle G \rangle$。
5. 结论:
   • 这个NTM $N'$ 正确地判定了语言 CYCLE。它在图有环时接受，在图无环时拒绝。