Abstract:
We consider generalized computations on Turing machines with a special oracle $F$ and introduce two analogs of $\alpha$-recursion on $F$-computable ordinals. The first analog is defined through an appropriate formal system $L(F)$; the second one is defined using $F$-computable mappings on the codes of ordinals. We prove that these approaches define the same class of functions and correspond to the $\alpha$-recursion relativized to the function $F$. We introduce an analog of the in-projectible ordinal and consider its relation to the decidability problem for bounded enumerable set.
Fulltext:
PDF file (1163 kB)
