The Standard Numbering φ of P(1)

In the previous chapters we have studied different kinds of machines, the computable functions and recursive and r.e. sets. The theorems we have proved are generally of a constructive nature themselves. We have shown e.g.: “for any f ∈ P(2), $$ \tilde \mu \left( f \right) \in {P^{\left( 1 \right)}}^{\prime \prime } $$” (Theorem 1.2.12), “for any stack machine there is a Turing machine computing the same function” (Theorem 1.6.7), “for any r.e. A ⊆ ℕ there is some recursive B ⊆ ℕ2 such that A is the projection of B” (Theorem 1.8.4). The proofs of these and many other theorems, however, yield more information. We have for example shown: “there is an effective procedure which for any register machine M produces a register machine M′ such that $$ {f_{M'}} = \tilde \mu {\left( {{f_M}} \right)^{\prime \prime }}, $$, or “there is an effective procedure which for any register machine M produces a register machine M′ such that f_m, is a total function and dom(f_M) is the projection of f_M′-1{0}”. In order to formulate these observations precisely one can introduce standard names for register machines (or the corresponding computable functions) which are appropriate words. Then the effective procedures can be represented by computable functions on the names. Since computability on words can be reduced to computability on numbers (Theorem 1.7.5), we shall use numbers as names which yields a formally simpler theory.