極限計算可能関数

計算可能性理論における極限計算可能関数(きょくげんけいさんかのうかんすう、英: limit computabile function)とは、一様に計算可能な関数列の極限によって表せる関数をいう。極限において計算可能(英: computable in the limit)や極限帰納的(英: limit recursive)などともいう。集合が極限計算可能とはその特性関数が極限計算可能であることをいう。

関数列が D-計算可能であるとき、極限の関数は D-極限計算可能であるという。

正式な定義

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

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

が成り立つことをいう。

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

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

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

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

極限補題

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

証明

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

$\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}}$

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

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

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

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

${\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}}$

算術的階層における位置づけ

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

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

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

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

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

極限計算可能実数

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

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

例

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

心変わりの制限

以下、関数列 $f_{0},f_{1},\ldots$ と入力 $x$ について $f_{s}(x)\neq f_{s+1}(x)$ となるとき、ステージ $s+1$ で $f_{s}(x)$ が心変わり（英: mind change）するということにする。このとき極限計算可能関数とは有限回の心変わりで極限計算可能であるということができる。実際、極限

$f(x)=\lim _{s}f_{s}(x)$

が存在するということは、心変わりの回数が有限回であることと同値である。

そこで極限計算可能関数を近似する関数列の心変わりの回数を制限することが考えられてくる。高々 $n$ 回の心変わりで極限計算可能な関数は $n$-近似可能（英: $n$-approximable）という。このクラスについて次が知られている：

• 任意の $n$-近似可能関数は $n+1$-近似可能である。
• $n$-近似可能でない $n$+1-近似可能関数が存在する。とくにそのような例は0-1関数として得られる。すなわち $n$-近似可能でない $n+1$-近似可能集合が存在する。
• いかなる $n$ についても $n$-近似可能でない、極限計算可能関数が存在する。とくにそのような例は0-1関数として得られる。

すなわち心変わりの回数が定数で抑えられる極限計算可能関数のクラスは、その定数によって階層を成している。また心変わりの回数を定数で抑えられないような極限計算可能関数が存在する。他のクラスとの関係としては次が知られている：

• $0$-近似可能であることと計算可能であることとは同値。

集合の心変わりの回数については、近似列 $A_{s}$ の初項 $A_{0}$ の形を制限することが考えられる。そこで空集合から始めて高々 $n$ 回の心変わりで極限計算可能な集合は $n$-帰納的可算という。また補集合が $n$-帰納的可算な集合は補 $n$-帰納的可算という。これらのクラスについては次が知られている：

• 任意の $n$-r.e.集合は $n+1$-r.e.かつco-$n+1$-r.e.である。
• 任意のco-$n$-r.e.集合は $n+1$-r.e.かつco-$n+1$-r.e.である。

また他のクラスとの関係としては次が知られている：

• $1$-r.e.であることとr.e.であることとは同値。
• co-$1$-r.e.であることとco-r.e.であることとは同値。
• $2$-r.e.であることとd-r.e.（2つのr.e.集合の差集合で書ける）であることとは同値。
• $n+1$-r.e.かつco-$n+1$-r.e.であることと $n$-近似可能であることとは同値。
• 任意の $n$-r.e.集合は $n$-近似可能である。
• 任意のco-$n$-r.e.集合は $n$-近似可能である。

すなわち $n-1$-近似可能集合のクラス $\Delta _{n}^{-1}$、 $n$-r.e.集合のクラス $\Sigma _{n}^{-1}$、co-$n$-r.e.集合のクラス $\Pi _{n}^{-1}$ は、それぞれ算術的階層における $\Delta _{n}^{0},\Sigma _{n}^{0},\Pi _{n}^{0}$ と対応する形の階層構造を成している。すなわちこの階層は次のような構造を持つ。ここで矢印は包含を示す。

${\begin{matrix}&&\Sigma _{1}^{-1}&&&&\Sigma _{2}^{-1}&&\cdots \\&\nearrow &&\searrow &&\nearrow \\\Delta _{1}^{-1}&&&&\Delta _{2}^{-1}&&&&\cdots \\&\searrow &&\nearrow &&\searrow \\&&\Pi _{1}^{-1}&&&&\Pi _{2}^{-1}&&\cdots \end{matrix}}{\begin{matrix}&&\Sigma _{n}^{-1}&&&\cdots \\&\nearrow &&\searrow \\\quad \Delta _{n}^{-1}&&&&\Delta _{n+1}^{-1}&\cdots \\&\searrow &&\nearrow \\&&\Pi _{n}^{-1}&&&\cdots \end{matrix}}$

これをエルショフの階層という。エルショフの階層はクリーネのOを用いることによって構成的順序数へ一般化できる。このとき極限計算可能関数はある構成的順序数 $\alpha$ について $\alpha$-近似可能となる。すなわち極限計算可能関数はエルショフの階層によって完全に分類される。

心変わりの回数がある計算可能関数で抑えられるとき、極限関数は $\omega$-近似可能という。このとき、集合 $A$ が $\omega$-近似可能であることと、$A$ が $0'$ に真理表還元可能であることとは同値である。この事実は、先の極限補題の証明において、$(x,n)\in Y$ なる神託問い合わせの $n$ が再帰的関数で抑えられることから分かる。

関連項目

• スペッカー列
• 計算論的学習理論

参考文献

1. J. Schmidhuber, "Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit", International Journal of Foundations of Computer Science, 2002.
2. R. Soare. Recursively Enumerable Sets and Degrees, Springer-Verlag, 1987.
3. R. G. Downey, D. R. Hirschfeldt. Algorithmic Randomness and Complexity, Springer, 2010.
4. W. Calvert, R. Miller, J. C. Reimann. The Distance Function on a Computable Graph, arXiv:1111.2480, 2011.
5. Richard L. Epstein, Richard Haas, Richard L. Kramer. Hierarchies of sets and degrees below $0'$, Logic Year 1979-1980, Lecture Notes in Mathematics, Vol. 859, Springer-Verlag, pp.32-48, 1981.