弗里德堡–穆奇尼克定理

弗里德堡–穆奇尼克定理(英語: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 (英语). [页码请求]