[FOM] Rogers's generalized machines
WILLIAM TAIT
williamtait at mac.com
Mon Jun 1 18:35:23 EDT 2015
I think that you are describing E-recursion on omega, which is a special case of E-recursion on an admissible ordinal. Maybe Sacks' *Higher Recursion Theory* contains information about the general theory and the case of the least admissible ordinal.
It could be, too, that Sacks discusses the subject in terms E-recursion on admissible sets rather than admissible ordinals; I can’t remember. Anyway, the earlier literature is bound to be mentioned there.
Best, Bill
> On Jun 1, 2015, at 6:24 AM, Robert Lubarsky <Lubarsky.Robert at comcast.net> wrote:
>
> Ackerman, Freer and I recently developed a theory of Turing machines augmented with the capability to ask (an oracle, say) whether a machine converges or regular Turing machine but rather about a machine that itself may make such inquiries. We showed among other things that the computations so induced are exactly the hyperarithmetic computations.
>
> Last week I happened to be looking through Hartley Rogers’s classic “Theory of Recursive Functions …”, and saw on p. 406-7 much the same definition under the neither proofs nor references. Does anybody know whether and, if so, where this material appeared before?
>
> Bob Lubarsky
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
More information about the FOM
mailing list