文章目录
一、不可判定性 ( Undecidability )
二、"停机问题" 不可判定
三、"图灵机语言是否空集问题" 不可判定
四、"图灵机是否等价问题" 不可判定
五、"是否存在自动机接受图灵机语言问题" 不可判定
六、莱斯定理 ( Rice's Theorem )
一、不可判定性 ( Undecidability )
不可判定 ( Undecidability ) 是正常的 , 绝大多数的 计算问题 都是不可判定的 ;
可判定的计算问题 只占 计算问题 中的 一小部分 ;
证明思路 :
不可数无穷 : 语言 与 计算问题 的个数是无穷的 , 其个数与实数一样多 , 是 不可数无穷 ;
可数无穷 : 图灵机 个数也是无穷的 , 其个数与自然数一样多 , 是 可数无穷的 ;
语言的个数 要 远远多于 图灵机个数 ;
二、“停机问题” 不可判定
停机问题 是不可判定的 ;
停机问题 : 设计一个程序 , 帮助判定 “给定一个程序 , 该程序是否会停机” ;
① 如果知道该程序 不会停机 , 就强制停止该程序 ;
② 如果知道该程序 会停机 , 就耐心等待该程序执行完毕 ;
上述 “能判定程序是否会停机” 的程序 , 是不存在的 ;
三、“图灵机语言是否空集问题” 不可判定
判定图灵机所认识的语言是否是空集 的问题 , 也是不可判定的 ;
四、“图灵机是否等价问题” 不可判定
图灵机的等价问题 , 即 判定两个图灵机是否是相互等价的 , 也是不可判定的 ;
五、“是否存在自动机接受图灵机语言问题” 不可判定
图灵机 所认识的语言 , 是否能够找到一个自动机认识 , 是不可判定的 ;
六、莱斯定理 ( Rice’s Theorem )
莱斯定理 ( Rice’s Theorem ) :
任何一个 关于图灵机的计算问题 , 都是 不可判定的 ;
