低基定理

来自testwiki
跳转到导航 跳转到搜索

Template:Multiple issues 低基定理是关于不可解度的定理。

定理

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

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

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

参考资料