極限計算可能関数
これが 0 ′ {\displaystyle 0'} -計算可能であることを示すには、半計算可能集合 Y {\displaystyle Y} で X ≤ T Y {\displaystyle X\leq _{T}Y} を満たすものを構成すればよい。以下、集合とその特性関数とを同一視する。まず Y {\displaystyle Y} を次で定める:
( x , n ) ∈ Y ⟺ ♯ { s ∣ X s ( x ) ≠ X s + 1 ( x ) } ≥ n {\displaystyle (x,n)\in Y\iff \sharp \{s\mid X_{s}(x)\neq X_{s+1}(x)\}\geq n}
ここで ♯ {\displaystyle \sharp } は集合の要素数を表す。つまり X s ( x ) {\displaystyle X_{s}(x)} の値が n {\displaystyle n} 回以上変化する場合に ( x , n ) {\displaystyle (x,n)} を Y {\displaystyle Y} に置く。すると Y {\displaystyle Y} をオラクルとして次のように X {\displaystyle X} を計算できる。入力 x {\displaystyle x} に対して ( x , n ) ∈ Y {\displaystyle (x,n)\in Y} を満たす最大の n {\displaystyle n} を探す。
以下、関数列 f 0 , f 1 , ... {\displaystyle f_{0},f_{1},\ldots } と入力 x {\displaystyle x} について f s ( x ) ≠ f s + 1 ( x ) {\displaystyle f_{s}(x)\neq f_{s+1}(x)} となるとき、ステージ s + 1 {\displaystyle s+1} で f s ( x ) {\displaystyle f_{s}(x)} が心変わり(英: mind change)するということにする。このとき極限計算可能関数とは有限回の心変わりで極限計算可能であるということができる。実際、極限
f ( x ) = lim s f s ( x ) {\displaystyle f(x)=\lim _{s}f_{s}(x)}
が存在するということは、心変わりの回数が有限回であることと同値である。
そこで極限計算可能関数を近似する関数列の心変わりの回数を制限することが考えられてくる。高々 n {\displaystyle n} 回の心変わりで極限計算可能な関数は n {\displaystyle n} -近似可能(英: n {\displaystyle n} -approximable)という。このクラスについて次が知られている:
任意の n {\displaystyle n} -近似可能関数は n + 1 {\displaystyle n+1} -近似可能である。
n {\displaystyle n} -近似可能でない n {\displaystyle n} +1-近似可能関数が存在する。
極限補題は自然数の集合が極限計算可能であることと 0 ′ {\displaystyle 0'} -計算可能であることとが同値であることを述べる。ここで 0 ′ {\displaystyle 0'} は空集合のチューリングジャンプである。相対化された極限補題は自然数の集合が D-極限計算可能であることと D'-計算可能であることとが同値であることを述べる。 さらにいえば極限補題(とその相対化)は一様に成立する。すなわち r ^ ( x , s ) {\displaystyle {\hat {r}}(x,s)} のインデックスから r ^ ( x ) {\displaystyle {\hat {r}}(x)} の 0 ′ {\displaystyle 0'} -相対的インデックスを計算できる。逆に r ^ ( x ) {\displaystyle {\hat {r}}(x)} の 0 ′ {\displaystyle 0'} -相対的インデックスから r ^ ( x , s ) {\displaystyle {\hat {r}}(x,s)} のインデックスを計算できる。
計算可能性理論における極限計算可能関数(きょくげんけいさんかのうかんすう、英: limit computabile function)とは、一様に計算可能な関数列の極限によって表せる関数をいう。極限において計算可能(英: computable in the limit)や極限帰納的(英: limit recursive)などともいう。集合が極限計算可能とはその特性関数が極限計算可能であることをいう。
関数列が D-計算可能であるとき、極限の関数は D-極限計算可能であるという。