Admissible numbering

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 ψ0, ψ1, ... is an enumeration of all partial computable functions.

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 sense if and only if: The proof is as follows: 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, ηe = ψp(e) (Soare 1987:25).