低基定理

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

 定理 
设  为无穷长二进制串的集合，若自然数的语言中存在递归公式 ，使  当且仅当 （注： 是二进制串  的前  位）为真，则定义  为  类。

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

低基定理表明，若  是一个  类，则存在  使得 （换句话说， 是一个低不可解度）。称  为  的低基。

 参考资料 





Category:数学定理
Category:递归论