Rogers' Equivalence Theorem - Definition

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 η.