[FOM] Rogers's generalized machines

[Yiannis N. Moschovakis]

This result is due to Kleene, a corollary of some of his basic
work in recursion in higher types. I am appending the reference to
the first (and most fundamental) paper on the topic which includes
the result that "HYP = recursive in the existential quantifier
over the natural numbers", and the references to the MR reviews of
two later papers in which he introduces "Turing computability in
higher types" and proves its equivalence with "general recursion
in higher types". (E-recursion came later.)

S. C.  Kleene, Recursive functionals and quantifiers of finite
types I, TAMS (1959), pp. 1 - 52.

MR0186542 (32 #4001), Kleene, S. C. Turing-machine computable
functionals of finite types. I.

MR0186543 (32 #4002) Kleene, S. C. Turing-machine computable
functionals of finite types. II.


On Mon, Jun 1, 2015 at 3:35 PM, WILLIAM TAIT <williamtait at mac.com> wrote:

> 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
>
> _______________________________________________
> 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/f63606af/attachment.html>