弗里德堡–穆奇尼克定理
弗里德堡–穆奇尼克定理(英语:Friedberg–Muchnik Theorem)是可计算性理论中关于不可解度的定理,声称存在一对互相不可计算的递归可枚举不可解度。[1]
内容
存在递归可枚举不可解度 互不可计算。
相关定理
- 波斯特定理
- 克莱尼–波斯特定理
- 波斯纳–罗宾逊定理
- 跳跃逆转定理
参考资料
- ^ Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 (英语).[页码请求]