[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