Turing-complet

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Turing.

En informatique ou en logique, un système Turing-complet[1] est un système formel ayant une puissance de calcul au moins équivalente à celle des machine de Turing. Dans un tel système, il est possible de programmer n'importe quelle machine de Turing, mais également tout ce que l'on peut programmer dans une machine 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) par certains auteurs, mais d'autres définitions de langage de programmation peuvent être choisies[4]. Tous les langages usuels de programmation (C, Java, Python ...) 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[5].

Un langage Turing Complet hérite des caractéristiques d'une machine de Turing, par exemple le Problème de l'arrêt est indécidable, donc il est impossible de montrer automatiquement pour un programme écrit dans le langage qu'il se termine systématiquement. Il existe cependant des langages qui ne sont pas Turing-Complet mais qui sont en pratique capable de calculer tout ce qui est intéressant comme le langage de l'assistant de preuve coq [6],[7]. Dans des langages de ce type, seuls les programmes qui terminent nécessairement peuvent être compilé. La compilation peut cependant devenir longue ou nécessiter un apport du programmeur pour accélérer le processus et apporter certaines démonstrations.

Voir aussi[modifier | modifier le code]

Références[modifier | modifier le code]

  1. 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.
  2. (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.»
  3. (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.»
  4. « Are non Turing-complete languages considered programming languages at all? », sur http://programmers.stackexchange.com
    exemple de la question posée sur un forum de question/réponse sur l’informatique populaire, une réponse sélectionnée considère que la Turing Complétude n’est pas requise pour considérer un langage comme langage de programmation
  5. Latex is more powerfull than you think, Post du blog ScribTex avec démonstrations, preuves et sources complémentaires
  6. « On the importance of Turing completeness », sur Lambda the Ultimate (Wikidata / Reasonator)
  7. Benjamin Werner, « Sets in Types, Types in Sets », Proceedings of TACS'97,‎ 1997