[FOM] Rogers's generalized machines

[Stephen G. Simpson]

Dear Bob,

Your result with Nate and Cameron, and the results mentioned by Rogers on
pages 406-407, are somewhat similar to a result in one of Kleene's papers
on recursion in higher types.  The result is as follows: A subset of $N$ is
hyperarithmetical if and only if it is recursive relative to $E$ where
$E:N^N\to N$ (pardon my LaTeX notation) is the type 2 functional given by
$E(f)=1$ if $\exists n\,(f(n)=1)$, otherwise $E(f)=0$, for all $f\in N^N$.
Alternatively, we can take $E$ to be the Turing jump operator.

By the way, Kleene's notation for $E$ is either $E_2$ or $E^2$ or $_2E$ or
$^2E$, but I forget which!

A good reference for this is the book "Higher Recursion Theory" by Gerald
E. Sacks.  My copy of Sacks's book isn't handy right now, but later this
week I will be able to give you a more precise reference.

-- Steve

Name: Stephen G. Simpson
Email: simpson at math.psu.edu
Affiliation: Pennsylvania State University
Research area: foundations of mathematics

Robert Lubarsky writes:
 > Date: Mon, 1 Jun 2015 07:24:30 -0400
 >
 >    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
 >
 > ----------------------------------------------------------------------
 > _______________________________________________
 > FOM mailing list
 > FOM at cs.nyu.edu
 > http://www.cs.nyu.edu/mailman/listinfo/fom
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20150602/5b00cc02/attachment.html>