[FOM] Rogers's generalized machines
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?
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the FOM