Système acceptable de programmation

Un article de Wikipédia, l'encyclopédie libre.

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)}.

[modifier] 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, second edition 1987, MIT Press. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
Autres langues