[35] If P is the class of all partial computable functions (for convenience restricted to one variable), then any map from N (the natural

[35] If P is the class of all partial computable functions (for convenience restricted to one variable), then any map π from N (the natural numbers) onto P is called a numbering. The standard indexing of the Turing machines provides such a numbering, say π0, and the indexing of the computable function definitions provides another, say

π1. A numbering π is acceptable, or a G¨odel numbering, if we can go back and forth effectively between π and π0, that is:

(i) There is a computable function f (not necessarily one-to-one) such that fπ0 = π.

(ii) There is a computable function g (not necessarily one-to-one) such that gπ = π0.

(a) Show that π1 is acceptable.

(b) Show that (i) is a necessary and sufficient condition that any π have a universal partial computable function (satisfies an appropriate version of the enumeration theorem).

(c) Show that (ii) is a necessary and sufficient condition that any π have an appropriate version of the s-m-n theorem (Exercise 1.7.5).

(d) Show that (ii) implies that π−1(φ) is infinite for every partial computable φ of one variable.

(e) Show that we can replace (i) and (ii) by the requirement that there be a computable isomorphism between π and π0.
Comments. These results, due to H. Rogers, Jr., in 1958, give an abstract formulation of the basic work of Church, Kleene, Post, Turing, Markov, and others, that their basic formalizations of the notion of partial computable functions are effectively isomorphic. It gives invariant significance to the notion of acceptable numbering in that major properties such as the enumeration theorem and the s-m-n theorem hold for every acceptable numbering. Note that (i) may be viewed as requiring that the numbering be ‘algorithmic’ in that each number yields an algorithm; and (ii) that the numbering be ‘complete’ in that it includes all algorithms. Source: [H. Rogers, Jr., Ibid.].