【计算理论】可判定性 ( 通用图灵机和停机问题 | 可判定性 与 可计算性 | 语言 与 算法模型 )

一、通用图灵机和停机问题

利用 图灵 的结论 , 证明 有哪些 计算问题 是找不到 算法 进行判定的 ; 如 停机问题 , 就找不到算法进行判定 ;

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

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

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

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

二、可判定性 与 可计算性

可判定性 与 可计算性

① 可判定性 ( Decidability ) : 计算模型是 图灵机中的 判定机 ;

② 可计算性 ( Turing-recognizable 图灵机可接受的 ) : 计算模型是 图灵机 ;

可计算性 包含 可判定性 ;

可计算性 与 可判定性 之间的相互关系 :

补集可计算 : 如果一个语言的 补集 ( Complement ) 是可计算的 ( Turing-recognizable ) , 那么称该语言是 补集可计算的 ( co-Turing-recognizable ) ;

判定 = 可计算 + 补集可计算 : 如果一个语言是 可判定的 ( Decidable ) , 那么这个语言是 可计算的 ( Turing-recognizable ) , 同时这个语言又是 补集是可计算的 ( co-Turing-recognizable ) ;

可计算 : Turing-recognizable

补集可计算 : co-Turing-recognizable

之前提到过 通用图灵机语言 A T M \rm A_{TM} ATM​ 是 可计算的 , 对应的计算模型是 图灵机 , 但 A T M \rm A_{TM} ATM​ 是 不可判定的 ;

可判定 = 可计算 + 补集可计算

通用图灵机语言 A T M \rm A_{TM} ATM​ 是 不可判定的 , 可计算的 , 其补集肯定是不可计算的 ;

三、语言 与 算法模型

语言 与 算法模型 :

① 正则语言 ( 自动机 ) : L r = L ( a ∗ b ∗ ) \rm L_r = L(a^*b^*) Lr​=L(a∗b∗) , 该语言是正则表达式语言 ; r \rm r r 下标含义是 regular 正则 ;

正则语言参考 : 【计算理论】正则语言 ( 正则表达式原子定义 | 正则表达式递归定义 | 正则表达式语言原子定义 | 正则表达式语言结构归纳 | 正则表达式语言示例 | 根据正则表达式构造自动机 )

② 上下文无关语言 ( 下推自动机 ) : L C F L = { a n b n : n ≥ 0 } \rm L_{CFL} = \{ a^nb^n : n \geq 0 \} LCFL​={anbn:n≥0} , 该语言不是正则表达式语言 , 是上下文无关语言 ; 下标 C F L \rm CFL CFL 含义是 Context-Free Grammer , 上下文无关语法 ;

上下文无关语法参考 : 【计算理论】上下文无关语法 ( 语法组成 | 规则 | 语法 | 语法示例 | 约定的简写形式 | 语法分析树 )

③ 可判定语言 ( 判定机 ) : L d = { a n b n c n : n ≥ 0 } \rm L_{d} = \{ a^nb^nc^n : n \geq 0 \} Ld​={anbncn:n≥0} , 该语言不是上下文无关语言 , 是可判定语言 ; 下标 d \rm d d 含义是 Decidability 可判定 ;

可判定语言参考 : 【计算理论】可判定性 ( 丘奇-图灵论题 | 可判定性引入 | 图灵机语言 | 图灵机结果 | 判定机 | 部分函数与全部函数 | 可判定性定义 )

④ 可计算语言 ( 图灵机 ) : L T r = A T M \rm L_{Tr} = A_{TM} LTr​=ATM​ , 该语言是可计算的 , 不是图灵可判定的 ; 下标 T r \rm Tr Tr 含义是 Turing-recognizable ( 图灵机可识别 ) 即可计算的 ;

⑤ 不可计算语言 ( 没有对应算法模型 ) : L n T r = A ‾ T M \rm L_{nTr} = \overline{A}_{TM} LnTr​=ATM​ , 图灵机不识别语言 , 不可计算语言 ;