ポストの定理

ポストの定理（英: Post's theorem）は、計算可能性理論における定理で、算術的階層とチューリング次数の関係を表している。名称はエミール・ポストに因んでいる。

背景

ポストの定理は定義可能性と再帰理論に関連したいくつかの概念を必要とする。この節ではそれら概念の概要を解説する。

算術的階層は、ペアノ算術で定義可能な自然数の集合を階層的に分類するものである。ある論理式が $\Sigma _{m}^{0}$ に属するとは、それが冠頭標準形（全ての量化子が先頭にある）の存在量化式で、存在量化と全称量化が $m$ 回交互にあって、それらが量化されていない論理式に適用されている場合である。次のような形式のペアノ算術の言語で書かれた論理式 $\phi (s)$ は $\Sigma _{m}^{0}$ 論理式である。

$\exists n_{1}\forall n_{2}\exists n_{3}\forall n_{4}\cdots Qn_{m}\rho (n_{1},\ldots ,n_{m},x_{1},\ldots ,x_{k})$

ここで ρ は量化子を含まない論理式で、Q は m が偶数なら $\forall$、m が奇数なら $\exists$ である。次のように $\rho$ が限定量化子のみを含む論理式

$\left(\exists n_{1}^{1}\exists n_{2}^{1}\cdots \exists n_{j_{1}}^{1}\right)\left(\forall n_{1}^{2}\cdots \forall n_{j_{2}}^{2}\right)\left(\exists n_{1}^{3}\cdots \right)\cdots \left(Q_{1}n_{1}^{m}\cdots \right)\rho (n_{1}^{1},\ldots n_{j_{m}}^{m},x_{1},\ldots ,x_{k})$

は、ペアノ算術の公理により、上記形式と等価である。そのため、$\Sigma _{m}^{0}$ 論理式をこの代替形式で定義することも珍しくない。

自然数の集合 A が $\Sigma _{m}^{0}$ であるとは、それを $\Sigma _{m}^{0}$ 論理式で定義できることを意味し、すなわち、$\Sigma _{m}^{0}$ 論理式 $\phi (s)$ を使って、自然数 n について $\phi (n)$ が成り立つときのみ、その自然数が A に含まれる。ある集合が $\Sigma _{m}^{0}$ であるとき、$n>m$ である任意の n についての $\Sigma _{n}^{0}$ でもある。ただし、個々の m について $\Sigma _{m}^{0}$ ではない $\Sigma _{m+1}^{0}$ 集合が存在する。従って、量化子の交代回数は、集合の複雑さの尺度を定義するのに必要である。

ポストの定理では、上で定義したような絶対的な算術的階層だけでなく、相対化された算術的階層も使う。自然数の集合 A が B に対して相対的に $\Sigma _{m}^{0}$ であることを $\Sigma _{m}^{0,B}$ と表記する。これは、B のメンバーシップを表す述語を含めた拡張言語で記述された $\Sigma _{m}^{0}$ 論理式で A を定義可能であることを意味する。

算術的階層が自然数の集合の定義可能性の尺度となる一方、チューリング次数は自然数の集合の計算不可能性のレベルの尺度となる。集合 A が集合 B にチューリング還元可能であることを $A\leq _{T}B$ と記述し、B についての神託を与える神託機械によって A の特性関数を計算できることを意味する。集合 A のチューリングジャンプは、A に関連する停止性問題の形式である。集合 A のチューリングジャンプ $A'$ は、A についての神託機械を持ち 0 が入力されたときに停止するチューリング機械のインデックスの集合である。あらゆる集合 A はそのチューリングジャンプにチューリング還元可能であるが、ある集合のチューリングジャンプは決して元の集合にチューリング還元できない。

ポストの定理は有限回反復されたチューリングジャンプを使用する。任意の自然数の集合 A について、$A^{(n)}$ とは A のチューリングジャンプを n 回反復したものを表す。従って、$A^{(0)}$ は A そのものであり、$A^{(n+1)}$ は $A^{(n)}$ のチューリングジャンプである。

ポストの定理とその系

ポストの定理は、算術的階層と $\emptyset ^{(n)}$ の形式のチューリング次数、すなわち空集合の有限回反復したチューリングジャンプとの密接な関係を確立する（空集合を任意の計算可能な集合に置き換えても定理は成り立つ）。

ポストの定理は次の通りである。

1. 集合 B が $\Sigma _{n+1}^{0}$ であるのは、$B$ が $\emptyset ^{(n)}$ の神託機械を持つチューリング機械により帰納可枚挙な場合である。すなわち、B が $\Sigma _{1}^{0,\emptyset ^{(n)}}$ で表される場合である。
2. 集合 $\emptyset ^{(n)}$ は、$n>0$ のあらゆる n について $\Sigma _{n}^{0}$ 完全である。すなわち、$\Sigma _{n}^{0}$ のあらゆる集合は $\emptyset ^{(n)}$ に多対一還元可能である。

ポストの定理には様々な系があり、算術的階層とチューリング次数の様々な関係を表している。例えば、以下のような系がある。

1. ある集合 C があるとする。集合 B が $\Sigma _{n+1}^{0,C}$ であるのは、B が $\Sigma _{1}^{0,C^{(n)}}$ となることと等価である。これはポストの定理の前半部分を C の神託機械で相対化したものである。
2. 集合 B が $\Delta _{n+1}$ であるのは、$B\leq _{T}\emptyset ^{(n)}$ と等価である。より一般化すると、B が $\Delta _{n+1}^{C}$ であるのは、$B\leq _{T}C^{(n)}$ と等価である。
3. 集合が算術的に定義できるのは、ある n について $\Sigma _{n}^{0}$ である場合である。ポストの定理によれば、集合が算術的といえるのは、その集合をある m について $\emptyset ^{(m)}$ にチューリング還元可能な場合のみである。

参考文献

• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7