出典: フリー百科事典『ウィキペディア（Wikipedia）』
ポストの定理 （英 : Post's theorem ）は、計算可能性理論 における定理で、算術的階層 とチューリング次数 の関係を表している。名称はエミール・ポスト に因んでいる。
ポストの定理は定義可能性と再帰理論に関連したいくつかの概念を必要とする。この節ではそれら概念の概要を解説する。
算術的階層 は、ペアノ算術 で定義可能な自然数 の集合を階層的に分類するものである。ある論理式 が
Σ
m
0
{\displaystyle \Sigma _{m}^{0}}
冠頭標準形 （全ての量化 子が先頭にある）の存在量化式 で、存在量化と全称量化 が
m
{\displaystyle m}
ϕ
(
s
)
{\displaystyle \phi (s)}
Σ
m
0
{\displaystyle \Sigma _{m}^{0}}
∃
n
1
∀
n
2
∃
n
3
∀
n
4
⋯
Q
n
m
ρ
(
n
1
,
…
,
n
m
,
x
1
,
…
,
x
k
)
{\displaystyle \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 が偶数なら
∀
{\displaystyle \forall }
m が奇数なら
∃
{\displaystyle \exists }
ρ
{\displaystyle \rho }
限定量化 子のみを含む論理式
(
∃
n
1
1
∃
n
2
1
⋯
∃
n
j
1
1
)
(
∀
n
1
2
⋯
∀
n
j
2
2
)
(
∃
n
1
3
⋯
)
⋯
(
Q
1
n
1
m
⋯
)
ρ
(
n
1
1
,
…
n
j
m
m
,
x
1
,
…
,
x
k
)
{\displaystyle \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})}
は、ペアノ算術 の公理により、上記形式と等価である。そのため、
Σ
m
0
{\displaystyle \Sigma _{m}^{0}}
自然数の集合 A が
Σ
m
0
{\displaystyle \Sigma _{m}^{0}}
Σ
m
0
{\displaystyle \Sigma _{m}^{0}}
Σ
m
0
{\displaystyle \Sigma _{m}^{0}}
ϕ
(
s
)
{\displaystyle \phi (s)}
n について
ϕ
(
n
)
{\displaystyle \phi (n)}
A に含まれる。ある集合が
Σ
m
0
{\displaystyle \Sigma _{m}^{0}}
n
>
m
{\displaystyle n>m}
n についての
Σ
n
0
{\displaystyle \Sigma _{n}^{0}}
m について
Σ
m
0
{\displaystyle \Sigma _{m}^{0}}
Σ
m
+
1
0
{\displaystyle \Sigma _{m+1}^{0}}
ポストの定理では、上で定義したような絶対的な算術的階層だけでなく、相対化された算術的階層も使う。自然数の集合 A が B に対して相対的に
Σ
m
0
{\displaystyle \Sigma _{m}^{0}}
Σ
m
0
,
B
{\displaystyle \Sigma _{m}^{0,B}}
B のメンバーシップを表す述語を含めた拡張言語で記述された
Σ
m
0
{\displaystyle \Sigma _{m}^{0}}
A を定義可能であることを意味する。
算術的階層が自然数の集合の定義可能性の尺度となる一方、チューリング次数 は自然数の集合の計算不可能性のレベルの尺度となる。集合 A が集合 B にチューリング還元 可能であることを
A
≤
T
B
{\displaystyle A\leq _{T}B}
B についての神託を与える神託機械 によって A の特性関数 を計算できることを意味する。集合 A のチューリングジャンプ は、A に関連する停止性問題 の形式である。集合 A のチューリングジャンプ
A
′
{\displaystyle A'}
A についての神託機械を持ち 0 が入力されたときに停止するチューリング機械のインデックスの集合である。あらゆる集合 A はそのチューリングジャンプにチューリング還元可能であるが、ある集合のチューリングジャンプは決して元の集合にチューリング還元できない。
ポストの定理は有限回反復されたチューリングジャンプを使用する。任意の自然数の集合 A について、
A
(
n
)
{\displaystyle A^{(n)}}
A のチューリングジャンプを n 回反復したものを表す。従って、
A
(
0
)
{\displaystyle A^{(0)}}
A そのものであり、
A
(
n
+
1
)
{\displaystyle A^{(n+1)}}
A
(
n
)
{\displaystyle A^{(n)}}
ポストの定理は、算術的階層と
∅
(
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)}}
