弗里德堡–穆奇尼克定理

弗里德堡–穆奇尼克定理（英語：Friedberg–Muchnik Theorem）是可計算性理論中關於不可解度的定理，声称存在一对互相不可计算的递归可枚举不可解度。^[1]

内容

存在递归可枚举不可解度 ${\displaystyle A,B}$  互不可计算。

相关定理

• 波斯特定理
• 克莱尼–波斯特定理
• 波斯纳–罗宾逊定理
• 跳躍逆轉定理

参考资料

1. Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 （英语）. ^{[页码请求]}