跳转到内容

克莱尼–波斯特定理

维基百科,自由的百科全书

克莱尼–波斯特定理(英语:Kleene–Post Theorem)是可计算性理论中关于不可解度的定理,声称存在且可从停机问题计算出一对互相不可计算的不可解度。[1]

内容

[编辑]

存在不可解度 ,使 互不可计算。

相关定理

[编辑]

参考资料

[编辑]
  1. ^ Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 (英语). [页码请求]