極限計算可能関数
ポストの定理によれば 0 ′ {\displaystyle 0'} -計算可能であることと Δ 2 0 {\displaystyle \Delta _{2}^{0}} であることとは同値である。したがって極限補題は任意の極限計算可能集合が Δ 2 0 {\displaystyle \Delta _{2}^{0}} であることを導く。実際 X {\displaystyle X} を極限計算可能集合とし、 X s {\displaystyle X_{s}} を X {\displaystyle X} に収束する一様に再帰的な集合列とすれば、
x ∈ X ⟺ ∃ s ∀ t ( s ≤ t → x ∈ X t ) {\displaystyle x\in X\iff \exists s\forall t(s\leq t\to x\in X_{t})}
が成り立つ。右辺は Σ 2 0 {\displaystyle \Sigma _{2}^{0}} である。また
x ∈ X ⟺ ∀ s ∃ t ( s ≤ t ∧ x ∈ X t ) {\displaystyle x\in X\iff \forall s\exists t(s\leq t\wedge x\in X_{t})}
が成り立つ。右辺は Π 2 0 {\displaystyle \Pi _{2}^{0}} である。
集合は n + 1 {\displaystyle n+1} -r.e.かつco- n + 1 {\displaystyle n+1} -r.e.である。
任意のco- n {\displaystyle n} -r.e.集合は n + 1 {\displaystyle n+1} -r.e.かつco- n + 1 {\displaystyle n+1} -r.e.である。
また他のクラスとの関係としては次が知られている:
1 {\displaystyle 1} -r.e.であることとr.e.であることとは同値。
co- 1 {\displaystyle 1} -r.e.であることとco-r.e.であることとは同値。
2 {\displaystyle 2} -r.e.であることとd-r.e.(2つのr.e.集合の差集合で書ける)であることとは同値。
n + 1 {\displaystyle n+1} -r.e.かつco- n + 1 {\displaystyle n+1} -r.e.であることと n {\displaystyle n} -近似可能であることとは同値。
任意の n {\displaystyle n} -r.e.集合は n {\displaystyle n} -近似可能である。
任意のco- n {\displaystyle n} -r.e.集合は n {\displaystyle n} -近似可能である。
すなわち n − 1 {\displaystyle n-1} -近似可能集合のクラス Δ n − 1 {\displaystyle \Delta _{n}^{-1}} 、 n {\displaystyle n} -r.
とくにそのような例は0-1関数として得られる。すなわち n {\displaystyle n} -近似可能でない n + 1 {\displaystyle n+1} -近似可能集合が存在する。
いかなる n {\displaystyle n} についても n {\displaystyle n} -近似可能でない、極限計算可能関数が存在する。とくにそのような例は0-1関数として得られる。
すなわち心変わりの回数が定数で抑えられる極限計算可能関数のクラスは、その定数によって階層を成している。また心変わりの回数を定数で抑えられないような極限計算可能関数が存在する。他のクラスとの関係としては次が知られている:
0 {\displaystyle 0} -近似可能であることと計算可能であることとは同値。
集合の心変わりの回数については、近似列 A s {\displaystyle A_{s}} の初項 A 0 {\displaystyle A_{0}} の形を制限することが考えられる。そこで空集合から始めて高々 n {\displaystyle n} 回の心変わりで極限計算可能な集合は n {\displaystyle n} -帰納的可算という。また補集合が n {\displaystyle n} -帰納的可算な集合は補 n {\displaystyle n} -帰納的可算という。これらのクラスについては次が知られている:
任意の n {\displaystyle n} -r.e.