ポストの定理

ポストの定理（英: Post's theorem）は、計算可能性理論における定理で、算術的階層とチューリング次数の関係を表している。名称はエミール・ポストに因んでいる。
背景.
ポストの定理は定義可能性と再帰理論に関連したいくつかの概念を必要とする。この節ではそれら概念の概要を解説する。
算術的階層は、ペアノ算術で定義可能な自然数の集合を階層的に分類するものである。ある論理式が formula_1 に属するとは、それが冠頭標準形（全ての量化子が先頭にある）の存在量化式で、存在量化と全称量化が formula_2 回交互にあって、それらが量化されていない論理式に適用されている場合である。次のような形式のペアノ算術の言語で書かれた論理式 formula_3 は formula_1 論理式である。
ここで ρ は量化子を含まない論理式で、"Q" は "m" が偶数なら formula_6、"m" が奇数なら formula_7 である。次のように formula_8 が限定量化子のみを含む論理式
は、ペアノ算術の公理により、上記形式と等価である。そのため、formula_1 論理式をこの代替形式で定義することも珍しくない。
自然数の集合 "A" が formula_11 であるとは、それを formula_11 論理式で定義できることを意味し、すなわち、formula_11 論理式 formula_3 を使って、自然数 "n" について formula_15 が成り立つときのみ、その自然数が "A" に含まれる。ある集合が formula_11 であるとき、formula_17 である任意の "n" についての formula_18 でもある。ただし、個々の "m" について formula_11 ではない formula_20 集合が存在する。従って、量化子の交代回数は、集合の複雑さの尺度を定義するのに必要である。
ポストの定理では、上で定義したような絶対的な算術的階層だけでなく、相対化された算術的階層も使う。自然数の集合 "A" が "B" に対して相対的に formula_11 であることを formula_22 と表記する。これは、"B" のメンバーシップを表す述語を含めた拡張言語で記述された formula_11 論理式で "A" を定義可能であることを意味する。
算術的階層が自然数の集合の定義可能性の尺度となる一方、チューリング次数は自然数の集合の計算不可能性のレベルの尺度となる。集合 "A" が集合 "B" にチューリング還元可能であることを formula_24 と記述し、"B" についての神託を与える神託機械によって "A" の特性関数を計算できることを意味する。集合 "A" のチューリングジャンプは、"A" に関連する停止性問題の形式である。集合 "A" のチューリングジャンプ formula_25 は、"A" についての神託機械を持ち "0" が入力されたときに停止するチューリング機械のインデックスの集合である。あらゆる集合 "A" はそのチューリングジャンプにチューリング還元可能であるが、ある集合のチューリングジャンプは決して元の集合にチューリング還元できない。
ポストの定理は有限回反復されたチューリングジャンプを使用する。任意の自然数の集合 "A" について、formula_26 とは "A" のチューリングジャンプを "n" 回反復したものを表す。従って、formula_27 は "A" そのものであり、formula_28 は formula_26 のチューリングジャンプである。
ポストの定理とその系.
ポストの定理は、算術的階層と formula_30 の形式のチューリング次数、すなわち空集合の有限回反復したチューリングジャンプとの密接な関係を確立する（空集合を任意の計算可能な集合に置き換えても定理は成り立つ）。
ポストの定理は次の通りである。
ポストの定理には様々な系があり、算術的階層とチューリング次数の様々な関係を表している。例えば、以下のような系がある。