Système acceptable de programmation

En informatique, et en particulier en théorie de la calculabilité, un système de programmation est une numérotation de Gödel de l'ensemble ${\mathcal {T}}$ des fonctions de $\mathbb {N}$ dans $\mathbb {N}$ Turing-calculables.

Un système de programmation $\varphi _{1},\varphi _{2},\varphi _{3},\dots$ est dit universel s'il admet une fonction (partielle) Turing-calculable $\varphi _{univ}$ dite fonction universelle telle que $\forall \,i\forall \,n\ \varphi _{univ}(\langle i,n\rangle )=\varphi _{i}(n)$ où $(x,y)\mapsto \langle x,y\rangle$ est la bijection classique de $\mathbb {N} ^{2}$ dans $\mathbb {N}$. Cette fonction est universelle au sens où elle peut simuler n'importe quelle fonction du système de programmation.

Un système acceptable de programmation est un système de programmation universel admettant une fonction totale dite de composition $c:\mathbb {N} ^{2}\to \mathbb {N}$ telle que pour tous i et j, $\varphi _{c(\langle i,j\rangle )}=\varphi _{j}\circ \varphi _{i}$. De façon équivalente, on peut demander au système de programmation d'être universel et de satisfaire le théorème s-n-m.

D'après le théorème d'équivalence de Roger, tous les systèmes acceptables de programmation sont équivalents, c'est-à-dire que si $\varphi _{1},\varphi _{2},\varphi _{3},\dots$ et $\psi _{1},\psi _{2},\psi _{3},\dots$ sont deux systèmes acceptables de programmation, alors il existe une fonction totale f Turing-calculable telle que pour tout n, $\varphi _{n}=\psi _{f(n)}$.

Bibliographie

• (en) M. Machtey and P. Young, An Introduction to the General Theory of Algorithms, North-Holland, 1978.
• (en) H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability, deuxième édition 1987, MIT Press. (ISBN 0-262-68052-1) (paperback), (ISBN 0-07-053522-1).