计算机科学

首页 > 计算机科学

弗里德堡–穆奇尼克定理

2018-08-30 09:59:48     所属分类:计算理论

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

上一篇:自指
相关推荐