Système acceptable de programmation

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 des fonctions de dans Turing-calculables.

Un système de programmation est dit universel s'il admet une fonction (partielle) Turing-calculable dite fonction universelle telle que est la bijection classique de dans . 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 telle que pour tous i et j, . 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 et sont deux systèmes acceptables de programmation, alors il existe une fonction totale f Turing-calculable telle que pour tout n, .

Bibliographie[modifier | modifier le code]

  • (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.