问题复杂性 ●●●●● ●●●● ●●0 ●●●● 图灵机分为两类: ●确定性图灵机 ●非确定性图灵机 2021/2/10
2021/2/10 问题复杂性 ⚫ 图灵机分为两类： ⚫ 确定性图灵机。 ⚫ 非确定性图灵机
问题复杂性(续) ●●●●● ●●●● ●●0 ●●●● 确定性图灵机。 确定性图灵机的输出结果只取决于输入和初始状态. 因此,对于具有相同输入和初始状态,运行一个确 定性图灵机所得到的结果是完全相同的 ●非确定性图灵机: ●能够进行猜测。 ●求解一个问题分两个阶段:猜测阶段和验证阶段。 2021/2/10
2021/2/10 问题复杂性（续） ⚫ 确定性图灵机。 ⚫ 确定性图灵机的输出结果只取决于输入和初始状态。 ▪ 因此，对于具有相同输入和初始状态，运行一个确 定性图灵机所得到的结果是完全相同的。 ⚫ 非确定性图灵机 ： ⚫ 能够进行猜测。 ⚫ 求解一个问题分两个阶段：猜测阶段和验证阶段
图灵机 ●●●●● ●●●● ●●0 ●图灵机包括一个有限状态控制单元、k(≥1)条纸 带(Tape)和k个读写头( Tapehead)。 有限状态控制单元控制每个读写头访问一条纸带,并沿 着纸带左右移动 图灵机求解问题的输入是一个有限长度的字符串,该输 入占据每条纸带无限个单元的最左边的有限个单元。 ●读写头对纸带的一次访问称之为一个合法移动 (Move) 2021/2/10
2021/2/10 图灵机 ⚫ 图灵机包括一个有限状态控制单元、k（≥1）条纸 带（Tape）和k个读写头（Tapehead）。 ⚫ 有限状态控制单元控制每个读写头访问一条纸带，并沿 着纸带左右移动 ⚫ 图灵机求解问题的输入是一个有限长度的字符串，该输 入占据每条纸带无限个单元的最左边的有限个单元。 ⚫ 读写头对纸带的一次访问称之为一个合法移动 （Move）
图灵机(续) ●●●●● ●●●● ●●0 ●●●● ●图灵机求解问题时,被赋予一个初始状态 ( Initial state),且一步一步地移动,从而完成 对输入的扫描。 ●如果图灵机最终扫描了整个输入串,且满足了中止条件 而停止下来,则称图灵机识别了该输入。 ●否则,图灵机在某一点没有合法移动,因此会没有识别 输入串而停止下来,此时称图灵机无法识别该输入。 图灵机所识别的一个输入,称为一种可识别语言的一个 实例。 2021/2/10
2021/2/10 图灵机（续） ⚫ 图灵机求解问题时，被赋予一个初始状态 （Initial State），且一步一步地移动，从而完成 对输入的扫描。 ⚫ 如果图灵机最终扫描了整个输入串，且满足了中止条件 而停止下来，则称图灵机识别了该输入。 ⚫ 否则，图灵机在某一点没有合法移动，因此会没有识别 输入串而停止下来，此时称图灵机无法识别该输入。 ⚫ 图灵机所识别的一个输入，称为一种可识别语言的一个 实例
图灵机(续) ●●●●● ●●●● ●●0 例如:请设计一个图灵机,用于证明某个非负整 数是否能被3整除 解:设该图灵机谓DIV3 图灵机的组成:1个有限状态控制单元、1条纸带、1个读写头 输入用二进制表示,且在最后加一个“空”表示输入结束 有限状态控制 单元 读写头 01空 纸带 识别一个输入是否可以被3整除的图灵机示意图 2021/2/10
2021/2/10 图灵机（续） ⚫ 例如：请设计一个图灵机，用于证明某个非负整 数是否能被3整除。 解：设该图灵机谓 DIV3 图灵机的组成：1 个有限状态控制单元、1 条纸带、1 个读写头。 输入用二进制表示，且在最后加一个“空”表示输入结束。 有限状态控制 单元 读写头 纸带 识别一个输入是否可以被3整除的图灵机示意图 1 1 0 1 空