Part4图灵机及可计算理论.ppt
《Part4图灵机及可计算理论.ppt》由会员分享,可在线阅读,更多相关《Part4图灵机及可计算理论.ppt(82页珍藏版)》请在三一文库上搜索。
1、Part 4 图灵机及可计算理论,主讲教师 贺利坚,2,Part 4 主要内容提示,3,一、图灵机及形式定义,1、图灵机 2、图灵机的形式定义 3、图灵机接受的语言,4,图灵机,FA和PDA的局限 FA有有限的存储,只能处理RL PDA用栈提供无限的存储,但栈只能后进先出,PDA只能处理CFL FA和PDA不能用作通用的计算模型,5,图灵机是通用的计算模型,是计算机的数学模型 图灵在论述“有些数学问题是不可解的”时,提出了图灵机 图灵论题:凡是可计算的函数,都可以用图灵机计算 丘奇论题:任何计算,如果存在一个有效过程,它就能被图灵机实现 提出TM的目的在于: 对有效的计算过程(即算法)进行形式
2、化的描述, 忽略模型的存储容量在内的一些枝节问题, 只考虑算法的基本特征. 图灵提出TM具有以下两个性质 具有有穷描述。 过程必须是由离散的、可以机械执行的步骤组成。,图灵机,6,图灵生平 1912年出生,演算能力突出 1931年,进剑桥大学学数学 1936年,提出图灵机模型 1938年,获普灵斯顿大学博士学位 1950年,发表论文“计算机和智能”,提出图灵测试 1951年,成为英皇家学会院士 1954年,不幸去世,现代计算机设计思想的创始人,人工智能领域的开拓者 计算机领域的最高奖以图灵命名,图灵机,7,Alan Turing(1912-1954),1912 (23 June): Birth
3、, Paddington, London 1926-31: Sherborne School 1930: Death of friend Christopher Morcom 1931-34: Undergraduate at Kings College, Cambridge University 1932-35: Quantum mechanics, probability, logic 1935: Elected fellow of Kings College, Cambridge 1936: The Turing machine, computability, universal mac
4、hine 1936-38: Princeton University. Ph.D. Logic, algebra, number theory 1938-39: Return to Cambridge. Introduced to German Enigma cipher machine 1939-40: The Bombe, machine for Enigma decryption 1939-42: Breaking of U-boat Enigma, saving battle of the Atlantic 1943-45: Chief Anglo-American crypto co
5、nsultant. Electronic work. 1945: National Physical Laboratory, London 1946: Computer and software design leading the world. 1947-48: Programming, neural nets, and artificial intelligence 1948: Manchester University 1949: First serious mathematical use of a computer 1950: The Turing Test for machine
6、intelligence 1951: Elected FRS. Non-linear theory of biological growth 1952: Arrested as a homosexual, loss of security clearance 1953-54: Unfinished work in biology and physics 1954 (7 June): Death (suicide) by cyanide poisoning, Wilmslow, Cheshire.,8,图灵机的物理模型 基本模型包括 一个有穷控制器。 一条含有无穷多个带方格的输入带。 一个读头。
7、 一个移动将完成以下三个动作: 改变有穷控制器的状态; 在当前所读符号所在的带方格中印刷一个符号; 将读头向右或者向左移一格。,图灵机,9,图灵机的形式定义,定义9-1 图灵机(Turing machine)/基本的图灵机 TM M=(Q, , , , q0, B, F) Q:状态的有穷集合,qQ为M的一个状态; :输入字母表,a为M的一个输入符号。除空白符号B外,只有中的符号才能在M启动时出现在输入带上; :带符号表(tape symbol),X为M的一个带符号,表示在M的运行过程中,X可以在某一时刻出现在输入带上; q0Q:M的开始状态,M从状态q0启动,读头正注视着输入带最左端的符号;
8、B:空白符(blank symbol),含空白符的带方格是空的; FQ:M的终止状态集,qF为M的一个终止状态。 TM M 一旦进入终止状态,它就停止运行。,10,TM M=(Q, , , , q0, B, F) 称为移动函数 :Q Q R, L,为M的移动函数(transaction function)。 (q, X)=(p, Y, R)表示M在状态q读入符号X,将状态改为p,并在这个X所在的带方格中印刷符号Y,然后将读头向右移一格; (q, X)=(p, Y, L)表示M在状态q读入符号X,将状态改为p,并在这个X所在的带方格中印刷符号Y,然后将读头向左移一格。,图灵机的形式定义,11,例
9、 TM 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),M1的移动函数的另一种表示:,图灵机的形式定义,q2,(q2, B, R),(q1, 0, R),q1,(q1, 1, R),(q0, 0, R),q0,B,1,0,状态,L(M1)=x | x0,1+,且x中有且仅有一个1,12,补充:图灵机的转移图 M1=(q0, q1, q2,0, 1,0, 1, B, ,q0 , B
10、,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/Y D,D为或 L(M1)=x | x0,1+,且x中有且仅有一个1,图灵机的形式定义,13,图灵机接受的语言,定义9-2 即时描述(instantaneous description, ID) 12 *,qQ, 1q2称为M的即时描述 q为M的当前状态, M正注视着2的最左符号。 当M的读头注视的符号右边还有非空白符时, 12为M的输入带最左端到最右的非空白符
11、号组成的符号串; 否则, 12是M的输入带最左端到M的读头注视的带方格中的符号组成的符号串,14,设X1X2Xi-1qXiXi+1Xn是M的一个ID, 如果(q,Xi)=(p,Y,R),则M的下一个ID为 X1X2Xi-1YpXi+1Xn 记作X1X2Xi-1qXiXi+1XnM X1X2Xi-1YpXi+1Xn,设X1X2Xi-1qXiXi+1Xn是M的一个ID, 如果(q, Xi)=(p, Y, L), 则当i1时,M的下一个ID为 X1X2pXi-1YXi+1Xn 记作X1X2Xi-1qXiXi+1Xn M X1X2pXi-1YXi+1Xn,图灵机接受的语言,15,Mn表示M的n次幂:M
12、n =(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),图灵机接受的语言,M 000100Bq2,M 000100 q1,M 00000q0B,M 00010q11,M 00010q10,M 0000 q00,M 0001q101,M 0001q100,M 000q000,M 000q0101,M 000q0100,M 00q0000,M 00q00101,M
13、1Bq2,M 00q00100,M 0q00000,M 0q000101,M 1q1,M 0q000100,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-3 TM接受的语言 TM M=(Q, , , , q0, B, F) L(M)=x | x*且q0xM* 1q 2 & qF & 1, 2 *,只要在工作过程中能进入终止状态(之一),则可以判断被接
14、受并停机。,图灵机不停地计算: 当输入被接受时, 图灵机将停止, 没有下一个动作; 当因未定义转换函数, 图灵机无法计算下去时, 将拒绝执行; 如果不进入任何接受或拒绝状态, 继续执行下去, 永不停止。 在TM接受的语言中,包含那些不能使TM停机的输入。,图灵机接受的语言,18,定义9-4 TM接受的语言叫做递归可枚举语言(recursively enumerable language,r.e.)。 如果存在TM M=(Q, , , , q0, B, F) ,L=L(M),并且对每一个输入串x,M都停机,则称L为递归语言(recursively language)。 x是任意的串 xL,M进入
15、接受状态并停机 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上那些至少含有
16、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 10 q101100101100 100q11100101100 1001 q2100101100 10011q300101100,(1)00010101: q000010101 0q00010101 00q0010101
17、000q010101 0001q10101 00010q1101 000101q201 0001010q21 00010101q3,(2)000101000: q0000101000 0q000101000 00q00101000 000q0101000 0001q101000 00010q11000 000101q2000 0001010q200 00010100q20 000101000q2B,21,一、图灵机及形式定义,1、图灵机 2、图灵机的形式定义 3、图灵机接受的语言,Any Question?,22,Part 4 主要内容提示,23,二、图灵机的构造,1、一般构造方法 2、TM作
18、为非负整函数的计算模型 3、 状态的有穷存储功能的利用 4、多道(multi-track)技术 5、子程序(subroutine)技术,24,一般构造方法,思路 图灵机可以对输入带进行写操作 写入一些标记即完成记忆(类似PDA的栈,但更丰富) 图灵机还可以用状态标记工作状态,25,例 构造TM M3,使L(M)=0n1n2n | n1。 不能通过“数” 0、1、或者2的个数来实现检查。 用匹配的方法比较它们的个数是否相同: 出现一个0、必然所有0后有1,所有1后有2。 遇0后在带方格上印刷一个X,找到1后在带方格上印刷一个Y,再找到2后在带方格上印刷一个Z。 带上为XXXYYYZZZB时接受
19、例:对000111222,一般构造方法,000111222B X00111222B X00Y11222B X00Y11Z22B, XX0Y11Z22B XX0YY1Z22B XX0YY1ZZ2B, XXXYY1ZZ2B XXXYYYZZ2B XXXYYYZZZB,26,正常情况下,输入带上的符号串的一般形式为 000011112222 TM经过一段运行, 输入带上的符号串的一般情况为 XX00YY11ZZ22BB 如果能被接受 XXXXYYYYZZB 边界情况可能有 XXXXYYYYZZ22BB XXXXYY11ZZ22BB XX00YYYYZZ22BB XX00YY11ZZZZBB XX00
20、YYYYZZZZBB,一般构造方法,27,(q0, 0)= (q1, X, R),(q1, 0)= (q1, 0, R),(q1, Y)= (q1, Y, R),(q1, 1)= (q2, Y, R),(q2, 1)= (q2, 1, R),(q2, Z)= (q2, Z, R),(q2, 2)= (q3, Z, L),(q3, 0)= (q3, 0, L) (q3, Y)= (q3, Y, L) (q3, 1)= (q3, 1, L) (q3, Z)= (q3, Z, L) (q3, X)= (q0, X, R),构造思路,28,构造思路,(q0, Y)= (q4, Y, R) 0已经读完,
21、(q4,Y)= (q4,Y,R),(q4,Z)= (q4,Z,R),(q4, B)= (q5, B, R),?q2时遇到B ?q2时遇到,终态,?q4时遇到1 ?q4时遇到2,?q1时遇到Z ?q1时遇到2 ?q1时遇到,29,L(M3)=0n1n2n | n1 M3= (q0,q1,q2,q3,q4,q5, 0, 1,2, 0,1,2,X,Y,Z,B, , q0, B, q5) 如右定义,(q0, 0)= (q1, X, R) (q1, 0)= (q1, 0, R) (q1, Y)= (q1, Y, R) (q1, 1)= (q2, Y, R) (q2, 1)= (q2, 1, R) (q2
22、, Z)= (q2, Z, R) (q2, 2)= (q3, Z, L) (q3, Z)= (q3, Z, L) (q3, 1)= (q3, 1, L) (q3, Y)= (q3, Y, L) (q3, 0)= (q3, 0, L) (q3, X)= (q0, X, R) (q0, Y)= (q4, Y, R) (q4,Y)= (q4,Y,R) (q4,Z)= (q4,Z,R) (q4, B)= (q5, B, R),一般构造方法,30,一般构造方法,L(M3)=0n1n2n | n1 M3= (q0,q1,q2,q3,q4,q5, 0, 1,2, 0,1,2,X,Y,Z,B, , q0, B
23、, q5),31,TM作为非负整函数的计算模型,TM除作为语言的识别器外,还可以求函数的值 用TM求解k元函数f(n1, n2, nk) 编码问题(带方格上的符号) 用符号串0n表示非负整数n 1进制 函数的输入(TM中带的初始值):k元函数f(n1, n2, nk)的输入是: 0n11 0n2110nk 函数的值(TM的输出):如果f(n1, n2, nk)=m,则该TM的输出为0m 。,32,定义9-5 图灵可计算的(Turing computable) 设有k元函数f(n1, n2, nk)=m, TM M=(Q, , , , q0 , B , F) M接受输入串0n11 0n2110n
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Part4 图灵机 可计算 理论
链接地址:https://www.31doc.com/p-2202422.html