[FOM] Rogers's generalized machines

[Oosten, J. van]

Dear Bob,

this is related to a recent paper of mine and Eric Faber, "Effective 
Operations of Type 2 in PCAs",
to appear in Computability (first version available on ArXiv: 
http://arxiv.org/abs/1408.4984v1 ).

We show that for every PCA A and for every functional F: A^A-->A, there 
is a universal solution to
the problem of constructing another PCA structure on A for which F is an 
effective operation. We show
that if we apply this construction to the PCA of indices of partial 
recursive functions (also called "K_1")
for the functional F which decides for f:N-->N whether or not f takes 
the value 0 somewhere, we
get a pca for which the total representable functions are exactly the 
hyperarithmetical ones.

On 6/1/15 1:24 PM, Robert Lubarsky 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 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/20150602/825a48a2/attachment.html>