En informatique et en logique, un système formel est dit complet au sens de Turing ou Turing-complet (par calque de l’anglais ) s’il possède un pouvoir expressif au moins équivalent à celui des machines de Turing. Dans un tel système, il est donc possible de programmer n'importe quelle machine de Turing.

Cette notion est rendue pertinente par la thèse de Church, qui postule l’existence d’une notion naturelle de calculabilité. Ainsi, le pouvoir expressif des machines de Turing coïncide avec celui des fonctions récursives, du lambda calcul, ou encore des machines à compteurs.

Bien que certains modèles de calcul, appelés des hypercalculs, soient strictement plus expressifs que les machines de Turing, ces modèles sont des objets de spéculation (requérant par exemple d’effectuer une infinité d’opérations, ou de calculer sur l’ensemble des nombres réels) et l’on ignore s’ils sont physiquement réalisables.

Dans ces conditions, la thèse de Church conjecture l’universalité du modèle de calcul des machines de Turing : tout système Turing-complet serait en fait équivalent aux machines de Turing.

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 ordinateursUn ordinateur a une mémoire finie, le modèle de calcul des machines de Turing a une mémoire illimitée.).

Certains auteurs prennent cette propriété pour définition d’un langage de programmation : : , mais d'autres définitions peuvent être choisies ..

Les langages de programmation usuels (C, Java…) sont Turing-complets car ils possèdent tous les ingrédients nécessaires à la simulation d'une machine de Turing universelle (compter, comparer, lire, écrire, etc.)Exemple de mise en œuvre d'une machine de Turing en C : .. Le langage C++ est également Turing-complet, et 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 lui permettant d'écrire des requêtes récursives.

Le langage LaTeX (issu du TeX), destiné à la composition de documents, est également Turing-complet..

Le langage HTML seul n'est pas Turing-complet, cependant il a été prouvé que le langage CSS (en version 3) permet de construire l'automate cellulaire élémentaire de code 110 (voir .), connu pour être universel au sens de Turing. Ces deux langages étant souvent indissociables, on peut conclure que le HTML+CSS est Turing-complet.

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 , les , où tous les calculs se terminent nécessairement (comme le langage Gallina de l'assistant de preuve Rocq), ne sont pas non plus Turing-complets.

Cependant, ces derniers sont en pratique capables de calculer tout ce qui est intéressant.., 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 correcte par construction.

Exemples en dehors des langages de programmation Certains jeux et logiciels présentent une complétude de Turing de manière fortuite, sans que leurs concepteurs l'aient intentionnellement recherchée ou anticipée.

Dwarf Fortress. Magic : L'Assemblée. Cities: Skylines Démineur avec grille infinie PowerPoint. Habbo Baba Is You. Microsoft Excel Opus Magnum Dans certains cas, l'intégration d'une propriété de complétude de Turing est intentionnelle, en raison de la capacité à implémenter des portes logiques et à contrôler un circuit électrique, constituant ainsi une composante essentielle du jeu :

Minecraft. Factorio Le jeu de la vie, un automate cellulaire.

Minecraft a par exemple été utilisé pour reprogrammer une version jouable de Pokémon Rouge..

Articles connexes Boucle infinie Théorème de Rice Théorie de la calculabilité Thèse de Church

Notes et références Notes

Références

Annexes Articles connexes Alan Turing Thèse de Church

Catégorie:Langage de programmation Catégorie:Logique mathématique