Definitions

# Acceptable programming system

In the theory of computation in computer science, a programming system is a Gödel numbering of the set $mathcal\left\{T\right\}$ of all Turing-computable functions from $mathbb\left\{N\right\}$ to $mathbb\left\{N\right\}$. The name derives from the numbering of $mathcal\left\{T\right\}$ 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\left\{N\right\}^2 rightharpoonup mathbb\left\{N\right\}: forall n, x in mathbb\left\{N\right\}, u\left(n,x\right) = phi_n\left(x\right)$, is Turing-computable. An acceptable programming system (also called an admissible Gödel numbering of $mathcal\left\{T\right\}$), is a programming system that is universal and has a total Turing-computable composition function $c: mathbb\left\{N\right\}^2 to mathbb\left\{N\right\}: forall i,j in mathbb\left\{N\right\}, phi_\left\{c\left(i,j\right)\right\} = 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_\left\{f\left(n\right)\right\}$.

## 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

Search another word or see are acceptableon Dictionary | Thesaurus |Spanish