丘奇-图灵论题-edX.ppt

第5周、第6周内容介绍
《理论计算机科学基础》
1
《理论计算机科学基础》
2
第2部分可计算性理论
第5周图灵机
第4章丘奇-图灵论题
第7章可计算性理论的
高级专题(递归定理)
第6周(不)可计算问题
第5章可判定性
第6章可归约性
《理论计算机科学基础》
3
第4章丘奇-图灵论题
图灵机(TM)
多带图灵机
非确定型图灵机(NTM)
枚举器
图灵可识别, 图灵可判定
丘奇-图灵论题
算法、希尔伯特第10问题
图灵机的描述
形式描述; 实现描述; 高层描述
编码: <O>
《理论计算机科学基础》第9讲
4
第7章可计算性高级专题
递归定理
自引用
应用递归定理的术语
可以在M的定义中使用<M>
应用
图灵机接受性问题
图灵机极小性问题
通用机
《理论计算机科学基础》第7讲
5
第5章可判定性
可判定语言
关于正则语言的可判定问题
关于上下文无关语言的
可判定问题
停机问题
对角化方法
停机问题是不可判定的
非图灵可识别语言
《理论计算机科学基础》第8讲
6
第6章可归约性
语言理论中的不可判定问题
利用计算历史的归约
线性界限自动机
波斯特对应问题
映射归约(多一归约,m归约)
单带图灵机的例子
《理论计算机科学基础》
7
《理论计算机科学基础》
8
单带图灵机的示意图
双向读写头
无穷带
停机状态
状态控制器
输入
a
a
b
b
c
双向读写头
TM
《理论计算机科学基础》
9
识别w#w的单带图灵机M1
B = { w#w | w{0,1}* }
M1=“对于输入字符串x:
1) 扫描输入,确认只含一个#.
否则拒绝.
2) 在#两边对应位置来回移动,
检查是否含相同符号.
若不是,则拒绝.
消去已检查过符号.
3) 当消去#左边所有符号时,
检查#右边是否还有符号,
若是,则拒绝. 否则接受. ”
《理论计算机科学基础》
10
M1对011000#011000计算
0 1 1 0 0 0 # 0 1 1 0 0 0
