算術階層遞歸論可計算性理論中的概念,將自然數子集按照定義它們的公式的複雜度分類。

定義

按公式定義

為自然數的語言中的公式,定義 公式當且僅當 中的所有量詞都是有界量詞(即形如 的量詞,其中 為該語言中的項)。

定義 公式當且僅當 ,其中 ;定義 公式當且僅當 ,其中

更進一步定義 公式當且僅當 ,其中 公式;定義 公式當且僅當 ,其中 公式。

;若存在 公式定義 則稱 集合,若存在 公式定義 則稱 公式。(若有公式 與集合 ,使 ,則稱 定義 。)

按可計算性定義

若集合 可以用圖靈機(或任何等價的計算模型)計算得出,則稱 集合。若 遞歸可列舉集合則稱 集合,若 的補集 遞歸可列舉則稱 集合。這一定義實際上與上面給出的定義是等價的。

更高階層的算術類可以通過波斯特定理與可計算性聯絡起來:設 為零不可解度的第 圖靈跳躍,則任何集合 集合當且僅當 可以用具備 預言機遞歸列舉;任何集合是 集合當且僅當其補集滿足以上條件。

舉例

  • 所有遞歸集合都是 集合、所有遞歸可列舉集合都是 集合(逆命題亦成立)。
  • 停機集合(即所有停機的圖靈機)是 集合,它在 類中是完全的。
  • 所有有限遞歸可列舉集合的編號(記作 )是 -完全集合(因此所有無限遞歸可列舉集合的編號是 -完全集合)。
  • 所有 -完全集合作為遞歸可列舉集合的編號是 -完全集合。

參考資料

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.