Part4图灵机及可计算理论 主讲教师贺利坚 2 Part4主要内容提示 3 一 图灵机及形式定义 1 图灵机2 图灵机的形式定义3 图灵机接受的语言 4 图灵机 FA和PDA的局限FA有有限的存储 只能处理RLPDA用栈提供无限的存储 但栈只能后进先出 PDA只能处理CFLFA和PDA不能用作通用的计算模型 5 图灵机是通用的计算模型 是计算机的数学模型图灵在论述 有些数学问题是不可解的 时 提出了图灵机图灵论题 凡是可计算的函数 都可以用图灵机计算丘奇论题 任何计算 如果存在一个有效过程 它就能被图灵机实现提出TM的目的在于 对有效的计算过程 即算法 进行形式化的描述 忽略模型的存储容量在内的一些枝节问题 只考虑算法的基本特征 图灵提出TM具有以下两个性质具有有穷描述 过程必须是由离散的 可以机械执行的步骤组成 图灵机 6 图灵生平1912年出生 演算能力突出1931年 进剑桥大学学数学1936年 提出图灵机模型1938年 获普灵斯顿大学博士学位1950年 发表论文 计算机和智能 提出图灵测试1951年 成为英皇家学会院士1954年 不幸去世 现代计算机设计思想的创始人 人工智能领域的开拓者计算机领域的最高奖以图灵命名 图灵机 7 AlanTuring 1912 1954 1912 23June Birth Paddington London1926 31 SherborneSchool1930 DeathoffriendChristopherMorcom1931 34 UndergraduateatKing sCollege CambridgeUniversity1932 35 Quantummechanics probability logic1935 ElectedfellowofKing sCollege Cambridge1936 TheTuringmachine computability universalmachine1936 38 PrincetonUniversity Ph D Logic algebra numbertheory1938 39 ReturntoCambridge IntroducedtoGermanEnigmaciphermachine1939 40 TheBombe machineforEnigmadecryption1939 42 BreakingofU boatEnigma savingbattleoftheAtlantic1943 45 ChiefAnglo Americancryptoconsultant Electronicwork 1945 NationalPhysicalLaboratory London1946 Computerandsoftwaredesignleadingtheworld 1947 48 Programming neuralnets andartificialintelligence1948 ManchesterUniversity1949 Firstseriousmathematicaluseofacomputer1950 TheTuringTestformachineintelligence1951 ElectedFRS Non lineartheoryofbiologicalgrowth1952 Arrestedasahomosexual lossofsecurityclearance1953 54 Unfinishedworkinbiologyandphysics1954 7June Death suicide bycyanidepoisoning Wilmslow Cheshire 8 图灵机的物理模型基本模型包括一个有穷控制器 一条含有无穷多个带方格的输入带 一个读头 一个移动将完成以下三个动作 改变有穷控制器的状态 在当前所读符号所在的带方格中印刷一个符号 将读头向右或者向左移一格 图灵机 9 图灵机的形式定义 定义9 1图灵机 Turingmachine 基本的图灵机TMM Q q0 B F Q 状态的有穷集合 q Q为M的一个状态 输入字母表 a 为M的一个输入符号 除空白符号B外 只有 中的符号才能在M启动时出现在输入带上 带符号表 tapesymbol X 为M的一个带符号 表示在M的运行过程中 X可以在某一时刻出现在输入带上 q0 Q M的开始状态 M从状态q0启动 读头正注视着输入带最左端的符号 B 空白符 blanksymbol 含空白符的带方格是空的 F Q M的终止状态集 q F为M的一个终止状态 TMM一旦进入终止状态 它就停止运行 10 TMM Q q0 B F 称为移动函数 Q Q R L 为M的移动函数 transactionfunction q X p Y R 表示M在状态q读入符号X 将状态改为p 并在这个X所在的带方格中印刷符号Y 然后将读头向右移一格 q X p Y L 表示M在状态q读入符号X 将状态改为p 并在这个X所在的带方格中印刷符号Y 然后将读头向左移一格 图灵机的形式定义 11 例TMM1 q0 q1 q2 0 1 0 1 B q0 B q2 其中 的定义如下 q0 0 q0 0 R q0 1 q1 1 R q1 0 q1 0 R q1 B q2 B R M1的移动函数的另一种表示 图灵机的形式定义 q2 q2 B R q1 0 R q1 q1 1 R q0 0 R q0 B 1 0 状态 L M1 x x 0 1 且x中有且仅有一个1 12 补充 图灵机的转移图M1 q0 q1 q2 0 1 0 1 B q0 B q2 q0 0 q0 0 R q0 1 q1 1 R q1 0 q1 0 R q1 B q2 B R 当 q X p Y D 时 在q到p的弧上标记X YD D为 或 L M1 x x 0 1 且x中有且仅有一个1 图灵机的形式定义 13 图灵机接受的语言 定义9 2即时描述 instantaneousdescription ID 1 2 q Q 1q 2称为M的即时描述q为M的当前状态 M正注视着 2的最左符号 当M的读头注视的符号右边还有非空白符时 1 2为M的输入带最左端到最右的非空白符号组成的符号串 否则 1 2是M的输入带最左端到M的读头注视的带方格中的符号组成的符号串 14 设X1X2 Xi 1qXiXi 1 Xn是M的一个ID 如果 q Xi p Y R 则M的下一个ID为X1X2 Xi 1YpXi 1 Xn记作X1X2 Xi 1qXiXi 1 Xn MX1X2 Xi 1YpXi 1 Xn 设X1X2 Xi 1qXiXi 1 Xn是M的一个ID 如果 q Xi p Y L 则当i 1时 M的下一个ID为X1X2 pXi 1YXi 1 Xn记作X1X2 Xi 1qXiXi 1 Xn MX1X2 pXi 1YXi 1 Xn 图灵机接受的语言 15 Mn表示 M的n次幂 Mn M n M 表示 M的正闭包 M M M 表示 M的克林闭包 M M 在意义明确时 用 n 表示 图灵机接受的语言 16 例M1在处理输入串的过程中经历的ID变换序列M1 q0 q1 q2 0 1 0 1 B q0 B q2 图灵机接受的语言 M000100Bq2 M000100q1 M00000q0B M00010q11 M00010q10 M0000q00 M0001q101 M0001q100 M000q000 M000q0101 M000q0100 M00q0000 M00q00101 M1Bq2 M00q00100 M0q00000 M0q000101 M1q1 M0q000100 q000000 q0000101 q01 q0000100 4 00000 3 000101 2 1 1 000100 q0 0 q0 0 R q0 1 q1 1 R q1 0 q1 0 R q1 B q2 B R 17 定义9 3TM接受的语言TMM Q q0 B F L M x x 且q0 x M 1q 2 q F 1 2 只要在工作过程中能进入终止状态 之一 则可以判断被接受并停机 图灵机不停地计算 当输入被接受时 图灵机将停止 没有下一个动作 当因未定义转换函数 图灵机无法计算下去时 将拒绝执行 如果不进入任何接受或拒绝状态 继续执行下去 永不停止 在TM接受的语言中 包含那些不能使TM停机的输入 图灵机接受的语言 18 定义9 4TM接受的语言叫做递归可枚举语言 recursivelyenumerablelanguage r e 如果存在TMM Q q0 B F L L M 并且对每一个输入串x M都停机 则称L为递归语言 recursivelylanguage x是任意的串x L M进入接受状态并停机x L M也可以停机 但不进入接受状态M不能停机 则可能是r e 或其他语言可以按TM接受及停机分类 图灵机接受的语言 TM能够定义 TM能够计算 19 例M2 q0 q1 q2 q3 0 1 0 1 B q0 B q3 q0 0 q0 0 R q0 1 q1 1 R q1 0 q1 0 R q1 1 q2 1 R q2 0 q2 0 R q2 1 q3 1 R M2接受的语言是什么 图灵机接受的语言 M2接受的语言是字母表 0 1 上那些至少含有3个1的0 1符号串 借助其他描述方法的观察 20 M2 q0 q1 q2 q3 0 1 0 1 B q0 B q3 处理输入串的过程 图灵机接受的语言 思考 如何构造出接受字母表 0 1 上那些含且恰含有3个1的符号串的TM 关键 不读完不能进入终态 3 1001100101100 q01001100101100 1q1001100101100 10q101100101100 100q11100101100 1001q2100101100 10011q300101100 1 00010101 q000010101 0q00010101 00q0010101 000q010101 0001q10101 00010q1101 000101q201 0001010q21 00010101q3 2 000101000 q0000101000 0q000101000 00q00101000 000q0101000 0001q101000 00010q11000 000101q2000 0001010q200 00010100q20 000101000q2B 21 一 图灵机及形式定义 1 图灵机2 图灵机的形式定义3 图灵机接受的语言 AnyQuestion 22 Part4主要内容提示 23 二 图灵机的构造 1 一般构造方法2 TM作为非负整函数的计算模型3 状态的有穷存储功能的利用4 多道 multi track 技术5 子程序 subroutine 技术 24 一般构造方法 思路图灵机可以对输入带进行写操作写入一些标记即完成记忆 类似PDA的栈 但更丰富 图灵机还可以用状态标记工作状态 25 例构造TMM3 使L M 0n1n2n n 1 不能通过 数 0 1 或者2的个数来实现检查 用匹配的方法比较它们的个数是否相同 出现一个0 必然所有0后有1 所有1后有2 遇0后在带方格上印刷一个X 找到1后在带方格上印刷一个Y 再找到2后在带方格上印刷一个Z 带上为XX XYY YZZ ZB时接受例 对000111222 一般构造方法 000111222B X00111222B X00Y11222B X00Y11Z22B XX0Y11Z22B XX0YY1Z22B XX0YY1ZZ2B XXXYY1ZZ2B XXXYYYZZ2B XXXYYYZZZB 26 正常情况下 输入带上的符号串的一般形式为00 0011 1122 22TM经过一段运行 输入带上的符号串的一般情况为X X0 0Y Y1 1Z Z2 2BB如果能被接受X XX XY YY YZ