# [FOM] Rogers's generalized machines

Stephen G. Simpson sgslogic at gmail.com
Tue Jun 2 15:33:29 EDT 2015

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>