Qu’est ce que’un langage Turing-Complet ?

En informatique, un système est dit Turing-Complet s’il possède un pouvoir au moins équivalent à celui des machines de Turing.

Dans un tel système, il faut savoir qu’il est donc possible de programmer n’importe quelle machine de Turing. Nous retrouvons également ce terme dans le domaine des cryptomonnaies, notamment avec la cryptomonnaie Ethereum.


Comprendre la machine de Turing

Alan Turing a créé une machine permettant de créer un programme, l’exécuter et afficher certains résultats. Mais il a ensuite dû créer différentes machines pour être en mesure de créer différents programmes. 

Pour simplifier le processus, il a alors créé une seule machine universelle qui peut exécuter n’importe quel programme.

 

Les langages de programmation sont similaires à ces machines car ils prennent des programmes et les exécutent. Désormais, un langage de programmation est appelé « Turing-complet » s’il peut exécuter des programmes quel que soit leur langage, et qu’une machine de Turing peut exécuter avec suffisamment de temps et de mémoire.

La plupart des langages de programmation modernes sont tous Complets, car ils implémentent toutes les fonctionnalités nécessaires à l’exécution de programmes tels que l’addition, la multiplication, la condition « if-else, » les moyens de stocker, récupérer des données etc.


Turing-Complet

Pour illustrer cela, supposons qu’un programme sélectionne 5 nombres et les additionne. La machine Turing peut facilement exécuter ce programme. 

Mais imaginez que pour une raison quelconque, votre langage de programmation ne puisse pas effectuer cette action. 

Cela signifie alors que le programme est « Turing Incomplet ». D’autre part, si elle peut exécuter n’importe quel programme pouvant être exécuté par la machine universelle, alors celui-ci sera Turing-Complet.


Exemples de langages Turing-Complet

Ethereum est construite avec un langage Turing-Complet, différent opérationnellement de Bitcoin

Les langages de programmation classiques tels que CJava, etc… sont Turing-Complet car ils possèdent tous les ingrédients nécessaires à la simulation d’une machine de Turing universelle (compter, comparer, lire, écrire, etc).

Le langage C++ est également Turing Complet.

Le langage SQL l’est devenu avec la norme SQL:1999 lui permettant d’écrire des requêtes récursives