非确定型图灵机与可判定语言的证明

"CHAP3new.doc" 在文档"CHAP3new.doc"中，主要讨论了可判定性、非确定型图灵机（NTM）和枚举器等概念，以及图灵机的形式定义和一些相关的问题。以下是这些概念的详细说明： 1. 可判定性：推论3.12表明，一个语言是可判定的当且仅当存在非确定型图灵机（NTM）可以判定它。这意味着如果有一个确定型判定器M，那么M自然也是非确定型的，因为它只需按照固定的路径进行计算。反之，如果存在非确定型判定器N，我们可以构造一个确定型判定器M来等效模拟N的所有可能的不确定分支。通过深度优先的方式遍历所有分支，M会在某一分支遇到接受状态时接受输入，或者遍历完所有分支后拒绝输入。 2. 非确定型图灵机（NTM）：NTM可以在每个步骤中选择多种可能的操作，这使得它能够同时探索多个计算路径。在证明中，介绍了如何通过确定型图灵机M来模拟非确定型图灵机N的工作，利用深度优先搜索策略处理N的不确定性分支。 3. 枚举器的形式定义：枚举器E是一个特殊的图灵机，它能够顺序地产生一个语言的所有元素。E有状态集合Q，带字母表(，输入字母表(，初始状态q0，接受状态qaccept和拒绝状态qreject。转移函数描述了E如何在不同的状态下操作，包括读取、改写、移动和打印操作。枚举器的起始格局是q0后面跟着一个空格。 4. 图灵机形式定义的问题解答： a. 图灵机可以在其带子上写下空白符，因为空白符是带字母表的一部分。 b. 带字母表(和输入字母表(不能相同，因为输入字母表不包含空白符，而空白符是图灵机在带子上进行操作的基础标记。 c. 图灵机的读写头在连续的两步中可以处于同一个位置，例如，当读写头在带子的左侧并且向左移动时，由于不允许机器离开带子的边界，所以它会停留在左侧。 d. 图灵机不能只包含一个状态，因为至少需要两个状态来区分接受和拒绝，即qaccept和qreject。 3.6中的问题没有完全解答，但提到M不一定是判定器，意味着在处理某些情况时可能不会停机，这暗示了对于非判定问题的存在。 "CHAP3new.doc"涵盖了图灵机理论的关键部分，特别是可判定性、非确定性以及这些概念如何应用于解决问题。这些知识是理解计算理论和复杂度理论的基础。