[FOM] Rogers's generalized machines

Robert Lubarsky Lubarsky.Robert at comcast.net
Mon Jun 1 07:24:30 EDT 2015

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 diverges. The exceptional power of doing so is that it may ask
not  just about a 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 name "generalized machines," with the result stated above. The
text includes neither proofs nor references. Does anybody know whether and,
if so, where this material appeared before?


Bob Lubarsky

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20150601/b27f8a41/attachment.html>

More information about the FOM mailing list