Incomputability theory,admissible numberings are enumerations (numberings) of the set ofpartial computable functions that can be convertedto and from the standard numbering. These numberings are also calledacceptable numberings andacceptable programming systems.
Rogers' equivalence theorem shows that all acceptable programming systems are equivalent to each other in the formal sense of numbering theory.
The formalization of computability theory byKleene led to a particular universal partial computable function Ψ(e,x) defined using theT predicate. This function is universal in the sense that it is partial computable, and for any partial computable functionf there is ane such that, for allx,f(x) = Ψ(e,x), where the equality means that either both sides are undefined or both are defined and are equal. It is common to write ψe(x) for Ψ(e,x); thus the sequence ψ0, ψ1, ... is an enumeration of all partial computable functions. Such enumerations are formally called computable numberings of the partial computable functions.
An arbitrary numberingη ofpartial functions is defined to be anadmissible numbering if:
The functionH(e,x) =ηe(x) is a partial computable function.
There is a total computable functionf such that, for alle,ηe = ψf(e).
There is a total computable functiong such that, for alle, ψe =ηg(e).
Here, the first bullet requires the numbering to be computable; the second requires that any index for the numberingη can be converted effectively to an index to the numbering ψ; and the third requires that any index for the numbering ψ can be effectively converted to an index for the numberingη.
The following equivalent characterization of admissibility has the advantage of being "internal toη", in that it makes no direct reference to a standard numbering (only indirectly through the definition of Turing universality). A numberingη of partial functions is admissible in the above senseif and only if:
The evaluation functionH(e,x) =ηe(x) is a partial computable function.
η is Turing universal: for all partial computable functionsf there is ane such thatηe=f (note that here we are not assuming a total computable function that transformsη-indices to ψ-indices).
The fact that admissible numberings in the above sense have all these properties follows from the fact that the standard numbering does, and Rogers's equivalence theorem.
In the other direction, supposeη has the properties in the equivalent characterization.
Since the evaluation functionH(e,x)=ηe(x) is partial computable, there existsv such that ψv=H. Thus, by theparameter theorem for the standard numbering, there is a total computable functiond such that ψd(v,e)(x)=H(e,x) for allx. The total functionf(e) =d(v,e) then satisfies the second part of the above definition.
Next, since the evaluation functionE(e,x)=ψe(x) for the standard numbering is partial computable, by the assumption of Turing universality there existsu such thatηu(e,x)=ψe(x) for alle,x.
Letc(x,e) be the computable currying function forη. Thenηc(u,e)=ψe for alle, sog(e) =c(u,e) satisfies the third part of the first definition above.
Hartley Rogers, Jr. showed that a numberingη of the partial computable functions is admissible if and only if there is a total computablebijectionp such that, for alle,ηe = ψp(e) (Soare 1987:25).
Y.L. Ershov (1999), "Theory of numberings",Handbook of Computability Theory, E.R. Griffor (ed.), Elsevier, pp. 473–506.ISBN978-0-444-89882-1
M. Machtey and P. Young (1978),An introduction to the general theory of algorithms, North-Holland, 1978.ISBN0-444-00226-X
H. Rogers, Jr. (1967),The Theory of Recursive Functions and Effective Computability, second edition 1987, MIT Press.ISBN0-262-68052-1 (paperback),ISBN0-07-053522-1
R. Soare (1987),Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag.ISBN3-540-15299-7
