算数阶层

算术阶层递归论可计算性理论中的概念,将自然数子集按照定义它们的公式的复杂度分类。

定义

按公式定义

  为自然数的语言中的公式,定义    公式当且仅当   中的所有量词都是有界量词(即形如    的量词,其中   为该语言中的项)。

定义    公式当且仅当  ,其中   ;定义    公式当且仅当  ,其中   

更进一步定义    公式当且仅当  ,其中    公式;定义    公式当且仅当  ,其中    公式。

 ;若存在   公式定义   则称    集合,若存在   公式定义   则称    公式。(若有公式   与集合  ,使  ,则称   定义  。)

按可计算性定义

若集合   可以用图灵机(或任何等价的计算模型)计算得出,则称    集合。若  递归可枚举集合则称    集合,若   的补集   递归可枚举则称    集合。这一定义实际上与上面给出的定义是等价的。

更高阶层的算术类可以通过波斯特定理与可计算性联系起来:设   为零不可解度的第  图灵跳跃,则任何集合    集合当且仅当   可以用具备  预言机递归枚举;任何集合是   集合当且仅当其补集满足以上条件。

举例

  • 所有递归集合都是   集合、所有递归可枚举集合都是   集合(逆命题亦成立)。
  • 停机集合(即所有停机的图灵机)是   集合,它在   类中是完全的。
  • 所有有限递归可枚举集合的编号(记作  )是  -完全集合(因此所有无限递归可枚举集合的编号是  -完全集合)。
  • 所有  -完全集合作为递归可枚举集合的编号是  -完全集合。

参考资料