Background: I'm trying to get an intuitive understanding of α-recursion and related concepts in higher recursion theory. Once nice book is Peter Hinman's Recursion-Theoretic Hierarchies, available here (open access), and specifically chapter VIII which is intuitively appealing because he presents recursion on ordinals by directly constructing recursive functions rather than going through the constructible hierarchy. However, this also suggests a number of questions which he does not fully answer, and I'm hoping someone can help me get a clearer picture.
Let me make the following definitions, which I state informally but should be straightforward to formalize:
A primitive $(\infty,0)$-machine is given by a program in a programming language, all of whose variables are ordinals, which can do the following:
Basic operations (assigning variables to other variables or to any natural number, comparing ordinals, computing the successor, predecessor, sum and product, and constructing/deconstructing finite tuples of ordinals as ordinals using the standard bijection between $\mathit{Ord}^2$ and $\mathit{Ord}$; part of this is probably redundant).
Looping over an ordinal $\alpha$ which has been computed in advance (i.e., in a variable): by this I mean that a subprogram will be iterated for all ordinals $\beta<\alpha$; to define the value of a variable at limit times $\beta$, we declare it to be the lim sup of variables up to this point. These loops always terminate. (Of course, it doesn't hurt to allow the program to interrupt the loop early.)
Recursive function calls are not allowed (all subroutines must be defined prior to where they are used). Because of this, a primitive $(\infty,0)$-machine always terminates, whatever its inputs.
Comment: Unless I got my definition horribly wrong, a primitive $(\infty,0)$-machine, when given natural numbers as input, can only produce a natural number as output, and the functions $\omega^r \to \omega$ thus defined are exactly the primitive recursive functions as usually defined.
- A general $(\infty,0)$-machine is similar to a primitive $(\infty,0)$-machine, except that recursive function calls are allowed: unless I am mistaken, this is equivalent to allowing a "universal" machine (i.e., a general $(\infty,0)$-machine can compute the value returned by another general $(\infty,0)$-machine on any specified input). Programs can now fail to terminate (and the precise (program,input)↦output partial function is defined as the smallest which satisfies the requirements).
This definition is supposed to coincide with what Hinman's aforementioned book calls a "$(\infty,0)$-partial recursive function" (with or without parameters as are passed to the machine): see p. 377. If it does not coincide, I must have made a mistake. The difference between "general" and "primitive" is supposed to be clause (2) in definition 1.1 on p. 376 of Hinman's book.
Comment: Again, when given natural numbers as input, a general $(\infty,0)$-machine can only produce natural numbers as output (or fail to terminate), and the partial functions $\omega^r \to \omega$ thus defined are exactly the usually defined general recursive (partial) functions.
Lastly, if $\lambda$ is any ordinal (fixed in advance), a primitive $(\infty,\lambda)$-machine and a general $(\infty,\lambda)$-machine are the same as a primitive $(\infty,0)$-machine and a general $(\infty,0)$-machine respectively, but with an additional construct:
- We can also loop over all ordinals $\beta<\lambda$; the difference with the previously defined type of loop (apart from the fact that here $\lambda$ is fixed in advanced rather than computed from the input) is that if the program does not interrupt the loop early (i.e., issue a
breakat some time $\beta<\lambda$), it does not terminate.
- We can also loop over all ordinals $\beta<\lambda$; the difference with the previously defined type of loop (apart from the fact that here $\lambda$ is fixed in advanced rather than computed from the input) is that if the program does not interrupt the loop early (i.e., issue a
Again, general $(\infty,\lambda)$-machines are supposed to define the same thing as Hinman's "$(\infty,\lambda)$-partial recursive function".
Note: If $\kappa$ is recursively regular (=admissible), then the total functions computed by general $(\infty,\kappa)$-machines on inputs $<\kappa$, and possibly using extra parameters (=constants) $<\kappa$, are exactly the $\kappa$-recursive total functions $\kappa^r \to \kappa$ (viz., those which are $\Delta^1_1$-definable over $L_\kappa$). I believe that primitive $(\infty,\kappa)$-machines also compute the same functions in this context (because recursivity can be simulated by a loop over ordinals $<\kappa$), but that's not really important.
Now basically what I'd like to understand is what can be computed by a general $(\infty,0)$-machine (=general 0-machine), or even a primitive $(\infty,0)$-machine, if it is allowed a given ordinal $\alpha$ as input. So here is my
MAIN QUESTION: Let $\alpha$ be an ordinal, and let $\kappa$ be the smallest recursively regular (=admissible) ordinal $>\alpha$. Is it true that any total function $\kappa^r \to \kappa$ which can be computed using a general $(\infty,\kappa)$-machine without extra parameters (=constants) can, in fact, be computed using a general $(\infty,0)$-machine from the only parameter $\alpha$?
This question is motivated by the fact that if given the parameter $\omega$, a general $(\infty,0)$-machine can clearly compute all hyperarithmetic functions $\omega^r \to \omega$, it can compute any ordinal $<\omega_1^{CK}$, and it seems as though it can compute the same things as a general $(\infty,\omega_1^{CK})$-machine.
A positive answer to this question would imply, among other things, that the ordinals stable under general $(\infty,0)$-recursive functions are exactly the recursively regular ordinals and limits thereof.
BONUS QUESTION: With the same notations, is it true for $\gamma<\kappa$ that any total function $\gamma^r \to \gamma$ which can be computed using a general $(\infty,\kappa)$-machine without extra parameters (=constants) can, in fact, be computed using a primitive $(\infty,0)$-machine from the only parameter $\alpha$?
More generally, I'm interested in any statements along the same lines that can help clear the relation between these various notions of ordinal machines.