極限計算可能関数

計算可能性理論における極限計算可能関数(きょくげんけいさんかのうかんすう、)とは、一様に計算可能な関数列の極限によって表せる関数をいう。極限において計算可能()や極限帰納的()などともいう。集合が極限計算可能とはその特性関数が極限計算可能であることをいう。
関数列が "D"-計算可能であるとき、極限の関数は "D"-極限計算可能であるという。
正式な定義.
関数 formula_1 が極限計算可能であるとは、計算可能全域関数 formula_2 が存在して
が成り立つことをいう。
関数 formula_1 が "D"-極限計算可能であるとは、"D"-計算可能全域関数 formula_2 が存在して
が同様に成り立つことをいう。
コード化可能な集合が極限計算可能とはその特性関数が極限計算可能であることをいう。これに対して、集合が計算可能であることと、ある関数 formula_7 によって極限計算可能であり、かつ formula_7 の値が安定する formula_9 の値が formula_10 に対して計算可能であることとは同値である。
極限補題.
極限補題は自然数の集合が極限計算可能であることと formula_11-計算可能であることとが同値であることを述べる。ここで formula_11 は空集合のチューリングジャンプである。相対化された極限補題は自然数の集合が "D"-極限計算可能であることと D'-計算可能であることとが同値であることを述べる。
さらにいえば極限補題(とその相対化)は一様に成立する。すなわち formula_2 のインデックスから formula_14 の formula_11-相対的インデックスを計算できる。逆に formula_14 の formula_11-相対的インデックスから formula_2 のインデックスを計算できる。
証明.
formula_11 は帰納的可算集合であるから実効的に枚挙できる。したがって次のようにして formula_11 が極限計算可能であることが分かる：
明らかに formula_2 の formula_23 に於ける極限は formula_11 の特性関数である。極限計算可能関数のクラスは recursively closed である。すなわち関数合成、原始再帰、最小化によって閉じている。したがって任意の formula_11-計算可能関数は極限計算可能である。
逆に formula_26 を極限計算可能な集合とし、 formula_27 を formula_26 に収束する一様に再帰的な集合列とする。これが formula_11-計算可能であることを示すには、半計算可能集合 formula_30 で formula_31 を満たすものを構成すればよい。以下、集合とその特性関数とを同一視する。まず formula_30 を次で定める：
ここで formula_34 は集合の要素数を表す。つまり formula_35 の値が formula_36 回以上変化する場合に formula_37 を formula_30 に置く。すると formula_30 をオラクルとして次のように formula_26 を計算できる。入力 formula_10 に対して formula_42 を満たす最大の formula_36 を探す。これは formula_35 が収束することから必ず存在する。このとき formula_45 の値はちょうど formula_36 回だけ変化する。そこで formula_36 が偶数ならば formula_48 を、 formula_36 が奇数ならば formula_50 を出力する。この出力は formula_51 に等しい。
算術的階層における位置づけ.
ポストの定理によれば formula_11-計算可能であることと formula_54 であることとは同値である。したがって極限補題は任意の極限計算可能集合が formula_54 であることを導く。実際 formula_26 を極限計算可能集合とし、 formula_27 を formula_26 に収束する一様に再帰的な集合列とすれば、
が成り立つ。右辺は formula_60 である。また
が成り立つ。右辺は formula_62 である。
極限計算可能実数.
実数 "x" が極限計算可能であるとは、計算可能有理数列 formula_63 (あるいは同じことだが計算可能実数列)で "x" に収束するものが存在することをいう。これに対して、実数が計算可能であることと、ある有理数列によって極限計算可能であり、かつ収束列の収束率が計算可能であることとは同値である。
実数をビットの無限列と見做せば次の定義と上の定義とは同等である。無限ビット列 formula_64 が極限計算可能であるとは、計算可能な0-1関数 formula_65 が存在して formula_66 が成り立つことをいう。したがって任意の "i" に対して、 "t" を増加させると formula_67 の値は最終的に formula_68 の値と等しくなる。計算可能実数の場合と同様に、極限計算可能関数の2つの表現を実効的に変換することはできない。
心変わりの制限.
以下、関数列 formula_69 と入力 formula_10 について formula_71 となるとき、ステージ formula_72 で formula_73 が心変わり（）するということにする。このとき極限計算可能関数とは有限回の心変わりで極限計算可能であるということができる。実際、極限
が存在するということは、心変わりの回数が有限回であることと同値である。
そこで極限計算可能関数を近似する関数列の心変わりの回数を制限することが考えられてくる。高々 formula_36 回の心変わりで極限計算可能な関数は formula_36-近似可能（）という。このクラスについて次が知られている：
すなわち心変わりの回数が定数で抑えられる極限計算可能関数のクラスは、その定数によって階層を成している。また心変わりの回数を定数で抑えられないような極限計算可能関数が存在する。他のクラスとの関係としては次が知られている：
集合の心変わりの回数については、近似列 formula_86 の初項 formula_87 の形を制限することが考えられる。そこで空集合から始めて高々 formula_36 回の心変わりで極限計算可能な集合は formula_36-帰納的可算という。また補集合が formula_36-帰納的可算な集合は補 formula_36-帰納的可算という。これらのクラスについては次が知られている：
また他のクラスとの関係としては次が知られている：
すなわち formula_108-近似可能集合のクラス formula_109、 formula_36-r.e.集合のクラス formula_111、co-formula_36-r.e.集合のクラス formula_113 は、それぞれ算術的階層における formula_114 と対応する形の階層構造を成している。すなわちこの階層は次のような構造を持つ。ここで矢印は包含を示す。
formula_115
これをエルショフの階層という。エルショフの階層はを用いることによって構成的順序数へ一般化できる。このとき極限計算可能関数はある構成的順序数 formula_116 について formula_116-近似可能となる。すなわち極限計算可能関数はエルショフの階層によって完全に分類される。
心変わりの回数がある計算可能関数で抑えられるとき、極限関数は formula_64-近似可能という。このとき、集合 formula_119 が formula_64-近似可能であることと、formula_119 が formula_11 に真理表還元可能であることとは同値である。この事実は、先の極限補題の証明において、formula_123 なる神託問い合わせの formula_36 が再帰的関数で抑えられることから分かる。