离散数学与(第5版)耿素云10.4 .ppt

* 10.4 图灵机 图灵机的基本模型 图灵机接受的语言 ——递归可枚举语言 用图灵机计算函数 ——部分可计算函数与可计算函数 * 问题的提出 1900年 D. Hilbert 在巴黎第二届数学家大会上提出 著名的23个问题. 第10个问题:如何判定整系数多项式是否有整数根? 要求使用“有限次运算的过程” 1970 年证明不存在这样的判定算法, 即这个问题是 不可判定的, 或不可计算的. * 计算模型 从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论题: 直观可计算的函数类 就是图灵机以及任何与图灵机等价的计算模 型可计算 (可定义) 的函数类 * 图灵机的基本模型 定义 图灵机(TM) M=?Q,?,?,?,q0,B,A ?, 其中 (1) 状态集合Q: 非空有穷集合; (2) 输入字母表?: 非空有穷集合; (3) 带字母表?: 非空有穷集合且? ??; (4) 初始状态 q0?Q; 控制器 * 图灵机的基本模型(续) (5) 空白符B?? -?; (6) 接受状态集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停机. * 一个TM M的实例 ? 0 1 B →q0 q1 q2 *q3 (0,R,q0) (1,R,q0) (B,L,q1) (B,L,q2) (1,R,q0) (B,R,q0) (B,L,q3) — — — — — 例1 * 格局: 带的内容, 当前的状态和读写头扫视的方格 ? = ?q?, 其中 ?,??Γ*, q?Q 初始格局? 0= q0w, 其中w?Σ*是输入字符串 接受格局? = ?q? : q?A 停机格局? = ?qs? : δ(q,s)没有定义 ?1 ? ?2: 从?1经过一步能够到达?2, 称?2是?1的后继 ?1 ?2: 从?1经过若干步能够到达 ?2 图灵机的计算 * 图灵机的计算(续) 计算: 一个有穷的或无穷的格局序列, 序列中的每一个格局都是前一个格局的后继. ?w??*, M从?0= q0w开始的计算有3种可能: (1) 停机在接受格局, 即计算为?0, ?1, … , ?n, 其中?n是接受的停机格局; (2) 停机在非接受格局, 即计算为?0, ?1, … , ?n, 其中?n是非接受的停机格局; (3) 永不停机, 即计算为?0, ?1, … , ?n, … * 图灵机接受的语言 定义 ?w??*, 如果M从?0= q0w开始的计算停机在 接受格局, 则称M接受输入串w. M接受的语言L(M) 是M接受的所有输入串, 即L(M)={w??* | M接受w}. 例1 (续) M关于输入w=10100的计算: q010100B ? 1q00100B ? 10q0100B ? 101q000B ? 1010q00B ? 10100q0B ? 1010q10B ? 101q20BB ? 101Bq3BB 由于停机在接受格局, 故M接受10100. L(M)={w00 | w?{0,1}*} * 图灵机接受的语言(续) 定义 能被图灵机接受的语言称作递归可枚举的, 记作r.e. 定理 语言L是r.e.当且仅当 L是 0 型语言. 图灵机与 0 型文法是等价的 * 用图灵机计算函数 ?上的m元部分字函数: (?*)m的某个子集到?*的部分函数 TM M计算的m元部分字函数f : 设输入字母表为?, ?x1,…,xm??*, 如果M从初始格