1 10.4 图灵机 n 图灵机的基本模型 n 图灵机接受的语言 递归可枚举语言 n 用图灵机计算函数 部分可计算函数与可计算函数 2 问题的提出 1900年 D. Hilbert 在巴黎第二届数学家大会上提出 著名的23个问题. 第10个问题: 如何判定整系数多项式是否有整数根? 要求使用“有限次运算的过程” 1970 年证明不存在这样的判定算法, 即这个问题是 不可判定的, 或不可计算的.3 计算模型 从20世纪30年代先后提出 图灵机 A.M.Turing, 1936 年 转换演算 A.Church, 1935 年 递归函数 K.Gdel, 1936 年 正规算法 A.A.Markov, 1951 年 无限寄存器机器 J.C.Shepherdson, 1963 年 4 Church-Turing 论题 已经证明这些模型都是等价的, 即它们计算 的函数类 ( 识别的语言类) 是相同的. Church-Turing 论题: 直观可计算的函数类 就是图灵机以及任何与图灵机等价的计算模 型可计算 ( 可定义) 的函数类5 图灵机的基本模型 定义 图灵机(TM) M= Q,q 0 ,B,A
