Recursion versus tail recursion over (F)over-bar(p)

摘要

We characterize the intrinsically recursive functions over the algebraic closure of a finite field in terms of Turing machine complexity classes and derive some structural properties about the family of such functions. In particular, we show that the domain of convergence of any partial recursive function is again recursive, and, under complexity theoretic hypotheses, that the class of tail recursive functions is strictly smaller than the class of recursive functions (cf. Theorems 5.4, 5.2, and Section 8).