In the theory of computation in computer science, a programming system is a G del numbering of the set \mathcal{T} of all Turing-computable functions from \mathbb{N} to \mathbb{N}. The name derives from the numbering of \mathcal{T} induced by a numbering of the programs of a Turing-complete programming language.

A programming system \phi_1, \phi_2, \phi_3, \dots is said to be universal if its (partial) universal function, u: \mathbb{N}^2 \rightharpoonup \mathbb{N}: \forall n, x \in \mathbb{N}, u(n,x) = \phi_n(x), is Turing-computable.

An acceptable programming system (also called an admissible G del numbering of \mathcal{T}), is a programming system that is universal and has a total Turing-computable composition function c: \mathbb{N}^2 \to \mathbb{N}: \forall i,j \in \mathbb{N}, \phi_{c(i,j)} = \phi_i \circ \phi_j . Equivalently, an acceptable programming system is a programming system that is universal and satisfies the s-m-n theorem.

As a consequence of Rogers' equivalence theorem, all acceptable programming systems are equivalent, in the sense that if \phi_1, \phi_2, \phi_3, \dots and \psi_1, \psi_2, \psi_3, \dots are acceptable programming systems, then there exists a total Turing-computable function f such that \forall n, \psi_n = \phi_{f(n)}.

References

• M. Machtey and P. Young, An introduction to the general theory of algorithms, North-Holland, 1978.
• 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

fr:Syst me acceptable de programmation