【计算理论】不可判定性 ( 停机问题 | 图灵机语言是否空集问题 | 图灵机是否等价问题 | 是否存在自动机接受图灵机语言问题 | 莱斯定理 Rice‘s Theorem )

一、不可判定性 ( Undecidability )

不可判定 ( Undecidability ) 是正常的 , 绝大多数的 计算问题 都是不可判定的 ;

可判定的计算问题 只占 计算问题 中的 一小部分 ;

证明思路 :

不可数无穷 : 语言 与 计算问题 的个数是无穷的 , 其个数与实数一样多 , 是 不可数无穷 ;

可数无穷 : 图灵机 个数也是无穷的 , 其个数与自然数一样多 , 是 可数无穷的 ;

语言的个数 要 远远多于 图灵机个数 ;

二、“停机问题” 不可判定

停机问题 是不可判定的 ;

停机问题 : 设计一个程序 , 帮助判定 “给定一个程序 , 该程序是否会停机” ;

① 如果知道该程序 不会停机 , 就强制停止该程序 ;

② 如果知道该程序 会停机 , 就耐心等待该程序执行完毕 ;

上述 “能判定程序是否会停机” 的程序 , 是不存在的 ;

三、“图灵机语言是否空集问题” 不可判定

判定图灵机所认识的语言是否是空集 的问题 , 也是不可判定的 ;

四、“图灵机是否等价问题” 不可判定

图灵机的等价问题 , 即 判定两个图灵机是否是相互等价的 , 也是不可判定的 ;

五、“是否存在自动机接受图灵机语言问题” 不可判定

图灵机 所认识的语言 , 是否能够找到一个自动机认识 , 是不可判定的 ;

六、莱斯定理 ( Rice’s Theorem )

莱斯定理 ( Rice’s Theorem ) :

任何一个 关于图灵机的计算问题 , 都是 不可判定的 ;