114图灵机 ■图灵机的基本模型 ■图灵机接受的语言 递归可枚举语言 用图灵机计算函数 部分可计算函数与可计算函数
1 11.4 图灵机 ◼ 图灵机的基本模型 ◼ 图灵机接受的语言 ——递归可枚举语言 ◼ 用图灵机计算函数 ——部分可计算函数与可计算函数
问题的提出 1900年D. Hilbert在巴黎第二届数学家大会上提出 著名的23个问题 第10个问题如何判定整系数多项式是否有整数根? 要求使用“有限次运算的过程” 1970年证明不存在这样的判定算法,即这个问题是 不可判定的,或不可计算的
2 问题的提出 1900年 D. Hilbert 在巴黎第二届数学家大会上提出 著名的23个问题. 第10个问题:如何判定整系数多项式是否有整数根? 要求使用“有限次运算的过程” 1970 年证明不存在这样的判定算法, 即这个问题是 不可判定的, 或不可计算的
计算模型 从20世纪30年代先后提出 图灵机 A M.Turing,1936年 λ转换演算 A Church,1935年 递归函数KG6del,1936年 正规算法A.A. Markov,1951年 无限寄存器机器 J.C. Shepherdson,1963年
3 计算模型 从20世纪30年代先后提出 图灵机 A.M.Turing, 1936年 λ转换演算 A.Church, 1935年 递归函数 K.Gödel, 1936年 正规算法 A.A.Markov, 1951年 无限寄存器机器 J.C.Shepherdson, 1963年 …
Church- Turing论题 已经证明这些模型都是等价的,即它们计算 的函数类(识别的语言类)是相同的 Church- Turing论题:直观可计算的函数类 就是图灵机以及任何与图灵机等价的计算模 型可计算(可定义)的函数类
4 Church-Turing论题 已经证明这些模型都是等价的, 即它们计算 的函数类 (识别的语言类) 是相同的. Church-Turing论题: 直观可计算的函数类 就是图灵机以及任何与图灵机等价的计算模 型可计算 (可定义) 的函数类
图灵机的基本模型 。。。。 B 。。 B 控制器 定义图灵机(TM)M=(Q,,6,q0,B,A),其中 (1)状态集合Q:非空有穷集合; (2)输入字母表∑:非空有穷集合; (3)带字母表/:非空有穷集合且Xc厂; (4)初始状态q∈Q;
5 图灵机的基本模型 定义 图灵机(TM) M=Q,Σ,Γ,δ,q0 ,B,A , 其中 (1) 状态集合Q: 非空有穷集合; (2) 输入字母表Σ: 非空有穷集合; (3) 带字母表Γ: 非空有穷集合且ΣΓ; (4) 初始状态 q0Q; 控制器