Système de programmation acceptable

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 \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, second edition 1987, MIT Press. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
Ce document provient de « Syst%C3%A8me acceptable de programmation ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Système de programmation acceptable 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 — [ 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

  • 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 est dit universel s il admet une… …   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

  • CONTRÔLE SOCIAL — La notion de contrôle social touche à quelques uns des problèmes essentiels de l’analyse sociologique, mais elle est particulièrement malaisée à définir. Dans son usage actuel, elle nous vient de la sociologie américaine. Aussi est elle associée… …   Encyclopédie Universelle

  • 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

  • DÉCISION — La réflexion moderne sur la question de savoir quel parti prendre lorsqu’on se trouve confronté à un choix difficile a été esquissée pour la première fois par Blaise Pascal, au XVIIe siècle, dans le fameux texte du «pari» sur l’entrée dans la… …   Encyclopédie Universelle

  • AUTOMATIQUE — Automation, automatique, automatisation, automatismes, théorie des automates, cybernétique..., la variété même des vocables utilisés traduit la difficulté de définir précisément le contenu du substantif automatique . Nous choisirons ici d’appeler …   Encyclopédie Universelle

  • OFFRE ET DEMANDE — L’offre et la demande représentent probablement les concepts les plus vénérables et les plus fondamentaux de la théorie économique. En effet, l’activité économique se résout essentiellement en une série de transactions effectuées par les agents… …   Encyclopédie Universelle

  • Java Framework de persistence — Persistance (informatique) Pour les articles homonymes, voir persistance. En programmation, la gestion de persistance des données (en anglais : persistence) et éventuellement des états de programme se réfère au mécanisme responsable de la… …   Wikipédia en Français

Share the article and excerpts

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