计算理论第4章图灵机

《计算理论第4章图灵机》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章图灵机许桂靖杨莹1Overview图灵机（TuringMachine，TM），是计算机的一种简单的数学模型。历史上，冯•诺曼计算机的产生就是由图灵机诱发的。丘奇—图灵论题：一切合理的计算模型都等同于图灵机.2类型文法结构产生式形式限制条件0短语结构文法α→βα∈Ｖ+,β∈Ｖ*PhraseStructure上下文有关文法α1Aα2→α1βα2

2、α1βα2

3、≥

4、α1Aα2

5、1ContextSensitiveα1，α2∈Ｖ*（CSG）A∈ＶＮ,β∈Ｖ+上下文无关文法A→αA∈ＶＮ,α∈Ｖ*2ContextFree（CFG）正右线性文法A→xB，C→yA,B,C∈ＶＮ3规文左线性文法

6、A→Bx，C→yx,y∈ＶT*法3Overview0型语言———图灵机1型语言(CSL)———线性界限自动机2型语言(CFL)———下推自动机3型语言(正规集)——有限自动机4Overview图灵机所定义的语言类---递归可枚举集合图灵机所计算的整数函数类---部分递归函数以图灵机为模型,研究问题的可计算性，即确定该问题是可计算的、部分可计算的，还是不可计算的。5Overview4.1图灵机模型4.2图灵机的变化和组合4.3通用图灵机4.4图灵机可计算性64.1图灵机模型74.1图灵机模型定义4-1图灵机M=(K,Σ,Γ,δ,q0,B,F)，其中K是有穷的状态集合；Γ是所允许的带符

7、号集合；B∈Γ，是空白符；ΣΓ，B∈Σ，是输入字符集合；FK，是终止状态集合。q0∈K,是初始状态；﹨84.1图灵机模型δ：K×ΓK×Γ×{L,R,S}是图灵机的动作(状态转移)函数，这里L表示读头左移一格；R表示读头右移一格；S表示读头不动；δ(q,a)=(p,b,z)表示状态q下读头所读符号为a时，状态转移为p,读头符号变为b，同时读头变化为z.94.1图灵机模型定义4-2设当前带上字符串为x1x2…xn，当前状态为q，读头正在读xi，图灵机的瞬时描述ID为x1x2…xi-1qxi…xn104.1图灵机模型定义4-3设当前的瞬时描述ID1=x1x2…xi-1qxi…xn若

8、有δ(q,xi)=(p,y,L)，则图灵机瞬时描述变为ID2=x1x2…xi-2pxi-1yxi+1…xn；若有δ(q,xi)=(p,y,R)，则图灵机瞬时描述变为ID2=x1x2…xi-1ypxi+1…xn。114.1图灵机模型定义4-3瞬时描述ID1经过一步变为瞬时描述ID2，称ID1与ID2具有一步变化关系，表示为ID1├ID2若ID1经过n步变为ID2(n≥0)，即有ID1├ID├…├ID2称ID1与ID2具有多步变化关系，简记为ID1├*ID2124.1图灵机模型定义4-4对于图灵机M=(K,Σ,Γ,δ,q0,B,F)，定义图灵机接受的语言集L(M)为L(M)={w

9、w∈

10、Σ*∧u0uvqqf(u0∈Σ*∧u∈Σ*∧v∈Σ*∧q∈K∧qf∈F∧q0w├*u0qB├*uqfv)}134.1图灵机模型【例4-1】设计一个图灵机，使得L(M)={0n1n

11、n≥1}。设计思路:在带上每当将一个0变为X，就把一个1变为Y。当将所有的0变为X时，恰将所有的1变为Y，这个串就是合法的，最后将X、Y分别还原为0、1。144.1图灵机模型154.1图灵机模型【例4-2】设计一个图灵机，使之接受L(M)={wcw

12、w∈{a,b}*}设计思路：在c左侧，从左至右逐一字符，用状态记下它并标志该符号为已处理符号，移至c右侧对应位置后，判断是否是相同符号。若相同，再返

13、回c左侧循环，直至所有符号比较完毕。最后将标志符号修改回原符号。在设计时，特别注意用状态存贮符号的方法，这是图灵机设计的重要方法之一。164.1图灵机模型174.1图灵机模型【例4-3】设计一个图灵机，计算自然数n的以2为底的对数。用一进制表示输入和输出值。an表示输入n,bm表示输出m.设计思路：从左到右扫描带，把所碰到的a划掉一个，留一个，并将计数器加1。重复此过程，直至a不复存在。这里，用字符c表示划掉的字符。184.1图灵机模型194.1图灵机模型【例4-4】设计一个图灵机，计算二个自然数m、n的减法：设计时，整数n用0n表示。开始时，带上符号为0m10n，结束时，带上符号

14、为0。每当在1的左边将一个0改变为B，就在1的右边将一个0改为1，若1的右边无0时，再将左边改为B的0恢复回来。m-n若m≥nm－n=0否则204.1图灵机模型R214.1图灵机模型【例4-5】设计图灵机实现数字从一进制表示到二进制表示的转换。这个图灵机的设计可以仿例4-3，不同在于每次循环时，要保留除以2的余数作为当前二进制位的值。注意这里首先计算出的是二进制的低位值，所以要将结果不断右移以插入新生成的位，生成的结果是低位在右端。初始时，整数n用an表示，结束时，带