正規系統的不可判定性

正規系統的不可判定性

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

基本介紹

  • 中文名:正規系統的不可判定性
  • 外文名:undecidability of normal system
  • 適用範圍:數理科學
簡介,可解性,算術系統的不可判定性,

簡介

正規系統的不可判定性是一種文法系統的不可判定特性。
所謂正規系統的判定問題是指:是否存在能行的算法,使得對任意的正規系統 S 及 S 上的兩個字 W1W2,該算法可以判定
是否成立。

可解性

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

算術系統的不可判定性

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

相關詞條

熱門詞條

聯絡我們