克莱尼–波斯特定理

克莱尼–波斯特定理英語:)是可計算性理論中關於不可解度的定理,声称存在且可从停机问题计算出一对互相不可计算的不可解度。[1]

内容

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

相关定理

参考资料

  1. 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.