图灵论题算法-edX.PPT

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 《理论计算机科学基础》第9讲 * 引理7.1 引理7.1: 存在可计算函数 q : ?*??*, 对任意串w, q(w)是图灵机Pw的描述, TM Pw打印出w, 然后停机. 说明: ?w, q(w)=Pw ?x, Pw(x)=w 对任何w, Pw都存在 从w得到Pw的过程, 是可计算的 《理论计算机科学基础》第9讲 * 引理7.1证明 证明: TM Q=“对输入串w: 1) 构造下列TM Pw: Pw=“对任何输入: a) 抹去输入; b) 写下w; c) 停机.” 2) 输出Pw. ” # 《理论计算机科学基础》第9讲 * 自我复制机 自己打印自己的TM TM SELF ?x, SELF(x)=SELF main(){printf(“main(){printf(“main(){… ”);} SELF=AB ?x, A(x)=B,B(x)=A A x B A B B A AB B 《理论计算机科学基础》第9讲 * TM SELF TM SELF打印SELF 构造: SELF=AB. A=PB, A=PB=q(B) B=“对输入M, M是TM的部分描述: 1) 计算q(M); 2) 用q(M)和M合成完整的 TM描述; 3) 打印这个描述, 然后停机. ” 《理论计算机科学基础》第9讲 * 递归定理 定理7.2(递归定理): 设TM T计算 函数 t: ?*??*??*, 则存在TM R 计算函数 r: ?*??*, 使得 ?w, r(w)=t(R,w). 说明: 若t(x,y)是2元函数, 则固定 输入x=c后, 变成1元函数t(c,y) 若 t(x,y) 可计算, 则对任意 c, t(c,y) 也可计算 递归定理说: 存在 c, 使得 c 就是 计算 t(c,y) 的程序! 《理论计算机科学基础》第9讲 * 递归定理的证明 ?t:?*??*??*, ?r:?*??*, r(w)=t(R,w) R=ABT A y B T A BT,y B T A ABT,y B T A t(ABT,y) B T T x,y T t(x,y) R y R t(R,y) 《理论计算机科学基础》第9讲 * 定理7.2递归定理的证明 证明: R=ABT, A=PBT, A=q(BT). B=“对输入w, 输出q(w)”. TM R=“对输入w: 1) 运行A, 在带上写下BT; 2) 运行B, 在带上写下A, 拼装出ABT; 3) 对ABT,w运行T. ” # 注: q见引理7.1. 递归定理的应用(通用机) 《理论计算机科学基础》 * 《理论计算机科学基础》第9讲 * 递归定理的用途 TM自引用定义 可以在M的定义中使用M, 即 TM M=“……M……” 是合法定义! 先定义TM T=“对输入x, y: ……x……” 根据递归定理, 存在这样的R TM R=“对输入y: ……R……” 代替对角化 证明ATM不可判定, MINTM不可识别 不动点定理 ?可计算函数t, ?TM F, L( t(F) )=L( F ) 《理论计算机科学基础》第9讲 * 应用递归定理的术语 可以在M的定义中使用M TM M=“…得到自己的一个描述M, …M…” 或: TM M=“……M……” 例: TM SELF=“对任意输入, 1) 利用递归定理得到自己的描述SELF; 2) 打印SELF. ” 或: TM SELF=“对任意输入,打印SELF” 《理论计算机科学基础》第7讲 * 图灵机接受性问题 TM接受性问题 检查一个图灵机是否接受 一个给定的串 语言 ATM = { M,w | TM M接受串w } 《理论计算机科学基础》第7讲 * 引理 引理: ATM是图灵可识别的 证明思路: 设计TM U模拟M在w上的计算 当M在w上停机接受时,U接受 当M在w上停机拒绝时,U拒绝 当M在w上不停机时,U也不