Turing-complet
Pour les articles homonymes, voir Turing.En informatique ou en logique, un système Turing-complet[note 1] est un système formel ayant une puissance de calcul au moins équivalente à celle des machines de Turing.
Grâce à la thèse de Church, cela signifie qu'un système Turing-complet a la puissance de n'importe quel autre système qui a la même puissance que les machines de Turing, à savoir les fonctions récursives, le lambda calcul, les machines à compteurs, etc.
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 des machines de Turing, on dit qu'il est équivalent aux machines de Turing. La complétude au sens de Turing est intimement liée à la thèse de Church qu'elle justifie en y ajoutant de plus en plus de systèmes équivalents en puissance de calcul.
Sommaire
1 Langages de programmation Turing-complets
2 Langages qui ne sont pas Turing-complets
3 Exemples en dehors des langages de programmation
4 Articles connexes
5 Notes et références
5.1 Notes
5.2 Références
6 Annexes
6.1 Articles connexes
Langages de programmation Turing-complets |
De même qu'un modèle de calcul, un langage informatique est dit Turing-complet 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).
Certains auteurs prennent cette propriété pour définition d’un langage de programmation[1],[2], mais d'autres définitions peuvent être choisies[3].
Les langages de programmation usuels (C, Java…) sont Turing-complets. Le langage C++, est évidemment Turing-complet, mais le sous ensemble permettant la programmation générique (templates), l'est aussi.
Le langage SQL à l'origine non complet au sens de Turing, l'est devenu avec la norme SQL:1999 en permettant d'écrire des requêtes récursives.
Le langage TeX, destiné à la composition de documents, est également Turing-complet[4].
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 d'écrire un programme qui dit si un programme arbitraire qu'on lui fournit se termine ou non.
Langages qui ne sont pas Turing-complets |
Certains langages dédiés au traitement de problèmes spécifiques ne sont pas Turing-complets. Système F, un formalisme de lambda calcul en est un exemple. Par ailleurs — par conception —, les langages totaux (en), où tous les calculs se terminent nécessairement (comme le langage Gallina de l'assistant de preuve Coq), ne sont pas non plus Turing-complets. Cependant, ces derniers sont en pratique capables de calculer tout ce qui est intéressant[5],[6], en d'autres termes ils peuvent mettre en œuvre toutes les fonctions dont nous pourrions avoir besoin dans la vie pratique ; les calculs qui leur échappent, soit ont une complexité au delà de l'imaginable et du réalisable, soit ne se terminent pas. La compilation doit alors démontrer la terminaison des programmes, ou nécessiter une interaction avec le programmeur pour certaines démonstrations, mais c'est le prix à payer pour une qualité de code qui est correct par construction.
Exemples en dehors des langages de programmation |
Certains jeux et logiciels sont Turing-complets par accident[note 2] :
Dwarf Fortress[7].- Le jeu de la vie, un automate cellulaire[8].
Little Big Planet[7].
Magic : L'Assemblée[7].
Minecraft[7].
Articles connexes |
- Boucle infinie
- Théorème de Rice
- Théorie de la Calculabilité
- Thèse de Church
Notes et références |
Notes |
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.
Sans que leurs auteurs l'aient souhaité ou envisagé.
Références |
(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 precise theorical way of determining whether a computer language can be used to express any program, namely, by showing that it is equivalent to a universal Turing machine. »
« Are non Turing-complete languages considered programming languages at all? », sur http://programmers.stackexchange.comExemple 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.
« LaTeX is More Powerful than you Think - Computing the Fibonacci Numbers and Turing Completeness - ShareLaTeX, Éditeur LaTeX en ligne », sur fr.sharelatex.com (consulté le 2 juin 2017)
« On the importance of Turing completeness », sur Lambda the Ultimate (en).
Benjamin Werner, « Sets in Types, Types in Sets », Proceedings of TACS'97, 1997.
Andrew Cedotal, « Man Uses World's Most Difficult Computer Game to Create … A Working Turing Machine » [archive du 27 juin 2015], sur The Mary Sue, 16 avril 2010(consulté le 2 juin 2015)
Paul Rendell, « A Turing Machine in Conway's Game of Life » [archive du 8 juillet 2009], sur Rendell-Attic, 12 janvier 2005(consulté le 22 juin 2009)
Annexes |
Articles connexes |
- Alan Turing
- Thèse de Church
Portail de l'informatique théorique 
Portail de la logique
