计算理论基础章4

1第章图灵机许桂靖杨莹2Overview图灵机（TuringMachine，TM），是计算机的一种简单的数学模型。历史上，冯•诺曼计算机的产生就是由图灵机诱发的。丘奇—图灵论题：一切合理的计算模型都等同于图灵机.3类型文法结构产生式形式限制条件0短语结构文法α→βα∈Ｖ+,β∈Ｖ*PhraseStructure上下文有关文法α1Aα2→α1βα2|α1βα2|≥|α1Aα2|1ContextSensitiveα1，α2∈Ｖ*（CSG）A∈ＶＮ,β∈Ｖ+上下文无关文法A→αA∈ＶＮ,α∈Ｖ*2ContextFree（CFG）正右线性文法A→xB，C→yA,B,C∈ＶＮ3规文左线性文法A→Bx，C→yx,y∈ＶT*法4Overview0型语言———图灵机1型语言(CSL)———线性界限自动机2型语言(CFL)———下推自动机3型语言(正规集)——有限自动机5Overview图灵机所定义的语言类---递归可枚举集合图灵机所计算的整数函数类---部分递归函数以图灵机为模型,研究问题的可计算性，即确定该问题是可计算的、部分可计算的，还是不可计算的。6Overview4.1图灵机模型4.2图灵机的变化和组合4.3通用图灵机4.4图灵机可计算性74.1图灵机模型84.1图灵机模型定义4-1图灵机M=(K,Σ,Γ,δ,q0,B,F)，其中K是有穷的状态集合；Γ是所允许的带符号集合；B∈Γ，是空白符；ΣΓ，B∈Σ，是输入字符集合；FK，是终止状态集合。q0∈K,是初始状态；94.1图灵机模型δ：K×ΓK×Γ×{L,R,S}是图灵机的动作(状态转移)函数，这里L表示读头左移一格；R表示读头右移一格；S表示读头不动；δ(q,a)=(p,b,z)表示状态q下读头所读符号为a时，状态转移为p,读头符号变为b，同时读头变化为z.104.1图灵机模型定义4-2设当前带上字符串为x1x2…xn，当前状态为q，读头正在读xi，图灵机的瞬时描述ID为x1x2…xi-1qxi…xn114.1图灵机模型定义4-3设当前的瞬时描述ID1=x1x2…xi-1qxi…xn若有δ(q,xi)=(p,y,L)，则图灵机瞬时描述变为ID2=x1x2…xi-2pxi-1yxi+1…xn；若有δ(q,xi)=(p,y,R)，则图灵机瞬时描述变为ID2=x1x2…xi-1ypxi+1…xn。124.1图灵机模型定义4-3瞬时描述ID1经过一步变为瞬时描述ID2，称ID1与ID2具有一步变化关系，表示为ID1├ID2若ID1经过n步变为ID2(n≥0)，即有ID1├ID├…├ID2称ID1与ID2具有多步变化关系，简记为ID1├*ID2134.1图灵机模型定义4-4对于图灵机M=(K,Σ,Γ,δ,q0,B,F)，定义图灵机接受的语言集L(M)为L(M)={w|w∈Σ*∧u0uvqqf(u0∈Σ*∧u∈Σ*∧v∈Σ*∧q∈K∧qf∈F∧q0w├*u0qB├*uqfv)}144.1图灵机模型【例4-1】设计一个图灵机，使得L(M)={0n1n|n≥1}。设计思路:在带上每当将一个0变为X，就把一个1变为Y。当将所有的0变为X时，恰将所有的1变为Y，这个串就是合法的，最后将X、Y分别还原为0、1。154.1图灵机模型164.1图灵机模型【例4-2】设计一个图灵机，使之接受L(M)={wcw|w∈{a,b}*}设计思路：在c左侧，从左至右逐一字符，用状态记下它并标志该符号为已处理符号，移至c右侧对应位置后，判断是否是相同符号。若相同，再返回c左侧循环，直至所有符号比较完毕。最后将标志符号修改回原符号。在设计时，特别注意用状态存贮符号的方法，这是图灵机设计的重要方法之一。174.1图灵机模型184.1图灵机模型【例4-3】设计一个图灵机，计算自然数n的以2为底的对数。用一进制表示输入和输出值。an表示输入n,bm表示输出m.设计思路：从左到右扫描带，把所碰到的a划掉一个，留一个，并将计数器加1。重复此过程，直至a不复存在。这里，用字符c表示划掉的字符。194.1图灵机模型204.1图灵机模型【例4-4】设计一个图灵机，计算二个自然数m、n的减法：设计时，整数n用0n表示。开始时，带上符号为0m10n，结束时，带上符号为0。每当在1的左边将一个0改变为B，就在1的右边将一个0改为1，若1的右边无0时，再将左边改为B的0恢复回来。m-n若m≥nm－n=0否则214.1图灵机模型224.1图灵机模型【例4-5】设计图灵机实现数字从一进制表示到二进制表示的转换。这个图灵机的设计可以仿例4-3，不同在于每次循环时，要保留除以2的余数作为当前二进制位的值。注意这里首先计算出的是二进制的低位值，所以要将结果不断右移以插入新生成的位，生成的结果是低位在右端。初始时，整数n用an表示，结束时，带上是0、1构成的二进制数。234.1图灵机模型244.2图灵机的变化和组合4.2.1双向无穷带图灵机4.2.2多带图灵机4.2.3非确定图灵机4.2.4多头图灵机4.2.5多维图灵机4.2.6离线图灵机4.2.7图灵机的组合4.2.8枚举器4.2.9图灵机的组合254.2.1双向无穷带图灵机定理4-1L被一个具有双向无穷带的图灵机识别，当且仅当它被一个单向无限带的图灵机识别。证明：单向无限TM模拟双向无限TM，采用多道技术。264.2.2多带图灵机274.2.2多带图灵机【例4-6】设计一个二带图灵机，使得T(M)={ww|w∈{0,1}*}。这个问题的关键是比较字符串前后两个部分，为此，首先要对带上字符串计数：每二元素计数加1，按计数值将字符串分为前后两个部分，并将它们分别存放于不同带上，然后进行比较。284.2.2多带图灵机294.2.2多带图灵机【例4-7】设计二带图灵机，实现二进制到一进制的转换。设这个图灵机为M7，其第一带用作输入带，第二带用作输出带。设计思路是从左到右扫描输入带上的二进制字符，并使用公式r*2+b生成输出带上一进制数，其中r是当前输出带上的一进制数，b是当前输入带上扫描的字符，这里的r*2就是将原输出带上的一进制数r复制一遍。例如：1001的一进制数计算过程。304.2.2多带图灵机314.2.2多带图灵机定理4-2如果一个语言L被一个多带图灵机接受，它就能被一个单带图灵机接受。证明思想：用单带TM模拟n带TM运行。单带的第i格表示n带TM各带第i格的状态。单带TM第i格中符号记为：((ai1,bi1)(ai2,bi2)…(ain,bin))其中（aik,bik)表示n带TM中第k带上第i格的情形324.2.2多带图灵机其中（aik,bik)表示n带TM中第k带上第i格的情形aik表示n带TM中第k带上第i格的字母，bik表示n带TM中第k带上第i格的读头，0不是读头所在，1是读头单元格334.2.2多带图灵机用单带模拟δ(q,(a1,a2,…,an))=(p,(b1,b2,…,bn),(c1,c2,…,cn))S1从左向右描述单带中各道读头所在符号是否为(a1,a2,…,an)。S2从右向左扫描各读头所在符号，符号改为b,读头按c移动。344.2.2多带图灵机其中（aik,bik)表示n带TM中第k带上第i格的情形aik表示n带TM中第k带上第i格的字母，bik表示n带TM中第k带上第i格的读头，0不是读头所在，1是读头单元格354.2.2多带图灵机【例4-8】下面的图灵机就是不确定图灵机。无向图G中，从a出发合法路径判定的不确定型图灵机。364.2.3非确定图灵机非确定图灵机由一个有穷控制器、一条带和一个读头组成。对于一个给定的状态和被读头扫描的带符号，机器的下一个动作将有有穷个选择。设一个非确定图灵机M1=(K,Σ,Γ,δ,q0,B,F)，除转移函数δ外，其它同一般图灵机的定义。转移函数δ仍是从K×Γ到K×Γ×{L,R,S}上的映射，但它可能有多个映射的像,即存在q∈K,a∈Σ,δ(q,a)=(p1,b1,c1)δ(q,a)=(p2,b2,c2)……δ(q,a)=(pr,br,cr)374.2.3非确定图灵机定理4-3如果语言L被一个非确定图灵机M1接受，则L将被某个确定图灵机M2接受。384.2.4多头图灵机一个k头图灵机有k个读头，一个控制器和一条带，读头由1到k编号，图录机的一个动作由当前状态和被每个读头所扫描的符号。在一个动作中，每个读头独立地左移、右移或不动。定理4-4如果L被某个k个读头的图灵机接受，则它能被一个单头图灵机接受。394.2.5多维图灵机多维图灵机具有通常的有限控制器，但带却由k维单元阵列组成。这里，在所有2k个方向上（k个轴，每轴正、负两个方向），都是无限的，根据状态和扫视的符号，该装置改变状态，打印一个新的符号，在2k个方向上移动它的读头，开始时，输入沿着一个轴排列，读头在输入的左端。404.2.6离线图灵机定理4-5如果L被一个二维图灵机M1接受，那么L将被一个一维图灵机M2接受。414.2.7图灵机的组合424.2.7图灵机的组合【例4-9】设计一个TM，完成乘法运算m×n。开始时带上符号为：0m10n1，结束时带上符号为0mn，用子程序调用的方式完成。设计思想是：每当抹去左边一个０，就在第二个１后面拷贝n个０。当第一个１的左边全变为B时，带上就为10n10mn，再抹去10n1，带上就剩0mn，即为所求。设计Copy子程序这个子程序完成在第二个１拷贝n个０的操作。第1次被调用开始ID：B０m-11q10n1结束ID：B０m-11q50n10n第i次被调用开始ID：Bi０m-i1q10n10(i-1)n结束ID：Bi０m-i1q50n10(i-1)n在拷贝时，每当将一个０变成２，就在末尾写个０。当0n变为2n时，就已在右边加了0n。再将2变为0n。434.2.7图灵机的组合设计主ＴＭMM={q0,q6,q7,q8,q9,q10,q11,q12,q13},{0,1},{0,1,2,B},δ,q0,B,{q13})开始ID为q00m10n1，进入Copy入口ID为B0m-11q10n1，为此，δ(q0,0)=(q6,B,R)δ(q6,0)=(q6,0,R)δ(q6,1)=(q1,1,R)从Copy结束时的ID，进入主TM的开始ID(B0m-11q50n10n├Bq00m-110n10n)δ(q5,0)=(q7,0,L)δ(q7,1)=(q8,1,L)δ(q8,0)=(q9,0,L)δ(q9,0)=(q9,0,L)δ(q9,B)=(q0,B,R)善后处理：Bm1q50n10mn444.2.8枚举器454.2.8枚举器定理4-6一个语言是图灵可识别的，当且仅当有枚举器枚举它。证明：首先证明如果有枚举器E枚举语言L，则存在图灵机M识别L。构造M如下：对于任意输入串w，运行E。每当E输出一个串时，与w比较，相等，接受w，并停机。显然，M接受在E输出序列中出现过的那些串。现在证明若有图灵机M识别语言L，则有枚举器E枚举L。设L={w1，w2，w3，…}，构造E：对i=1,2,3,…,执行如下步骤（1）对w1，w2，w3，…,wi中的每一串，让M以其作为输入运行i步。（2）若在这个计算中，M接受wj，则打印wj，M接受w，它最终将出现在E的枚举打印中。事实上，它可能在E的列表在出现无限多次，因为每一次重复运行，M在每一个串上都从头开始运行。464.3通用图灵机(１)缓冲域带的最左面是标记符Ａ，Ａ的右边是|K|+|Γ|+2个单元构成的缓冲（|K|、|Γ|分别是状态集和字母集的元素数目）。(２)Ｍ的描述字域缓冲区域右边紧接的是Ｍ的描述字dM，以Ｂ为开始标志，以３个０结束。对于转移函数δ(q,a)=(q,a,d)，我们用五元组表示为(q,a,q,a,d)，将顺序调整为(q,a,a,d,q)。dM就是由这样的五元组组成的序列。对于每个五元组中的状态和字符，我们用其序号的一进表示，其间用０分隔，五元组间用２个０分隔。例如：若有δ(q２,０)=(q３,２,Ｌ)，表示成上面定义