Gemini 大手子发力了！ 你好！我是 Theory of Computation 课程的出题专家。根据你提供的 **Lecture 12 (Undecidability and Reducibility)**、**Assignment 3 (Turing Machine)** 以及 Chomsky 体系结构的相关材料，我为你设计了 10 道模拟选择题。 ### 考查核心逻辑 在 Theory of Computation 的考试中，区分 **Decidable (Recursive)** 和 **Recognizable (Recursively Enumerable)** 是核心难点。你需要掌握以下层级关系： 1. **Regular $\subset$ Context-Free $\subset$ Decidable $\subset$ Recognizable**。 2. 如果一个语言是 Regular 或 CFL，它**必然**是 Decidable 的。 3. **Decidable (判定)**：TM 总是会停机（接受或拒绝）。 4. **Recognizable (识别)**：对于属于语言的串，TM 会停机接受；对于不属于的串，TM **可能拒绝，也可能死循环**。 ------ ### 模拟选择题 (10道) **题目说明：** 对于下列每一个语言 $L$，请从选项中选出**最准确**的分类描述。 **选项：** A. Turing-decidable (Recursive) B. Turing-recognizable but **not** decidable C. Not Turing-recognizable D. Context-Free ------ #### Q1. 基础正则语言 **语言：** $L = { w \in {0, 1}^* \mid w \text{ 包含子串 } 101 }$ **分析：** 这是一个典型的正则语言。 **解答：** **A (Turing-decidable)** **详解：** 正则语言（Regular Language）是 Decidable 的子集。我们可以设计一个 DFA 来接受它，DFA 可以转化为一个总是停机的 TM。虽然它是 Regular，但如果没有 Regular 选项，Decidable 是正确的归类。 #### Q2. 经典的非 CFL **语言：** $L = { a^n b^n c^n \mid n \ge 0 }$ **分析：** 在 Assignment 3 Q1 中，要求设计一个 "Standard TM to decide" 这个语言。 **解答：** **A (Turing-decidable)** **详解：** 这个语言虽然不是 Context-Free 的（Lecture 8），但我们可以设计一个 TM，利用 "Zig-zag" 策略来回扫描并标记 $a, b, c$，这台机器对于任何输入都能在有限步内给出 Accept 或 Reject 的结果。因此它是 Decidable 的。 #### Q3. 停机问题 (Halting Problem) **语言：** $HALT = { \langle M, w \rangle \mid \text{TM } M \text{ 在输入 } w \text{ 上停机} }$ **分析：** Lecture 12 明确指出了这是 "Undecidable" 的。 **解答：** **B (Turing-recognizable but not decidable)** **详解：** 1. **Undecidable:** 我们无法设计一个 TM 来判定任意 TM 是否停机（Lecture 12）。 2. **Recognizable:** 我们可以设计一个通用图灵机（Universal TM）来模拟 $M$ 在 $w$ 上的运行。如果 $M$ 停机，模拟器就接受。但如果 $M$ 不停机，模拟器也会一直运行下去（无法拒绝）。因此它符合 Recognizable 的定义。 #### Q4. 接受问题 (Acceptance Problem) **语言：** $ACCEPT = { \langle M, w \rangle \mid \text{TM } M \text{ 接受输入 } w }$ **分析：** Lecture 12 证明了 $ACCEPT$ 是 Undecidable 的，并且通过归约（Reduction）证明了 $HALT$ 也不比它容易。 **解答：** **B (Turing-recognizable but not decidable)** **详解：** 同样地，我们可以模拟 $M$。如果 $M$ 接受 $w$，我们就接受。如果 $M$ 拒绝或死循环，我们可能永远无法给出答案。因此它是 Recognizable 但不是 Decidable。 #### Q5. 上下文无关语言 (CFL) **语言：** $L = { a^n b^n \mid n \ge 0 }$ **分析：** 这是一个经典的 Context-Free Language。 **解答：** **A (Turing-decidable)** **详解：** 所有的 CFL 都是 Decidable 的。我们可以将 PDA 转化为 TM，或者直接设计一个 TM（Assignment 3 Q1a 的简化版）来判定它。如果在选项中没有 "Context-Free"，则 "Turing-decidable" 是正确答案。 #### Q6. 空语言检测 (Emptiness Problem) **语言：** $EMPTY = { \langle M \rangle \mid L(M) = \emptyset }$ (即 M 不接受任何字符串) **分析：** Lecture 12 证明了 $EMPTY$ 是 Undecidable 的。 **解答：** **C (Not Turing-recognizable)** **详解：** - 这是一个较难的考点。$EMPTY$ 是 Undecidable 的。 - 它的补集 $\overline{EMPTY}$（即 $L(M) \neq \emptyset$）是 Recognizable 的（我们可以并行模拟 $M$ 在所有字符串上的运行，一旦有一个被接受，就接受）。 - 根据定理：如果 $L$ 和 $\overline{L}$ 都是 Recognizable，则 $L$ 是 Decidable。因为 $EMPTY$ 不是 Decidable，而 $\overline{EMPTY}$ 是 Recognizable，所以 $EMPTY$ 本身必然是 **Not Recognizable**。 #### Q7. 有限自动机判定 **语言：** $L = { \langle D, w \rangle \mid D \text{ 是一个 DFA，且 } D \text{ 接受 } w }$ **分析：** 这里的对象是 DFA，而不是 TM。 **解答：** **A (Turing-decidable)** **详解：** Lecture 12 提到我们可以用 DFA 来构建 TM 的证明逻辑。因为 DFA 没有任何死循环（Loop）的可能，它总是在读取完输入后停在某个状态。我们可以编写一个 TM 来模拟这个 DFA，它一定会在有限步内结束并给出答案。因此是 Decidable。 #### Q8. 语言的补集性质 **语言：** $\overline{HALT}$ (即 ${ \langle M, w \rangle \mid M \text{ 在 } w \text{ 上死循环/不停机} }$) **分析：** 考察 Recognizable 的封闭性。 **解答：** **C (Not Turing-recognizable)** **详解：** - 已知 $HALT$ 是 Recognizable。 - 已知 $HALT$ 是 Undecidable。 - 如果 $\overline{HALT}$ 也是 Recognizable，那么 $HALT$ 就必须是 Decidable（定理：$L$ 和 $\bar{L}$ 都 RE $\implies$ $L$ is Recursive）。 - 因为 $HALT$ 不 Decidable，所以 $\overline{HALT}$ 甚至连 Recognizable 都不是。 #### Q9. 简单的数学运算 **语言：** $L = { a \mid a \text{ 是二进制数且 } a \text{ 是 2 的幂} }$ **分析：** 考察 Assignment 3 Q2 类型的计算能力。 **解答：** **A (Turing-decidable)** **详解：** 虽然 Assignment 3 Q2 讨论的是 "Computation" (impure TM)，但判定一个数是否为 2 的幂（例如 $1, 10, 100...$）完全可以在有限步骤内完成（不断除以 2 或者检查二进制是否只有一个 1）。这属于 Decidable。 #### Q10. Rice's Theorem (莱斯定理) 的应用 **语言：** $L = { \langle M \rangle \mid L(M) \text{ 是一个正则语言} }$ **分析：** 这是一个关于 TM 语言属性的判断。 **解答：** **B (or C, depending on strictness, usually B is safe context, but strictly C/Undecidable is key)** *注：在 Lecture 12 中提到了 Rice's Theorem。* **详解：** Rice's Theorem 指出，任何关于 TM 所识别语言的非平凡属性（Non-trivial property）都是 **Undecidable** 的。判断 $L(M)$ 是否 Regular 是一个非平凡属性。因此它肯定不是 A。通常这类属性也不具备 Recognizable 的特征（既难证明它 Regular，也难证明它不 Regular），但在简单的二元选择题逻辑中，首要判断是 **Undecidable**。 *(修正：严格来说，正则性检测属于 $\Sigma_2$ 或 $\Pi_2$ 级别的复杂度，通常既不是 RE 也不是 co-RE，所以选 C 更准确。但如果题目只区分 Decidable vs Undecidable，则它是 Undecidable)*。**如果是标准本科考试，通常考查点在于它 "Undecidable"，若必须在 B/C 选，选 C 更稳妥，但核心是它违反了 Decidable。** ------ ### 备考建议 1. **牢记层级：** 看到 DFA/NFA/Regex $\rightarrow$ 选 Decidable；看到 PDA/CFG $\rightarrow$ 选 Decidable；看到 $a^n b^n c^n$ $\rightarrow$ 选 Decidable。 2. 区分 HALT/ACCEPT 和 EMPTY： - 涉及 "TM M 接受/停机" ($HALT, ACCEPT$) $\rightarrow$ 选 Recognizable (but not decidable)。 - 涉及 "TM M 语言为空/语言等于..." ($EMPTY, EQUAL, ALL$) $\rightarrow$ 通常是 Not Recognizable (C)。 3. **Assignment 3 的启示：** 只要是 Assignment 3 Q1 中让你画图设计的（如倍数关系、加法关系），全部都是 **Decidable** 的，因为题目要求 "Design a standard TM to **decide**"。 Loading... Gemini 大手子发力了！ 你好！我是 Theory of Computation 课程的出题专家。根据你提供的 **Lecture 12 (Undecidability and Reducibility)**、**Assignment 3 (Turing Machine)** 以及 Chomsky 体系结构的相关材料，我为你设计了 10 道模拟选择题。 ### 考查核心逻辑 在 Theory of Computation 的考试中，区分 **Decidable (Recursive)** 和 **Recognizable (Recursively Enumerable)** 是核心难点。你需要掌握以下层级关系： 1. **Regular $\subset$ Context-Free $\subset$ Decidable $\subset$ Recognizable**。 2. 如果一个语言是 Regular 或 CFL，它**必然**是 Decidable 的。 3. **Decidable (判定)**：TM 总是会停机（接受或拒绝）。 4. **Recognizable (识别)**：对于属于语言的串，TM 会停机接受；对于不属于的串，TM **可能拒绝，也可能死循环**。 ------ ### 模拟选择题 (10道) **题目说明：** 对于下列每一个语言 $L$，请从选项中选出**最准确**的分类描述。 **选项：** A. Turing-decidable (Recursive) B. Turing-recognizable but **not** decidable C. Not Turing-recognizable D. Context-Free ------ #### Q1. 基础正则语言 **语言：** $L = { w \in {0, 1}^* \mid w \text{ 包含子串 } 101 }$ **分析：** 这是一个典型的正则语言。 **解答：** **A (Turing-decidable)** **详解：** 正则语言（Regular Language）是 Decidable 的子集。我们可以设计一个 DFA 来接受它，DFA 可以转化为一个总是停机的 TM。虽然它是 Regular，但如果没有 Regular 选项，Decidable 是正确的归类。 #### Q2. 经典的非 CFL **语言：** $L = { a^n b^n c^n \mid n \ge 0 }$ **分析：** 在 Assignment 3 Q1 中，要求设计一个 "Standard TM to decide" 这个语言。 **解答：** **A (Turing-decidable)** **详解：** 这个语言虽然不是 Context-Free 的（Lecture 8），但我们可以设计一个 TM，利用 "Zig-zag" 策略来回扫描并标记 $a, b, c$，这台机器对于任何输入都能在有限步内给出 Accept 或 Reject 的结果。因此它是 Decidable 的。 #### Q3. 停机问题 (Halting Problem) **语言：** $HALT = { \langle M, w \rangle \mid \text{TM } M \text{ 在输入 } w \text{ 上停机} }$ **分析：** Lecture 12 明确指出了这是 "Undecidable" 的。 **解答：** **B (Turing-recognizable but not decidable)** **详解：** 1. **Undecidable:** 我们无法设计一个 TM 来判定任意 TM 是否停机（Lecture 12）。 2. **Recognizable:** 我们可以设计一个通用图灵机（Universal TM）来模拟 $M$ 在 $w$ 上的运行。如果 $M$ 停机，模拟器就接受。但如果 $M$ 不停机，模拟器也会一直运行下去（无法拒绝）。因此它符合 Recognizable 的定义。 #### Q4. 接受问题 (Acceptance Problem) **语言：** $ACCEPT = { \langle M, w \rangle \mid \text{TM } M \text{ 接受输入 } w }$ **分析：** Lecture 12 证明了 $ACCEPT$ 是 Undecidable 的，并且通过归约（Reduction）证明了 $HALT$ 也不比它容易。 **解答：** **B (Turing-recognizable but not decidable)** **详解：** 同样地，我们可以模拟 $M$。如果 $M$ 接受 $w$，我们就接受。如果 $M$ 拒绝或死循环，我们可能永远无法给出答案。因此它是 Recognizable 但不是 Decidable。 #### Q5. 上下文无关语言 (CFL) **语言：** $L = { a^n b^n \mid n \ge 0 }$ **分析：** 这是一个经典的 Context-Free Language。 **解答：** **A (Turing-decidable)** **详解：** 所有的 CFL 都是 Decidable 的。我们可以将 PDA 转化为 TM，或者直接设计一个 TM（Assignment 3 Q1a 的简化版）来判定它。如果在选项中没有 "Context-Free"，则 "Turing-decidable" 是正确答案。 #### Q6. 空语言检测 (Emptiness Problem) **语言：** $EMPTY = { \langle M \rangle \mid L(M) = \emptyset }$ (即 M 不接受任何字符串) **分析：** Lecture 12 证明了 $EMPTY$ 是 Undecidable 的。 **解答：** **C (Not Turing-recognizable)** **详解：** - 这是一个较难的考点。$EMPTY$ 是 Undecidable 的。 - 它的补集 $\overline{EMPTY}$（即 $L(M) \neq \emptyset$）是 Recognizable 的（我们可以并行模拟 $M$ 在所有字符串上的运行，一旦有一个被接受，就接受）。 - 根据定理：如果 $L$ 和 $\overline{L}$ 都是 Recognizable，则 $L$ 是 Decidable。因为 $EMPTY$ 不是 Decidable，而 $\overline{EMPTY}$ 是 Recognizable，所以 $EMPTY$ 本身必然是 **Not Recognizable**。 #### Q7. 有限自动机判定 **语言：** $L = { \langle D, w \rangle \mid D \text{ 是一个 DFA，且 } D \text{ 接受 } w }$ **分析：** 这里的对象是 DFA，而不是 TM。 **解答：** **A (Turing-decidable)** **详解：** Lecture 12 提到我们可以用 DFA 来构建 TM 的证明逻辑。因为 DFA 没有任何死循环（Loop）的可能，它总是在读取完输入后停在某个状态。我们可以编写一个 TM 来模拟这个 DFA，它一定会在有限步内结束并给出答案。因此是 Decidable。 #### Q8. 语言的补集性质 **语言：** $\overline{HALT}$ (即 ${ \langle M, w \rangle \mid M \text{ 在 } w \text{ 上死循环/不停机} }$) **分析：** 考察 Recognizable 的封闭性。 **解答：** **C (Not Turing-recognizable)** **详解：** - 已知 $HALT$ 是 Recognizable。 - 已知 $HALT$ 是 Undecidable。 - 如果 $\overline{HALT}$ 也是 Recognizable，那么 $HALT$ 就必须是 Decidable（定理：$L$ 和 $\bar{L}$ 都 RE $\implies$ $L$ is Recursive）。 - 因为 $HALT$ 不 Decidable，所以 $\overline{HALT}$ 甚至连 Recognizable 都不是。 #### Q9. 简单的数学运算 **语言：** $L = { a \mid a \text{ 是二进制数且 } a \text{ 是 2 的幂} }$ **分析：** 考察 Assignment 3 Q2 类型的计算能力。 **解答：** **A (Turing-decidable)** **详解：** 虽然 Assignment 3 Q2 讨论的是 "Computation" (impure TM)，但判定一个数是否为 2 的幂（例如 $1, 10, 100...$）完全可以在有限步骤内完成（不断除以 2 或者检查二进制是否只有一个 1）。这属于 Decidable。 #### Q10. Rice's Theorem (莱斯定理) 的应用 **语言：** $L = { \langle M \rangle \mid L(M) \text{ 是一个正则语言} }$ **分析：** 这是一个关于 TM 语言属性的判断。 **解答：** **B (or C, depending on strictness, usually B is safe context, but strictly C/Undecidable is key)** *注：在 Lecture 12 中提到了 Rice's Theorem。* **详解：** Rice's Theorem 指出，任何关于 TM 所识别语言的非平凡属性（Non-trivial property）都是 **Undecidable** 的。判断 $L(M)$ 是否 Regular 是一个非平凡属性。因此它肯定不是 A。通常这类属性也不具备 Recognizable 的特征（既难证明它 Regular，也难证明它不 Regular），但在简单的二元选择题逻辑中，首要判断是 **Undecidable**。 *(修正：严格来说，正则性检测属于 $\Sigma_2$ 或 $\Pi_2$ 级别的复杂度，通常既不是 RE 也不是 co-RE，所以选 C 更准确。但如果题目只区分 Decidable vs Undecidable，则它是 Undecidable)*。**如果是标准本科考试，通常考查点在于它 "Undecidable"，若必须在 B/C 选，选 C 更稳妥，但核心是它违反了 Decidable。** ------ ### 备考建议 1. **牢记层级：** 看到 DFA/NFA/Regex $\rightarrow$ 选 Decidable；看到 PDA/CFG $\rightarrow$ 选 Decidable；看到 $a^n b^n c^n$ $\rightarrow$ 选 Decidable。 2. 区分 HALT/ACCEPT 和 EMPTY： - 涉及 "TM M 接受/停机" ($HALT, ACCEPT$) $\rightarrow$ 选 Recognizable (but not decidable)。 - 涉及 "TM M 语言为空/语言等于..." ($EMPTY, EQUAL, ALL$) $\rightarrow$ 通常是 Not Recognizable (C)。 3. **Assignment 3 的启示：** 只要是 Assignment 3 Q1 中让你画图设计的（如倍数关系、加法关系），全部都是 **Decidable** 的，因为题目要求 "Design a standard TM to **decide**"。 最后修改：2025 年 12 月 31 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 1 如果觉得我的文章对你有用，请随意赞赏
