In the theory of computation
in computer science
, a programming system
is a Gödel numbering
of the set
of all Turing-computable functions
. The name derives from the numbering
induced by a numbering of the programs of a Turing-complete
A programming system
is said to be universal
if its (partial) universal function
, is Turing-computable.
An acceptable programming system
(also called an admissible Gödel numbering
), is a programming system that is universal and has a total Turing-computable composition function
. 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 and are acceptable programming systems, then there exists a total Turing-computable function f such that .
- 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