Admissible numbering

In computability theory, admissible numberings are enumerations (numberings) of the set of partial computable functions that can be converted to and from the standard numbering. These numberings are also called acceptable numberings and acceptable programming systems.

Rogers' equivalence theorem shows that all acceptable programming systems are equivalent to each other in the formal sense of numbering theory.

Definition

The formalization of computability theory by Kleene led to a particular universal partial computable function Ψ(e, x) defined using the T predicate. This function is universal in the sense that it is partial computable, and for any partial computable function f there is an e such that, for all x, 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 ψ₀, ψ₁, ... is an enumeration of all partial computable functions. Such enumerations are formally called computable numberings of the partial computable functions.

An arbitrary numbering η of partial functions is defined to be an admissible numbering if:

• The function H(e,x) = η_e(x) is a partial computable function.
• There is a total computable function f such that, for all e, η_e = ψ_f(e).
• There is a total computable function g such that, for all e, ψ_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 η.

Rogers' equivalence theorem

Hartley Rogers, Jr. showed that a numbering η of the partial computable functions is admissible if and only if there is a total computable bijection p such that, for all η_e = ψ_p(e) (Soare 1987:25).

See also

• Friedberg numbering

References

• Y.L. Ershov (1999), "Theory of numberings", Handbook of Computability Theory, E.R. Griffor (ed.), Elsevier, pp. 473–506. ISBN 978-0-444-89882-1
• M. Machtey and P. Young (1978), An introduction to the general theory of algorithms, North-Holland, 1978. ISBN 0-444-00226-X
• H. Rogers, Jr. (1967), The Theory of Recursive Functions and Effective Computability, second edition 1987, MIT Press. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
• R. Soare (1987), Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag. ISBN 3-540-15299-7