極限計算可能関数

関数 ${\displaystyle r(x)}$ が極限計算可能であるとは、計算可能全域関数 ${\displaystyle {\hat {r}}(x,s)}$ が存在して

${\displaystyle r(x)=\lim _{s\to \infty }{\hat {r}}(x,s)}$

が成り立つことをいう。

関数 ${\displaystyle r(x)}$ が D-極限計算可能であるとは、D-計算可能全域関数 ${\displaystyle {\hat {r}}(x,s)}$ が存在して

${\displaystyle r(x)=\lim _{s\to \infty }{\hat {r}}(x,s)}$

が同様に成り立つことをいう。

コード化可能な集合が極限計算可能とはその特性関数が極限計算可能であることをいう。これに対して、集合が計算可能であることと、ある関数 ${\displaystyle \varphi (x,s)}$ によって極限計算可能であり、かつ ${\displaystyle \varphi (x,s)}$ の値が安定する ${\displaystyle s}$ の値が ${\displaystyle x}$ に対して計算可能であることとは同値である。

Summarize Timeline Top Qs Fact Check

極限補題は自然数の集合が極限計算可能であることと ${\displaystyle 0'}$-計算可能であることとが同値であることを述べる。ここで ${\displaystyle 0'}$ は空集合のチューリングジャンプである。相対化された極限補題は自然数の集合が D-極限計算可能であることと D'-計算可能であることとが同値であることを述べる。 さらにいえば極限補題(とその相対化)は一様に成立する。すなわち ${\displaystyle {\hat {r}}(x,s)}$ のインデックスから ${\displaystyle {\hat {r}}(x)}$ の ${\displaystyle 0'}$-相対的インデックスを計算できる。逆に ${\displaystyle {\hat {r}}(x)}$ の ${\displaystyle 0'}$-相対的インデックスから ${\displaystyle {\hat {r}}(x,s)}$ のインデックスを計算できる。

${\displaystyle 0'}$ は帰納的可算集合であるから実効的に枚挙できる。したがって次のようにして ${\displaystyle 0'}$ が極限計算可能であることが分かる：

${\displaystyle \displaystyle {\hat {r}}(x,s)={\begin{cases}1&{\text{if by stage }}s,x{\text{ has been enumerated into }}0'\\0&{\text{if not}}\end{cases}}}$

明らかに ${\displaystyle {\hat {r}}(x,s)}$ の ${\displaystyle s\to \infty }$ に於ける極限は ${\displaystyle 0'}$ の特性関数である。極限計算可能関数のクラスは recursively closed である。すなわち関数合成、原始再帰、最小化によって閉じている。したがって任意の ${\displaystyle 0'}$-計算可能関数は極限計算可能である。

逆に ${\displaystyle X}$ を極限計算可能な集合とし、 ${\displaystyle X_{s}}$ を ${\displaystyle X}$ に収束する一様に再帰的な集合列とする。これが ${\displaystyle 0'}$-計算可能であることを示すには、半計算可能集合 ${\displaystyle Y}$ で ${\displaystyle X\leq _{T}Y}$ を満たすものを構成すればよい。以下、集合とその特性関数とを同一視する。まず ${\displaystyle Y}$ を次で定める：

${\displaystyle (x,n)\in Y\iff \sharp \{s\mid X_{s}(x)\neq X_{s+1}(x)\}\geq n}$

ここで ${\displaystyle \sharp }$ は集合の要素数を表す。つまり ${\displaystyle X_{s}(x)}$ の値が ${\displaystyle n}$ 回以上変化する場合に ${\displaystyle (x,n)}$ を ${\displaystyle Y}$ に置く。すると ${\displaystyle Y}$ をオラクルとして次のように ${\displaystyle X}$ を計算できる。入力 ${\displaystyle x}$ に対して ${\displaystyle (x,n)\in Y}$ を満たす最大の ${\displaystyle n}$ を探す。これは ${\displaystyle X_{s}(x)}$ が収束することから必ず存在する。このとき ${\displaystyle X_{0}(x),X_{1}(x),\ldots }$ の値はちょうど ${\displaystyle n}$ 回だけ変化する。そこで ${\displaystyle n}$ が偶数ならば ${\displaystyle X_{0}(x)}$ を、 ${\displaystyle n}$ が奇数ならば ${\displaystyle 1-X_{0}(x)}$ を出力する。この出力は ${\displaystyle X(x)}$ に等しい。

${\displaystyle {\begin{matrix}{\mbox{accept}}&X_{0}(x)&X_{1}(x)&&X_{3}(x)&&&\cdots \\{\mbox{reject}}&&&X_{2}(x)&&X_{4}(x)&X_{5}(x)&\cdots \\{\mbox{mind change}}&0&0&1&2&3&3&\cdots \end{matrix}}}$

ポストの定理によれば ${\displaystyle 0'}$-計算可能であることと ${\displaystyle \Delta _{2}^{0}}$ であることとは同値である。したがって極限補題は任意の極限計算可能集合が ${\displaystyle \Delta _{2}^{0}}$ であることを導く。実際 ${\displaystyle X}$ を極限計算可能集合とし、 ${\displaystyle X_{s}}$ を ${\displaystyle X}$ に収束する一様に再帰的な集合列とすれば、

${\displaystyle x\in X\iff \exists s\forall t(s\leq t\to x\in X_{t})}$

が成り立つ。右辺は ${\displaystyle \Sigma _{2}^{0}}$ である。また

${\displaystyle x\in X\iff \forall s\exists t(s\leq t\wedge x\in X_{t})}$

が成り立つ。右辺は ${\displaystyle \Pi _{2}^{0}}$ である。

実数 x が極限計算可能であるとは、計算可能有理数列 ${\displaystyle r_{i}}$ (あるいは同じことだが計算可能実数列)で x に収束するものが存在することをいう。これに対して、実数が計算可能であることと、ある有理数列によって極限計算可能であり、かつ収束列の収束率が計算可能であることとは同値である。

実数をビットの無限列と見做せば次の定義と上の定義とは同等である。無限ビット列 ${\displaystyle \omega }$ が極限計算可能であるとは、計算可能な0-1関数 ${\displaystyle \varphi (t,i)}$ が存在して ${\displaystyle \lim _{t\to \infty }\varphi (t,i)=\omega _{i}}$ が成り立つことをいう。したがって任意の i に対して、 t を増加させると ${\displaystyle \varphi (t,i)}$ の値は最終的に ${\displaystyle \omega _{i}}$ の値と等しくなる。計算可能実数の場合と同様に、極限計算可能関数の2つの表現を実効的に変換することはできない。

• 二進展開が停止性問題のコードに一致する実数は極限計算可能だが計算可能でない。
• 二進展開が真の算術のコードに一致する実数は極限計算可能でない。