極限計算可能関数
これをエルショフの階層という。エルショフの階層はクリーネのO(英語版)を用いることによって構成的順序数へ一般化できる。このとき極限計算可能関数はある構成的順序数 α {\displaystyle \alpha } について α {\displaystyle \alpha } -近似可能となる。すなわち極限計算可能関数はエルショフの階層によって完全に分類される。
心変わりの回数がある計算可能関数で抑えられるとき、極限関数は ω {\displaystyle \omega } -近似可能という。このとき、集合 A {\displaystyle A} が ω {\displaystyle \omega } -近似可能であることと、 A {\displaystyle A} が 0 ′ {\displaystyle 0'} に真理表還元可能であることとは同値である。この事実は、先の極限補題の証明において、 ( x , n ) ∈ Y {\displaystyle (x,n)\in Y} なる神託問い合わせの n {\displaystyle n} が再帰的関数で抑えられることから分かる。
0 ′ {\displaystyle 0'} は帰納的可算集合であるから実効的に枚挙できる。したがって次のようにして 0 ′ {\displaystyle 0'} が極限計算可能であることが分かる:
r ^ ( x , s ) = { 1 if by stage s , x has been enumerated into 0 ′ 0 if not {\displaystyle \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}}}
明らかに r ^ ( x , s ) {\displaystyle {\hat {r}}(x,s)} の s → ∞ {\displaystyle s\to \infty } に於ける極限は 0 ′ {\displaystyle 0'} の特性関数である。極限計算可能関数のクラスは recursively closed である。すなわち関数合成、原始再帰、最小化によって閉じている。したがって任意の 0 ′ {\displaystyle 0'} -計算可能関数は極限計算可能である。
逆に X {\displaystyle X} を極限計算可能な集合とし、 X s {\displaystyle X_{s}} を X {\displaystyle X} に収束する一様に再帰的な集合列とする。