计算理论计算理论2章 计算3

VIP免费
2025-01-13 0 0 1.45MB 44 页 5.9玖币
侵权投诉
计算理论
第二章 计算
定理：
任意一台图灵机都可以等价转换为
一台通用图灵机。
图灵机自身可以编码作为图灵机的输入
不可判定与不可识别
图灵可判定
语言（递归）
图灵可识别
语言
( 递归可
枚举）
？
？
不可判定 undecidable
设计图灵机，检查 TM M 是否接受字符串
w。
ATM={<M,w>|TM M 接受输入 w}
模拟 TM M 的运行，接受则接受，拒绝则拒绝
循环？
ATM 是不可判定的？
ATM 是不可判定的
定理：ATM={ <M,w> | TM M 接受串 w } 是
不可判定的。
证明思路：
反证法，若 ATM 可判定，设 H是ATM 的判定
器。构造一 TM D ，D定义为 H的相反。 H接受则
D拒绝，反之， H拒绝则 D接受。
当 H判定 D时，用对角化法得出矛盾。
H<M1> <M2> <M3> <M4> … <D>
M1accept accept accept refuse …
M2refuse refuse refuse accept …
M3accept refuse refuse refuse ….
M4refuse refuse accept accept …
… … … … … …
D refuse accept accept refuse … ?
证明 : ( 反证 ) 设TM H 判定 ATM.
则
构造 TM D.
D: 输入 <M>, M 是TM
(1) 在输入 <M,<M>> 上运行 H.
(2) 如果 H接受 , 就拒绝 ; 若H拒绝 ,就接受。
D输入 <D> 时：
D(<D>)= 接受 D(<D>)= 拒绝 。矛盾 !
不可判定与不可识别
图灵可判定
语言（递归）
图灵可识别
语言
( 递归可
枚举）
？
？
摘要：

计算理论第二章计算定理：任意一台图灵机都可以等价转换为一台通用图灵机。图灵机自身可以编码作为图灵机的输入不可判定与不可识别图灵可判定语言（递归）图灵可识别语言(递归可枚举）？？不可判定undecidable设计图灵机，检查TMM是否接受字符串w。ATM={|TMM接受输入w}模拟TMM的运行，接受则接受，拒绝则拒绝循环？ATM是不可判定的？ATM是不可判定的定理：ATM={|TMM接受串w}是不可判定的。证明思路：反证法，若ATM可判定，设H是ATM的判定器。构造一TMD，D定义为H的相反。H接受则D拒绝，反之，H拒绝则D接受。当H判定D时，用对角化法得出矛盾。H…M1acce...

展开>> 收起<<
计算理论计算理论2章 计算3.pptx

共44页,预览9页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：计算机 价格：5.9玖币 属性：44 页 大小：1.45MB 格式：PPTX 时间：2025-01-13

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

高考理综 人际关系 配电装置 动力学连接体 力的合成 全宋诗作者索引 公务员考试
/ 44
评分 收藏
分享
立即下载 VIP免费下载
客服
关注