極限計算可能関数
関数 r ( x ) {\displaystyle r(x)} が極限計算可能であるとは、計算可能全域関数 r ^ ( x , s ) {\displaystyle {\hat {r}}(x,s)} が存在して
r ( x ) = lim s → ∞ r ^ ( x , s ) {\displaystyle r(x)=\lim _{s\to \infty }{\hat {r}}(x,s)}
が成り立つことをいう。
関数 r ( x ) {\displaystyle r(x)} が D-極限計算可能であるとは、D-計算可能全域関数 r ^ ( x , s ) {\displaystyle {\hat {r}}(x,s)} が存在して
r ( x ) = lim s → ∞ r ^ ( x , s ) {\displaystyle r(x)=\lim _{s\to \infty }{\hat {r}}(x,s)}
が同様に成り立つことをいう。
コード化可能な集合が極限計算可能とはその特性関数が極限計算可能であることをいう。これに対して、集合が計算可能であることと、ある関数 φ ( x , s ) {\displaystyle \varphi (x,s)} によって極限計算可能であり、かつ φ ( x , s ) {\displaystyle \varphi (x,s)} の値が安定する s {\displaystyle s} の値が x {\displaystyle x} に対して計算可能であることとは同値である。