[FOM] acceptable enumerations

[Samuel Moelius]

This email expands on Dr. Raatkinainen's email a bit.

Let N denote the set of natural numbers.  I assume that "p.r. function" 
means partial recursive function from N to N.  Thus, for this email, 
assume that each partial recursive function is from N to N, unless 
stated otherwise.

An _effective enumeration of the p.r. functions_ is a p.r. function psi 
from N x N to N such that, for each p.r. function alpha from N to N, 
there exists a p in N such that, for each x in N, psi(p,x) = alpha(x).

An _acceptable enumeration of the p.r. functions_ is an effective 
enumeration phi such that, for each effective enumeration psi, there 
exists a (total) computable function t from N to N such that, for each p 
and x, phi(t(p),x) = psi(p,x).

Thus, an effective enumeration phi is acceptable iff it is possible to 
algorithmically translate every effective enumeration psi into phi.

To relate this to Dr. Raatkinainen's email: usually, any coding regarded 
as "standard" is acceptable.  Thus, it is possible to algorithmically 
translate any effective enumeration of the p.r. functions into such a 
standard coding.  Furthermore, if a standard coding can be 
algorithmically translated into phi, then it follows that phi is acceptable.

As Dr. Raatkinainen notes, the Fixed-Point Theorem holds in any 
acceptable enumeration of the p.r. functions.  This is true regardless 
of whether one considers Kleene's original formulation of the theorem, 
or Rogers' variant.

Kleene's original formulation w.r.t. phi is: for each p.r. function 
alpha from N x N to N, there exists an e in N such that, for each x in 
N, phi(e,x) = alpha(e,x).

Rogers's variant w.r.t. phi is: for each (total) computable function t 
from N to N, there exists an e in N such that, for each x in N, 
phi(t(e),x) = phi(e,x).

An alternative definition of "effective enumeration of the p.r. 
functions" is the following.  Let <.,.> be any pairing function, i.e., a 
1-1, onto, computable function from N x N to N.  An _effective 
enumeration of the p.r. functions_ is a p.r. function psi from N to N 
such that, for each p.r. function alpha from N to N, there exists a p in 
N such that, for each x in N, psi(<p,x>) = alpha(x).  (Note the change 
in the type of psi.)  None of the above changes significantly when 
things are phrased in this way, and this is true regardless of the 
choice of pairing function.

Finally, an _acceptable enumeration of the r.e. sets_ is the domain of 
an acceptable enumeration of the p.r. functions.

I hope this is useful.

Best wishes,

Sam

On 12/25/2011 04:36 AM, Panu Raatikainen wrote:
> A system of indices is acceptable if it is possible to go effectively
> from the standard coding to the system, and vice versa.
>
> Rogers has shown that a system of indices is acceptable iff it satisfies
> both enumeration and parametrization, and that every acceptable system
> of indices satisfies the Fixed-Point Theorem.
>
> Hence, one can say that acceptable systems of indices provide the same
> structure theory for recursive functions as the standard one.
>
>
> Best
>
> Panu
>
>
>
> Lainaus T.Forster at dpmms.cam.ac.uk:
>
>> ... as in ``acceptable enumeration of p.r. functions'' or acceptable
>> enumeration of r.e. sets''...
>>
>> I am in the market for a decent and thorough explanation of this
>> important notion. I am away from my books and am nowhere near a
>> library, but i do have the internet. Can anyone point me towards an
>> electronically available
>> text of this nature? Or perhaps supply such an analysis themselves?
>>
>> tf
>>
>> _______________________________________________
>> FOM mailing list
>> FOM at cs.nyu.edu
>> http://www.cs.nyu.edu/mailman/listinfo/fom
>>
>>
>
>
>