第三章丘奇图灵论题.ppt

2020 3 8 1 第3章丘奇 图灵论题 研究内容图灵机图灵机的变形算法的定义 2020 3 8 2 图灵机概述 图灵机与有穷自动机相似 但它具有无限大容量的存储且任意访问内部数据 是一种精确的通用计算机模型 能模拟实际计算机的所有计算行为图灵机具有以下两个性质具有有穷描述过程必须是由离散的 可以机械执行的步骤组成 2020 3 8 3 图灵机基本模型 基本模型包括一个有穷控制器一条含有无穷多个带方格的输入带一个读写头 2020 3 8 4 图灵机的标准 图灵机设计必须满足的三条标准它们应该是自动机 即在构造和功能等一般特点上应该和前面研究过的装置相同在描述 形式化定义和讨论方式它们应该尽量简单就可完成的计算而言它们应该尽量简单 2020 3 8 5 图灵机的动作 当读写头扫描输入带上一格 即输入一个字符 时 结合图灵机的当前状态 在有限控制器的控制下 图灵机将执行以下三个动作进行状态转移读写头在带上当前格写下新的符号决定读写头向右或者向左移一格 2020 3 8 6 与有穷自动机的区别 图灵机在带子上既然读也能写图灵机的读写头既然向左也能向右移动图灵机的带子是无限长的图灵机进入拒绝和接受状态将立即停机 2020 3 8 7 图灵机与语言 对于带上一串输入字符 图灵机从初始状态和带上最左边的字符开始 通过连续不断的扫描和执行相关动作 如果在某个时候进入终止状态 图灵机就接受输入串被一个图灵机所接受的全部字符串的集合 就是该图灵机所接受的语言设计图灵机M1 使得如果输入是B 0 1 的成员 它就接受 否则就拒绝 2020 3 8 8 图灵机的形式化定义 图灵机M是一个7元组 Q q0 qaccept qreject 其中Q 都是有穷集合 并且Q是状态的有穷集合 相当于程序标号 是输入字母表 不包含空白符 或者B 是带符号表 或者B 作为 中除 符号之外唯一特殊边界符q0开始状态 q0 Q 对于一个给定的输入串 M从状态q0启动 读头正注视着输入带最左端的符号接受状态qaccept Q 拒绝状态qreject Q 转移函数 Q qaccept qreject Q L R 2020 3 8 9 图灵机M是一个7元组 Q q0 B F 其中Q 都是有穷集合 并且Q是状态的有穷集合 是输入字母表 不包含空白符B 是带符号集 B q0 Q是初始状态F Q是终止状态 Q Q L R 称为转移函数 对某些状态q和某些带符号a q a 可以定义 进入拒绝状态 图灵机的形式化定义 1 2020 3 8 10 Q Q R L 是 为M的移动函数 q xi p y R 表示M在状态q读入符号X 将状态改为p 并在这个X所在的带方格中印刷符号Y 然后将读头向右移一格x1 xi 1qxi xn x1 xi 1ypxi 1 xn q xi p y L 表示M在状态q读入符号X 将状态改为p 并在这个X所在的带方格中印刷符号Y 然后将读头向左移一格x1 xi 1qxi xn x1 pxi 1yxi 1 xn图灵机所能接受的语言为L M w q0w M 1p 2 p F 状态转移函数 2020 3 8 11 状态图表示法 如果有 qi b qj c R 读b写c 且右移 则可表示为 2020 3 8 12 开始时 M以最左边的n个带方格接收输入 1 2 n 带的其余部分保持空白 空白符不在 中 一旦被M读到则表示输入结束读写头从最左边的带方格开始运行 开始运行后 计算根据转移函数所描述的规则进行 一直持续到它进入接受或拒绝状态 然后停机如果二者都不发生 则M将永远运行下去 图灵机计算过程 2020 3 8 13 图灵机的格局表示 图灵机计算过程中以当前状态 当前带内容和读写头当前位置组合在一起称为图灵机的格局 或称为瞬像 以uqv表示 其q表示当前状态 字符串uv表示当前带内容 读写头的当前位置为v的第一个字符前例如1011q701111表示格局 当前带内容为101101111 当前状态为q7 读写头当前字符是字符中第二个0 2020 3 8 14 图灵机格局产生 如果图灵机能合法地从C1格局迁移到C2格局 则称格局C1产生格局C2 其形式化表示为设a b c u v qi qj Q uaqibv uqjacv 或uacqjv 是两个格局如果 qi b qj c L 则称uaqibv产生uqjacv或者 qi b qj c R 则称uaqibv产生uacqjv 2020 3 8 15 端点格局 但当格局位于两个端点时会发生特殊变化M在输入w上的起始格局q0w 表示机器处于起始状态 并且读写头处于带子的最左端接受格局 uqacceptv 返回true拒绝格局 uqrejectv 返回false接受和拒绝状态是停机状态 2020 3 8 16 图灵机与语言 图灵机M接受输入 如果存在格局的序列C1 C2 Ck 使得C1是M在输入上的初始格局每个Ci产生Ci 1Ck是接受格局M接受的字符串的集合称为M的语言 或被M识别的语言 记为L M 2020 3 8 17 一个图灵机M识别一个输入串w 可能会遇到下面三种情况 进入终止状态 即在格局推导过程中能够进入一个格局x1 xi 1qxi xn 其中q F 此时图灵机停机 并接受串w未进入终止状态 但推导过程停止 即在格局推导过程中进入一个格局x1 xi 1qxi xn 使得q F 但 q xi 没有定义 此时图灵机停机 但不接受w陷入死循环 即在格局演化过程中 一直不能进入终止状态 但 一直有定义 图灵机对输入串永不停机 图灵机与语言 2020 3 8 18 如果一个语言能被某一图灵机识别 则称该语言是图灵可识别的判定器 对于所有输入都停机的图灵机 即可能因接受而停机 也可能因拒绝而停机定义3 3 如果一个语言能被某一图灵机判定 则称该语言是图灵可判定的由于很难区分机器是进入循环还是需要耗费长时间的运行 因此图灵可识别可以有两种状态 有限步接受停机 也可能进入循环或长时间运行而不拒绝 图灵可识别 2020 3 8 19 定义 设L是一个语言 若存在一个图灵机M使得L L M 则称L为一个递归可枚举语言 如果存在一个图灵机 Q q0 B F 使得L L M 而且对于任意输入串w M对w都停机 则称L是一个递归语言递归语言类是递归可枚举语言类的一个真子类 递归与递归可枚举 2020 3 8 20 定义 对函数f i1 i2 ik 若存在一个图灵机实现f的计算 对某些输入可能不停机 则称f是一个部分递归函数 若存在一个图灵机M实现f的计算 而且对任意一组输入 i1 i2 ik 图灵机M都停机 则称f是一个完全递归函数 部分递归与完全递归 2020 3 8 21 图灵机的例子 例题4 构造图灵机M1识别语言A 02n n 0 例题5 构造图灵机M2识别语言B w w w 0 1 例题6 构造图灵机M3识别语言C aibjck i j k i j k 1 例题7 构造图灵机M4识别语言E x1 x2 xL xi 0 1 且对任意i j 有xi xj 2020 3 8 22 图灵机的例子 2020 3 8 23 图灵机的例子 2020 3 8 24 图灵机的例子 2020 3 8 25 图灵机的例子 构造图灵机M5识别语言D 0n1n n 1 构造图灵机M6 Q 1 q0 B q5 其中Q q0 q1 q2 q3 q4 q5 B 1 动作函数 如下 2020 3 8 26 图灵机计算整函数的例子 构造图灵机实现下面的函数计算 构造思路 图灵机的输入串形式为0m10nBB 首先从左边的 0 块中把最左边的 0 改写为B 然后读写头向右边移动到右边的 0 块最左边的 0 改写为 1 读写头来回移动 重复上述过程两种结果 左边改写完备 右边剩下0 右边改写完备 左边剩下0 此时0的个数就是结果 2020 3 8 27 图灵机计算整函数的例子 计算函数f m n 的图灵机形式表示为M Q 0 1 0 1 B q0 B Q q0 q1 q2 q3 q4 q5 q6 转移函数 定义如下 q0 0 q1 B R q0 1 q5 B R q1 0 q1 0 R q1 1 q2 1 R q2 0 q3 1 R q2 1 q2 1 R q2 B q4 B L q3 0 q3 0 L q3 1 q3 1 L q3 B q0 B R q4 0 q4 0 L q4 1 q4 B L q4 B q6 0 R q5 0 q5 B R q5 1 q5 B R q5 B q6 B R 考虑输入串0010和输入串0100运行格局 2020 3 8 28 图灵机计算整函数的例子 构造图灵机实现函数f m n m n输入串的形式依然为0m10nBB 初始状态q0下 左边 0 块中擦去一个0 进入状态q1 字符串为B0m 110nBB 在q1状态下 重复m 1遍地做相同的工作 在左边一块中擦去一个 0 把最右边的 0 块复制一遍 并与 1 分隔 得 Bm10n10n1 0n10nB 依次将最右边的 0 块左移一位 重复m次 得 Bm0n mB 2020 3 8 29 图灵机设计 设计一个图灵机M 它接受所有首字符不再出现的串w 0 1 除空串外 要设计的图灵机所接受的语言为01 10 图灵机的形式表示为 M Q 0 1 0 1 B q0 B B q1 B Q q0 B q1 0 q1 1 q1 B 转移函数 定义如下 q0 B 0 q1 0 0 R q0 B 1 q1 1 1 R q1 0 1 q1 0 1 R q1 1 0 q1 1 0 R q1 0 B q1 B B L q1 1 B q1 B B L 2020 3 8 30 图灵机设计 设计一个图灵机M 它把读写带上的非空白字符串整体右移两位图灵机的形式表示为 M Q q1 B B B q2 x x B x Q qi A1 A2 i 1 2 A1 A2 转移函数 定义如下 q1 B B ai q1 B ai x R q1 B ai aj q1 ai aj x R q1 ai aj ak q1 aj ak ai R q1 ai aj ai R q1 aj B ai R q1 aj B B q2 B B aj L q2 B B aj q2 B B aj L q2 B B x q2 B x B L q2 B x x q2 x x B R 2020 3 8 31 图灵机的变形 有多种形式的图灵机模型 称为变形图灵机 或称为扩充图灵机 它们与原来的模型具有相同的识别能力 能识别相同的语言类稳健性 在形式变化中保持不变的性质 2020 3 8 32 多带图灵机 多带图灵机有多个带子 每个带子都有自己的读写头 用于读和写初始时 输入出现在第一个带子上 其他带子都是空白的转移函数改为允许多个带子同时进行读 写和移动读写头 Q k Q k R L S k qi a1 a2 ak qj b1 bk L R L 其意义是 若机器处于状态qi 读写头1到k所读的符号分别是a1到ak 则机器转移到状态qj 各读写头分别写下符号b1到bk 并按 函数指定的要求移动读写头 2020 3 8 33 多带图灵机 多带图灵机的动作函数可表示为 Q k Q k R L S k q a1i a2j akr p b1i A1 b2 A2 bk Ak 其中asi bsi表示第s条带上的字符 As R L S 2020 3 8 34 多带图灵机 定理3 8 每个多带图灵机等价于某一个单带图灵机证明 设M有k条带子 S把此k条带子的信息都存储在它的唯一带子上 并以新符号 作为定界符号以分开不同带子的内容 而且在每段的某个符号上加点标记读写头的位置 2020 3 8 35 多带图灵机 推论3 9 一个语言是图灵可识别的 当且仅当存在多带图灵机识别它定理 语言L能够被多带图灵机接受 则L也可以被一个单带图灵机接受 2020 3 8 36 非确定型图灵机 非确定型图灵机在计算过程中 机器可以在多种可能性动作中选择一种继续进行转移函数具有如下形式 Q P Q R L 非确定型图灵机的计算过程是一棵树 不同分支对应机器不同的可能性 如果计算的某个分支导致接受状态 则机器接受输入 2020 3 8 37 非确定型图灵机 定理3 10 每个非确定性图灵机都等价于某一个确定性图灵机证明思路 2020 3 8 38 非确定型图灵机 推论3 11 一个语言是图灵可识别的 当且仅当存在非确定性图灵机识别它推论3 12 一个语言是可判定的 当且仅当存在非确定性图灵机判定它 2020 3 8 39 枚举器 图灵机有三种功能语言识别器函数计算装置语言产生系统 即用一个图灵机枚举出一个语言的各个句子 2020 3 8 40 枚举器 定理13 一个语言是可识别的 当且仅当存在枚举器枚举它证明 定理 一个语言是递归可枚举语言当且仅当存在图灵机M 使得L G M 证明 2020 3 8 41 双向无限带图灵机 双向无限带图灵机的读写带可以向左 右两个方向无限延伸 2020 3 8 42 双向无限带图灵机 双向无限带图灵机的格局可以像基本图灵机模型那样定义 只是在左边界不同当动作函数 q x1 p y L 时 基本图灵机模型是不能再向左推导的 但在双向无限带图灵机中却有相应的格局推导 qx1x2 xn PByx2x3 xn定理 语言L被一个双向无限带图灵机接受当且仅当它被一个单向无限带图灵机接受 2020 3 8 43 与其它模型的等价性 图灵机能够模拟现代电子计算机的一种极限模型 随机存取机随机存取机RAM是满足下列条件的的一种计算装置有无限多个存储单元 依次编号为0 1 2 每个单元可以存储任意整数有有限多个寄存器 用于做运算 每个寄存器可以存放任意整数 整数可以编码成计算机指令如果选择适当的指令集合 随机存取机可以模拟任何现代数字计算机图灵机与随机存取机具有相同的能力 2020 3 8 44 各种图灵机的等价性 图灵机的本质特征 无限制地访问无限的存储器具有此特点的所有模型在能力上都是等价的 只要它们满足一些合理的必要条件 2020 3 8 45 各种图灵机的等价性 计算模型之间的普遍等价性 任何两个满足合理条件的计算模型都能相互模拟 从而在能力上等价这种普遍等价性从哲学解释了计算模型与算法之间的关系 计算模型可以多种多样 但所描述的算法却只有一个 即算法本质上由问题决定 而计算模型却与所用语言有关 2020 3 8 46 算法的定义 关于算法的问题 什么是算法 在使用和描述算法时依赖什么 2020 3 8 47 希尔伯特问题 设计一个通过有限多次运算就可以决定的过程来检测一个多项式是否有整数根 2020 3 8 48 关于算法 所谓算法 就是求解某一特定类型问题的一组有穷规则 这些规则是确定的 可执行的和可终止的一个算法有输入和输出从本质上说 一个算法就是一个对任何输入都停机的确定图灵机 2020 3 8 49 关于算法 对于任何输入 算法都应该能够终止 否则 只能称其为 计算 过程如果某个图灵机使用永不停机的方式表示对某个输入串不能够接受的话 该图灵机就不是算法 接受递归语言的图灵机是算法 接受递归可枚举语言的图灵机不一定是算法 2020 3 8 50 算法的描述 描述算法有三种基本形式形式描述需要详细给出图灵机的状态定义 转换函数的定义 是最详细程度的算法描述实现描述通常使用自然语言描述图灵机的动作 如读 写头的移动 怎样存储数据等 不需要给出具体的状态转换函数的描述高水平描述采用自然语言描述 忽略了图灵机的实现模型 即通常意义上的算法描述 2020 3 8 51 丘奇 图灵命题 图灵 丘奇和克林尼分别提出了图灵机 演算 和递归函数几种计算模型 这三种模型被证明为等价的 如果其中一种模型可以作为衡量可计算性的标准 则其他两种模型当然也可以作为衡量可计算性的标准丘奇 图灵论题 一个函数是可计算的当且仅当它是图灵机可计算的 一个函数是可计算的当且仅当它是 可定义的图灵机能够模拟现代电子计算机的一种极限模型 随机存取机 可以为丘奇 图灵论题提供强有力支持 2020 3 8 52 丘奇 图灵命题 丘奇 图灵论题 对任何可以用有效算法解决的问题 都存在解决此问题的图灵机有效算法说明的可解性概念是形式化的 不严格的 即只能列出算法的有限性 机械可执行性 确定性和终止性等特征图灵机的概念是形式化的和严格的图灵机作为人们普遍接受的计算模型 使得算法被集中在可以用图灵机描述的计算上 这样算法的可计算性问题等同于图灵机的可计算问题 2020 3 8 53 丘奇 图灵命题 在所有输入上都停机的任何图灵机就是算法反过来 不能变换成在所有输入上都停机的图灵机的任何东西都不能被认为是算法已经可以肯定存在不可计算的函数 即存在计算机不可判定的问题 但什么样的函数是可计算的 什么样的函数是不可计算的 2020 3 8 54 NP问题和P问题 对于一个问题Q 如果存在一个确定的 对任何输入都停机的 的图灵机在多项式时间内求解 则问题Q必然存在多项式时间的计算机算法 但对于不确定的图灵机 却未必有相应的结论用DTM在多项式时间内求解的问题类称为P类问题 用NTM在多项式时间内可解的问题类称为NP类问题 P NPNP P 问题是计算机理论中尚未解决的最重要问题之一 许多问题已被证明为NP类问题 却不能证明它们是否属于P类问题 2020 3 8 55 描述图灵机的术语 算法的描述方式形式化描述 详尽地写出图灵机的状态 转移函数等实现描述 使用日常语言来描述图灵机的动作 如怎么移动读写头 怎么在带上存储数据等高层描述 使用日常语言来描述算法 但忽略实现的模型 2020 3 8 56 图灵机带符号集的简化 定理 如果L 0 1 是一个递归可枚举语言 则L可以被一个只有三个带符号 0 1 B 的单带图灵机接受证明思路 将L的图灵机M带符号集 中的每个符号用k位0 1编码代替 新图灵机M2每扫描k次带符号 才实现图灵机M的一个动作 从而用M2实现了M的动作模拟 2020 3 8 57 图灵机编码 对于一个图灵机 只要按顺序给出它们全部转移函数 就可以知道它的基本结构 决定它们的实际功能假设图灵机 Q q1 B F 的带符号集 和状态集Q分别是 X1 X2 Xs Q q1 q2 qn 则可以对图灵机的转移函数 q xi qk xl Dm Dm L R 进行编码 写成0i10j10k10l10m的形式 并称它为一个编码段一个编码段由5个全0子串按一定的顺序组成 每个全0子串的长度分别是转移函数中对应符号的序号 用字符1隔开 2020 3 8 58 图灵机编码 每个转移函数对应一个0 1编码段 各编码段之间用11隔开 整个转移函数对应的0 1编码段用111表示结束和开始一个图灵机的标准编码形如 111编码段 1 11编码段 2 11 11编码段 r 111其中r为图灵机对应的转移函数个数 2020 3 8 59 图灵机编码例子 设有图灵机M q1 q2 q3 0 1 0 1 B q1 B q2 其中转移函数 为 q1 1 q3 0 R q3 0 q1 1 R q3 1 q2 0 R q3 B q3 1 L 对状态集中的各个状态 带符号集中的各个字符 以及左右移动一格分别编码为q1 q2 q30 1 BL R0 00 0000 00 0000 00则图灵机M的标准编码为 11101001000101001100010101001001100010010010100110001000100010010111 2020 3 8 60 通用图灵机 根据丘奇 图灵论题 图灵机应该是现代数字计算机形式化的描述应该存在一个图灵机 它可以实现对所有图灵机的模拟 即该图灵机可以实现所有有效的算法 称该图灵机为通用图灵机通用图灵机就是能够模拟所有图灵机的图灵机 2020 3 8 61 通用图灵机 为了使通用