Système acceptable de programmation

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 φ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, φn = ψ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, second edition 1987, MIT Press. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Système acceptable de programmation de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Systeme acceptable de programmation — 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 des fonctions de dans Turing calculables. Un système de programmation… …   Wikipédia en Français

  • Système de programmation acceptable — 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 des fonctions de dans Turing calculables. Un système de programmation… …   Wikipédia en Français

  • PROGRAMMATION — Un ordinateur est une machine universelle pour le traitement de l’information. Il doit pouvoir être utilisé aussi bien pour des calculs numériques que pour la gestion d’un stock de pièces détachées ou des travaux de secrétariat. Il est donc… …   Encyclopédie Universelle

  • système — [ sistɛm ] n. m. • 1552, repris v. 1650, répandu XIXe; gr. sustêma « assemblage, composition » I ♦ Ensemble organisé d éléments intellectuels. 1 ♦ Hist. Sc. Ensemble conçu par l esprit (à titre d hypothèse, de croyance) d objets de pensée unis… …   Encyclopédie Universelle

  • Machine De Turing — Pour les articles homonymes, voir Turing (homonymie). Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire, créé par Alan Turing en vue de donner une définition précise …   Wikipédia en Français

  • Machine de turing — Pour les articles homonymes, voir Turing (homonymie). Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire, créé par Alan Turing en vue de donner une définition précise …   Wikipédia en Français

  • SAP —  Pour l’article homophone, voir SAPE. Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.   Sigles d’une seule lettre    …   Wikipédia en Français

  • Sap —  Pour l’article homophone, voir SAPE. Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. {{{image}}}  …   Wikipédia en Français

  • Machine de Turing — Pour les articles homonymes, voir Turing (homonymie). Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire, créé par Alan Turing en vue de donner une définition précise …   Wikipédia en Français

  • Ramasse-miettes (informatique) — Pour les articles homonymes, voir Ramasse miettes (homonymie). Illustration d un ramasse miette compactant Un ramasse miettes, ou récupérateur de mémoire, ou glaneur de cellules (en anglais …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”