跳至內容

弗里德堡–穆奇尼克定理

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

弗里德堡–穆奇尼克定理(英語:Friedberg–Muchnik Theorem)是可計算性理論中關於不可解度的定理,聲稱存在一對互相不可計算的遞歸可枚舉不可解度。[1]

內容

存在遞歸可枚舉不可解度 互不可計算。

相關定理

參考資料

  1. ^ Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 (英語). [頁碼請求]