计算机科学

首页 > 计算机科学

低基定理

2018-08-28 09:58:23     所属分类:递归论

低基定理是关于不可解度的定理。

定理

为无穷长二进制串的集合,若自然数的语言中存在递归公式 ,使 当且仅当 (注: 是二进制串 的前 位)为真,则定义 类。

若将无穷长二进制串的第 位理解成“ 是否属于该集合”,则 自然对应了自然数集合的子集集合 。因此 上可以引入不可解度的关系

低基定理表明,若 是一个 类,则存在 使得 (换句话说, 是一个低不可解度)。称 的低基。

参考资料

  • Cenzer, Douglas. classes in computability theory. (编) Griffor, Edward R. Handbook of computability theory. Stud. Logic Found. Math. 140. North-Holland. 1999: 37–85. ISBN 0-444-89882-4. MR 1720779. Zbl 0939.03047 (英语).  参数|chapter=值左起第1位存在删除符 (帮助)
  • Jockusch, Carl G., jr; Soare, Robert I. Π(0, 1) Classes and Degrees of Theories. Transactions of the American Mathematical Society. 1972, 173: 33–56. ISSN 0002-9947. JSTOR 1996261. Zbl 0262.02041 (英语). 
  • Nies, André. Computability and randomness. Oxford Logic Guides 51. Oxford: Oxford University Press. 2009. ISBN 978-0-19-923076-1. Zbl 1169.03034 (英语). 
  • Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 (英语). 

上一篇:决定性问题
下一篇:停机问题
相关推荐