極限の計算

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

シーケンスがDに対して一様に計算可能であれば、関数はDで極限計算可能です。

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

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

全関数がDで極限計算可能であるとは、 Dで計算可能な全関数が存在し、かつ以下を満たす場合 である。${\displaystyle r(x)}$${\displaystyle {\hat {r}}(x,s)}$

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

自然数の集合は、その特性関数が極限で計算可能である場合に限り、極限で計算可能であると定義されます。対照的に、集合が計算可能であるのは、関数によって極限で計算可能であり、入力i を受け取り、安定するのに十分な大きさのtの値を返す2 番目の計算可能な関数が存在する場合のみです。 ${\displaystyle \phi (t,i)}$${\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)}$

は[計算可能列挙可能]集合であるため、計算可能関数が定義できるため、極限自体で計算可能でなければならない。 ${\displaystyle 0'}$

${\displaystyle \displaystyle {\hat {r}}(x,s)={\begin{cases}1&{\text{ステージ }}s までに、x{\text{ が }}0' に列挙されている場合\\0&{\text{そうでない場合}}\end{cases}}}$

が無限大になるときの極限は の特性関数です。 ${\displaystyle r(x)}$${\displaystyle s}$${\displaystyle 0'}$

したがって、チューリング還元によって極限計算可能性が保存されるなら、 を示すだけで十分です。これは、 から計算可能なすべての集合が極限計算可能であることを示すからです。 特性関数と同一視される集合と、極限 を持つ計算可能関数 を固定します。あるチューリング還元 に対して であると仮定し、 が計算可能関数を次のように 定義するとします。${\displaystyle 0'}$${\displaystyle X,Y}$${\displaystyle X_{s}}$${\displaystyle X}$${\displaystyle Y(z)=\phi ^{X}(z)}$${\displaystyle \phi}$${\displaystyle Y_{s}}$

${\displaystyle \displaystyle Y_{s}(z)={\begin{cases}\phi ^{X_{s}}(z)&{\text{if }}\phi ^{X_{s}}{\text{ は最大 }}s{\text{ ステップで収束します。}}\\0&{\text{それ以外の場合 }}\end{cases}}}$

ここで、計算がステップごとに収束し、の最初のビットのみを調べると仮定します。ここで、すべての に対して となるような を選びます。 の場合、計算は最大でステップごとに まで収束します。したがって にはの極限があるため、極限は計算可能です。 ${\displaystyle \phi ^{X}(z)}$${\displaystyle s}$${\displaystyle s}$${\displaystyle X}$${\displaystyle s'>s}$${\displaystyle z<s+1}$ ${\displaystyle X_{s'}(z)=X(z)}$${\displaystyle t>s'}$${\displaystyle \phi ^{X_{t}}(z)}$${\displaystyle s'<t}$${\displaystyle \phi ^{X}(z)}$${\displaystyle Y_{s}(z)}$${\displaystyle \phi ^{X}(z)=Y(z)}$${\displaystyle Y}$

集合はポストの定理によってから計算可能な集合にすぎないので、極限補題は、極限計算可能集合が集合であることも意味します。 ${\displaystyle \Delta _{2}^{0}}$${\displaystyle 0'}$${\displaystyle \Delta _{2}^{0}}$

極限計算可能性と - 性の同値性を予見する初期の結果は、1954年にモストフスキーによって階層と公式を用いて予見された。ここで、 は任意の原始再帰関数から得られる関数であり、 はと同値である。^[1]${\displaystyle \Delta _{2}^{0}}$${\displaystyle \mathbf {P} _{2}^{(1)}}$${\displaystyle \exists y(\lim _{x\to \infty }10^{-x}\gamma (x,y)<1)}$${\displaystyle \gamma (x,y)}$${\displaystyle \varrho}$${\displaystyle \exists p\forall s(\varrho (p,s,y)=0)}$${\displaystyle \exists x_{0}\forall x(x>x_{0}\implies \gamma (x,y)=0)}$

極限計算可能性の反復は算術階層を登るのに使用できる。つまり、すべての極限が存在するという仮定の下で、 -項関数が であるのは、それが何らかの-項再帰関数 \(g\)の形式で記述できる場合である。 ^[2]${\displaystyle m}$${\displaystyle f(x_{1},\ldots,x_{m})}$${\displaystyle \Delta _{k+1}^{0}}$${\displaystyle \lim _{n_{k}}\lim _{n_{k-1}}\ldots \lim _{n_{1}}g(x_{1},\ldots ,x_{m},n_{k},\ldots ,n_{1})}$${\displaystyle m+k}$

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

実数をビットのシーケンスとして見ると、次の同等の定義が成り立ちます。2進数の無限シーケンスが の極限で計算可能であるのは、各iに対して極限が存在し に等しいような集合内の値を取る全計算可能関数が存在する場合のみです。したがって、各iに対して、tが増加すると の値は最終的に一定になり に等しくなります。計算可能実数の場合と同様に、極限計算可能実数の 2 つの表現間を効果的に移動することはできません。 ${\displaystyle \omega}$${\displaystyle \phi (t,i)}$${\displaystyle \{0,1\}}$${\displaystyle \lim _{t\rightarrow \infty }\phi (t,i)}$${\displaystyle \omega (i)}$${\displaystyle \phi (t,i)}$${\displaystyle \omega (i)}$

• 2 進展開が停止問題をエンコードする実数は、極限では計算可能ですが、計算可能ではありません。
• 二進展開が一階算術の真理値集合をエンコードする実数は、極限では計算できません。
• チャイティン定数。

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

与えられた許容順序数に対して、算術階層を定義します。 ${\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. Soare .再帰的に列挙可能な集合と次数. Springer-Verlag 1987.
3. V. Brattka.チューリングジャンプと限界の間のガロア接続。Log . Methods Comput. Sci.、2018、doi :10.23638/LMCS-14(3:13)2018。