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

定义

按公式定义

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

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

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

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

按可计算性定义

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

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

举例

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

参考资料

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.