正規系統的不可判定性

正規系統的不可判定性是一種文法系統的不可判定特性。正規系統的判定問題是不可解的，由於以上問題是對所有的系統而言，故稱為一般正規系統的判定問題。

基本介紹

• 中文名：正規系統的不可判定性
• 外文名：undecidability of normal system
• 適用範圍：數理科學

簡介

正規系統的不可判定性是一種文法系統的不可判定特性。

所謂正規系統的判定問題是指：是否存在能行的算法，使得對任意的正規系統 S 及 S 上的兩個字 W₁W₂，該算法可以判定是否成立。

可解性

正規系統的判定問題是不可解的，由於以上問題是對所有的系統而言，故稱為一般正規系統的判定問題。對具體的正規系統，也有其對應的特殊的判定問題，後者依賴於所給的系統。事實上，存在僅有兩個字母組成的正規系統，其對應的特殊的判定問題是不可解的。

算術系統的不可判定性

(undecidability of ari-thmetic system)

佩亞諾算術系統的不可判定特性。

1936年，美國數學家、邏輯學家丘奇(Church,A.)用哥德爾證明不完備定理的思想證明了佩亞諾算術的不可判定性。美國學者羅塞(Rosser } J. B.)同年證明了佩亞諾算術是本質不可判定的。由算術系統的本質不可判定性還可以得到諸如 ZF系統等重要理論的不可判定性。