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

定義

編輯

按公式定義

編輯

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

定義    公式若且唯若  ,其中   ;定義    公式若且唯若  ,其中   

更進一步定義    公式若且唯若  ,其中    公式;定義    公式若且唯若  ,其中    公式。

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

按可計算性定義

編輯

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

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

舉例

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

參考資料

編輯