Turing-complet
- Turing-complet
-
L'adjectif Turing-complet[1] s'applique en informatique et en logique à un système formel ou formalisable ayant la force de calcul des machines de Turing, c'est-à-dire un système dans lequel on peut coder les machines de Turing. Si de plus, ce système peut être codé par celui des machines de Turing, on dit qu'il est équivalent aux machines de Turing.
Ainsi un langage informatique est dit Turing-complet et nommé langage de programmation[2],[3], s'il permet de représenter toutes les fonctions calculables au sens de Turing et Church (nonobstant la finitude de la mémoire des ordinateurs). Tous les langages usuels de programmation (C, C++, Java, ...) sont Turing-complets. En revanche, ce n'est pas le cas pour certains langages dédiés au traitement de problèmes spécifiques, comme le langage SQL qui n'est devenu complet qu'à partir de 1999 quand il a été possible d'écrire des requêtes récursives. Le langage TeX, dédié à la composition de documents, est également Turing-complet.
Voir aussi
Note
- ↑ En toute rigueur on devrait dire complet au sens de Turing, mais c'est la traduction littérale (et le calque syntaxique aussi) de l'expression anglo-saxonne Turing complete qui a prévalu.
- ↑ (en) John C. Mitchell ,Concepts in programming languages, Cambridge University Press, 2003, p.14 [1] «The fact that all standard programming languages express precisely the class of partial recursive functions is often summarized by the statement that all programming languages are Turing complete.»
- ↑ (en)Bruce J.MacLennan, Principles of Programming Languages, Introduction : What is a programming language?, Oxford University Press, 1999. «A programming language is a language that is intended for the expression of computer programs and that is capable of expressing any computer program. This is not a vague notion. There is a precice theorical way of determining whether a computer language can be used to express any program, namely, by showing that is equivalent to a universal Turing machine.»
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Turing-complet de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Turing — (homonymie) Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Alan Mathison Turing était un mathématicien et informaticien anglais, considéré comme l « inventeur » de l ordinateur. Son nom est… … Wikipédia en Français
Turing (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Alan Mathison Turing était un mathématicien et informaticien anglais, considéré comme l « inventeur » de l ordinateur. Son nom est fréquemment… … Wikipédia en Français
Turing-équivalent — Désigne un système strictement Turing complet, c est à dire, pouvant calculer exactement le même ensemble de fonctions que les machines de Turing (les fonctions calculables), sans plus. Un système non Turing equivalent ne semble pas pouvoir… … 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
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
IA-Complet — L expression IA complet, formée par allusion plaisante à NP complet et Turing complet, désigne un problème dont on suppose que la résolution complète est en fait équivalent à la création d une véritable intelligence artificielle (il ne s agit pas … Wikipédia en Français
Ia-complet — L expression IA complet, formée par allusion plaisante à NP complet et Turing complet, désigne un problème dont on suppose que la résolution complète est en fait équivalent à la création d une véritable intelligence artificielle (il ne s agit pas … Wikipédia en Français
IA-complet — L expression IA complet, formée par allusion plaisante à NP complet et Turing complet, désigne un problème dont on suppose que la résolution complète est en fait équivalente à la création d une véritable intelligence artificielle (il ne s agit… … Wikipédia en Français
NP-Complet — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation … Wikipédia en Français
Pour les articles homonymes, voir Turing (homonymie).
