ポストの定理とその系
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 10:09 UTC 版)
「ポストの定理」の記事における「ポストの定理とその系」の解説
ポストの定理は、算術的階層と ∅ ( n ) {\displaystyle \emptyset ^{(n)}} の形式のチューリング次数、すなわち空集合の有限回反復したチューリングジャンプとの密接な関係を確立する（空集合を任意の計算可能な集合に置き換えても定理は成り立つ）。 ポストの定理は次の通りである。 集合 B が Σ n + 1 0 {\displaystyle \Sigma _{n+1}^{0}} であるのは、 B {\displaystyle B} が ∅ ( n ) {\displaystyle \emptyset ^{(n)}} の神託機械を持つチューリング機械により帰納可枚挙な場合である。すなわち、B が Σ 1 0 , ∅ ( n ) {\displaystyle \Sigma _{1}^{0,\emptyset ^{(n)}}} で表される場合である。 集合 ∅ ( n ) {\displaystyle \emptyset ^{(n)}} は、 n > 0 {\displaystyle n>0} のあらゆる n について Σ n 0 {\displaystyle \Sigma _{n}^{0}} 完全である。すなわち、 Σ n 0 {\displaystyle \Sigma _{n}^{0}} のあらゆる集合は ∅ ( n ) {\displaystyle \emptyset ^{(n)}} に多対一還元可能である。 ポストの定理には様々な系があり、算術的階層とチューリング次数の様々な関係を表している。例えば、以下のような系がある。 ある集合 C があるとする。集合 B が Σ n + 1 0 , C {\displaystyle \Sigma _{n+1}^{0,C}} であるのは、B が Σ 1 0 , C ( n ) {\displaystyle \Sigma _{1}^{0,C^{(n)}}} となることと等価である。これはポストの定理の前半部分を C の神託機械で相対化したものである。 集合 B が Δ n + 1 {\displaystyle \Delta _{n+1}} であるのは、 B ≤ T ∅ ( n ) {\displaystyle B\leq _{T}\emptyset ^{(n)}} と等価である。より一般化すると、B が Δ n + 1 C {\displaystyle \Delta _{n+1}^{C}} であるのは、 B ≤ T C ( n ) {\displaystyle B\leq _{T}C^{(n)}} と等価である。 集合が算術的に定義できるのは、ある n について Σ n 0 {\displaystyle \Sigma _{n}^{0}} である場合である。ポストの定理によれば、集合が算術的といえるのは、その集合をある m について ∅ ( m ) {\displaystyle \emptyset ^{(m)}} にチューリング還元可能な場合のみである。
※この「ポストの定理とその系」の解説は、「ポストの定理」の解説の一部です。
「ポストの定理とその系」を含む「ポストの定理」の記事については、「ポストの定理」の概要を参照ください。
- ポストの定理とその系のページへのリンク
