極限における計算

計算可能性理論において、関数が一様計算可能な関数列の極限である場合、その関数は極限計算可能であると呼ばれる。極限計算可能、極限再帰的、再帰近似可能といった用語も用いられる。極限計算可能な関数とは、その真の値において最終的に正しい計算可能な推測手順を許容する関数と考えることができる。集合が極限計算可能であるのは、その特性関数が極限計算可能である場合のみである。

数列がDに関して一様に計算可能であるならば、関数はDにおいて極限計算可能である。

全体関数${\displaystyle r(x)}$総計算可能な関数が存在する場合、極限は計算可能であるか。$\displaystyle {\hat {r}}(x,s)}$そのため

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

総関数${\displaystyle r(x)}$総関数が存在する場合、極限はDで計算可能か$\displaystyle {\hat {r}}(x,s)}$Dで計算可能であり、かつそれを満たす

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

自然数の集合は、その特性関数が極限において計算可能である場合に限り、極限において計算可能であると定義される。対照的に、集合は、関数によって極限において計算可能な場合に限り、計算可能である。${\displaystyle \phi (t,i)}$また、入力iを受け取り、 tの値が十分に大きい値を返す2 番目の計算可能な関数があり、${\displaystyle \phi (t,i)}$状況は安定しました。

極限補題は、自然数の集合が極限計算可能であるのは、その集合がから計算可能である場合に限る、と述べている。${\displaystyle 0'}$（空集合のチューリングジャンプ）。相対化された極限補題は、集合が極限計算可能であることを述べている。${\displaystyle D}$から計算可能な場合に限り${\displaystyle D'}$さらに、極限補題（およびその相対化）は一様に成り立つ。したがって、関数のインデックスから$\displaystyle {\hat {r}}(x,s)}$インデックスへ$\displaystyle {\hat {r}}(x)}$相対的に${\displaystyle 0'}$インデックスから$\displaystyle {\hat {r}}(x)}$相対的に${\displaystyle 0'}$何らかのインデックスへ$\displaystyle {\hat {r}}(x,s)}$制限がある$\displaystyle {\hat {r}}(x)}$。

実数xは、計算可能な数列が存在する場合に極限において計算可能である。$\displaystyle r_{i}}$有理数列（または、同等の計算可能な実数列）がxに収束する。対照的に、実数が計算可能であるのは、その実数に収束し、かつ計算可能な収束係数を持つ有理数列が存在する場合に限る。

実数をビット列とみなした場合、以下の同等の定義が成り立つ。無限列${\displaystyle \omega }$2進数の桁数が極限において計算可能であるのは、全計算可能な関数が存在する場合に限る。${\displaystyle \phi (t,i)}$セット内の値を取る${\displaystyle \{0,1\}}$各iに対して極限${\displaystyle \lim _{t\rightarrow \infty }\phi (t,i)}$存在し、等しい${\displaystyle \omega (i)}$したがって、各iについて、t が増加するにつれて、${\displaystyle \phi (t,i)}$最終的には定数となり、等しくなります${\displaystyle \omega (i)}$計算可能な実数の場合と同様に、極限計算可能な実数の2つの表現の間を効果的に行き来することはできません。

• 停止問題を符号化する二進展開を持つ実数は、極限においては計算可能であるが、計算可能ではない。
• 二進展開によって一階算術の真理集合を符号化する実数は、極限において計算不可能である。
• チャイティン定数。

関数を介してα-再帰理論の極限補題の修正版が存在する。${\displaystyle \alpha }$算術的階層とは、許容される順序数に関して定義された階層のことである。${\displaystyle \alpha }$[ ^{3 ]​}

与えられた許容順序数に対して${\displaystyle \alpha }$定義する${\displaystyle \alpha }$-算術階層:

• 関係${\displaystyle R}$の上${\displaystyle \alpha }$は${\displaystyle {\boldsymbol {\シグマ }}_{0}}$もしそうなら${\displaystyle \alpha }$再帰的。
• ${\displaystyle R}$は$\displaystyle {\boldsymbol {\Sigma }}_{n+1}}$それが投影である場合${\displaystyle {\boldsymbol {\Pi }}_{n}}$関係。
• ${\displaystyle R}$は${\displaystyle {\boldsymbol {\Pi }}_{n}}$その補集合が$\displaystyle {\boldsymbol {\Sigma }}_{n}}$。

させて${\displaystyle f}$部分関数である${\displaystyle \alpha }$に${\displaystyle \alpha }$以下は同等です。

• （グラフ）${\displaystyle f}$は${\displaystyle {\boldsymbol {\シグマ }}_{2}}$。
• ${\displaystyle f}$弱く${\displaystyle \alpha }$-再帰的に${\displaystyle {\boldsymbol {0}}^{\プライム }}$、${\displaystyle \alpha }$-ジャンプ${\displaystyle \emptyset }$インデックスを使用して${\displaystyle \alpha }$計算可能な関数。
• があります${\displaystyle \alpha }$再帰関数${\displaystyle f':\alpha \times \alpha \to \alpha }$近似する${\displaystyle f}$そのため${\displaystyle f(\gamma )\simeq \lim _{\sigma \to \alpha }f'(\sigma ,\gamma )}$。

${\displaystyle f\simeq g}$次のいずれかを示す${\displaystyle f(x)}$そして${\displaystyle g(x)}$両方とも未定義であるか、両方とも定義されていて等しい。

• スペッカーシーケンス

1. J. Schmidhuber、「一般化されたコルモゴロフ複雑性の階層と極限で計算可能な非可算普遍尺度」、International Journal of Foundations of Computer Science、2002年、doi : 10.1142/S0129054102001291。
2. R. ソアレ。『再帰的に列挙可能な集合と次数』。シュプリンガー・フェルラーク、1987年。
3. V. Brattka.チューリングジャンプと極限の間のガロア接続. Log. Methods Comput. Sci. , 2018, doi : 10.23638/LMCS-14(3:13)2018 .