弗里德堡–穆奇尼克定理

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

内容

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

相关定理

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

参考资料

Robert I. Soare. . Springer. 2004. ISBN 9780387152998 （英语）.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.