Acceptable programming system

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\; ightharpoonup\; 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\; o\; 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