算術的階層

算術的階層は、自然数の集合を、それらを定義するのに必要な交互の量化子の数によって分類し、論理的な複雑さと非計算可能性の度合いを結びつけます。

Definition

算術的階層は、計算可能な行列の前に置かれた無制限の量化子の交代を数えることによって、一階算術で定義可能な集合を層別化します。シグマn集合は存在量化子で始まるブロックによって定義され、パイn集合は全称量化子で始まるブロックによって定義されます。

Scope

このトピックでは、計算可能な関係に対する量化子の交代によるシグマ、パイ、デルタレベルへの定義可能な集合の分類、階層と反復停止問題およびチューリングジャンプを関連付けるポストの定理、階層の厳密性、および解析的階層への拡張について扱います。

Core questions

• 量化子の交代は集合の複雑さをどのように測定しますか？
• 各レベルにおけるシグマ、パイ、デルタのクラスは互いにどのように関連していますか？
• この階層は停止問題の反復とどのように対応していますか？
• なぜこの階層は厳密であり、各レベルが前のレベルよりも真に大きいのですか？

Key theories

量化子分類

集合がシグマnであるのは、計算可能な関係に対して存在量化子で始まるn個の交互の量化子ブロックによって定義可能である場合であり、パイnであるのは全称量化子で始まる場合です。計算可能に列挙可能な集合は、まさにシグマ1集合です。

ポストの定理

集合がシグマ(n+1)であるのは、それがn番目のチューリングジャンプに対して計算可能に列挙可能である場合であり、階層のレベルを反復相対化停止問題に結びつけます。

階層の厳密性

各チューリングジャンプは前のものよりも厳密に複雑であるため、算術的階層の各レベルはそれより下のレベルを真に含み、階層は崩壊しません。

Clinical relevance

算術的階層は、論理学および計算機科学における定義可能な問題の複雑さの標準的な尺度です。これは、計算可能集合の全域性、有限性、補有限性などの問題を正確なレベルに位置づけ、計算可能に列挙可能なものと、より強力な非計算可能なリソースを必要とするものとの境界を明確にします。

History

クリーネとモストフスキは、1943年頃に独立して算術的階層を導入し、計算可能な述語に対する量化子の複雑さによって集合を分類しました。ポストの定理は、この階層をチューリングジャンプと結びつけ、定義可能性に基づく視点と計算可能性に基づく視点を統合しました。この枠組みは後に解析的階層へと上方拡張されました。

Key figures

• Stephen Cole Kleene
• Andrzej Mostowski
• Emil Post

Seminal works

• rogers1987
• soare1987
• cutland1980

Frequently asked questions

階層におけるより高いレベルは何を意味しますか？

より多くの交互の量化子は、より複雑な定義を意味し、ポストの定理によれば、決定するためにより多くの停止問題の反復を必要とする問題を意味します。階層の上位にある集合は、それより下にある集合よりも計算へのアクセスが厳密に困難です。

計算可能に列挙可能な集合はどこに位置しますか？

それらはシグマ1レベルを占め、計算可能な関係に対する単一の存在量化子によって定義可能です。それらの補集合はパイ1レベルを占め、その両方であるデルタ1集合は、まさに計算可能な集合です。