跳至內容

低基定理

維基百科,自由的百科全書

低基定理是關於不可解度的定理。

定理

[編輯]

為無窮長二進制串的集合,若自然數的語言中存在遞歸公式 ,使 若且唯若 (註: 是二進制串 的前 位)為真,則定義 類。

若將無窮長二進制串的第 位理解成「 是否屬於該集合」,則 自然對應了自然數集合的子集集合 。因此 上可以引入不可解度的關係

低基定理表明,若 是一個 類,則存在 使得 (換句話說, 是一個低不可解度)。稱 的低基。

參考資料

[編輯]
  • Cenzer, Douglas. classes in computability theory. Griffor, Edward R. (編). Handbook of computability theory. Stud. Logic Found. Math. 140. North-Holland. 1999: 37–85. ISBN 0-444-89882-4. MR 1720779. Zbl 0939.03047 (英語). 
  • Jockusch, Carl G., jr; Soare, Robert I. Π(0, 1) Classes and Degrees of Theories. Transactions of the American Mathematical Society. 1972, 173: 33–56. ISSN 0002-9947. JSTOR 1996261. Zbl 0262.02041 (英語). 
  • Nies, André. Computability and randomness. Oxford Logic Guides 51. Oxford: Oxford University Press. 2009. ISBN 978-0-19-923076-1. Zbl 1169.03034 (英語). 
  • Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 (英語).