离散数学配套课件ppt(第5版)第六部分-形式语言与自动机图灵机.ppt
《离散数学配套课件ppt(第5版)第六部分-形式语言与自动机图灵机.ppt》由会员分享,可在线阅读,更多相关《离散数学配套课件ppt(第5版)第六部分-形式语言与自动机图灵机.ppt(15页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、110.4 图灵机图灵机n图灵机的基本模型图灵机的基本模型n图灵机接受的语言图灵机接受的语言 递归可枚举语言递归可枚举语言n用图灵机计算函数用图灵机计算函数 部分可计算函数与可计算函数部分可计算函数与可计算函数 2问题的提出问题的提出1900年年 D. Hilbert 在巴黎第二届数学家大会上提出在巴黎第二届数学家大会上提出著名的著名的23个问题个问题.第第10个问题个问题:如何判定整系数多项式是否有整数根如何判定整系数多项式是否有整数根? 要求使用要求使用“有限次运算的过程有限次运算的过程”1970 年证明不存在这样的判定算法年证明不存在这样的判定算法, 即这个问题是即这个问题是不可判定的不
2、可判定的, 或不可计算的或不可计算的.3计算模型计算模型从从20世纪世纪30年代先后提出年代先后提出图灵机图灵机 A.M.Turing, 1936年年 转换演算转换演算 A.Church, 1935年年递归函数递归函数 K.Gdel, 1936年年正规算法正规算法 A.A.Markov, 1951年年无限寄存器机器无限寄存器机器 J.C.Shepherdson, 1963年年 4Church-Turing论题论题已经证明这些模型都是等价的已经证明这些模型都是等价的, 即它们计算即它们计算的函数类的函数类 (识别的语言类识别的语言类) 是相同的是相同的.Church-Turing论题论题: 直观
3、可计算的函数类直观可计算的函数类就是图灵机以及任何与图灵机等价的计算模就是图灵机以及任何与图灵机等价的计算模型可计算型可计算 (可定义可定义) 的函数类的函数类5图灵机的基本模型图灵机的基本模型定义定义 图灵机图灵机(TM) M= Q, , , ,q0,B,A , 其中其中 (1) 状态集合状态集合Q: 非空有穷集合非空有穷集合; (2) 输入字母表输入字母表 : 非空有穷集合非空有穷集合; (3) 带字母表带字母表 : 非空有穷集合且非空有穷集合且 ; (4) 初始状态初始状态 q0 Q;控制器控制器6图灵机的基本模型图灵机的基本模型(续续) (5) 空白符空白符B - ; (6) 接受状态
4、集接受状态集A Q; (7) 动作函数动作函数 是是Q 到到 L,R Q的部分函数的部分函数, 即即dom Q . (q,s)=(s ,R,q )的含义的含义: 当处于状态当处于状态q, 读写头扫视读写头扫视符号符号s时时, M的下一步把状态转移到的下一步把状态转移到q , 读写头把这读写头把这个个s改写成改写成s , 并向右移一格并向右移一格; (q,s)=(s ,L,q )的含义类似的含义类似, 只是读写头向左移一只是读写头向左移一格格; 若若 (q,s)没有定义没有定义, 则则M停机停机.7一个一个TM M的的实例实例 0 1 B q0 q1 q2*q3 (0,R,q0) (1,R,q0
5、) (B,L,q1) (B,L,q2) (1,R,q0) (B,R,q0) (B,L,q3) 例例18格局格局: 带的内容带的内容, 当前的状态和读写头扫视的方格当前的状态和读写头扫视的方格 = q , 其中其中 , *, q Q初始格局初始格局 0= q0w, 其中其中w *是输入字符串是输入字符串接受格局接受格局 = q : q A停机格局停机格局 = qs : (q,s)没有定义没有定义 1 2: 从从 1经过一步能够到达经过一步能够到达 2, 称称 2是是 1的的后继后继 1 2: 从从 1经过若干步能够到达经过若干步能够到达 2图灵机的计算图灵机的计算9图灵机的计算图灵机的计算(续续
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 配套 课件 ppt 第六 部分 形式语言 自动机 图灵机
限制150内