Calendrier de l'avent n°14
Turing-complétude: finalement, tous les langages se valent ?
Existe-t-il un programme écrit en Java que l’on ne puisse pas traduire en C ou en OCaml ? Il y a-t-il un super langage qui est plus expressif que tous les autres ?
Ça ressemble un petit peu à une devinette, mais la question de l’expressivité s’est très rapidement posée aux premiers informaticiens.
Je ne fais pas durer le suspens plus longtemps, la réponse à toutes ces questions est: NON! Enfin, je vois vos sourcils froncés: laissez-moi nuancer.
Les langages auxquels nous sommes habitués (Java, C, python et j’en passe) sont tous Turing complets[1]. Mais qu’est-ce que ça veut dire ? Et bien tout simplement qu’ils sont aussi expressifs qu’une machine de Turing[2], le modèle théorique de nos ordinateurs (inventé par Alan Turing vers 1935).
Je ne vous fais pas la démonstration, mais on montre que tous les langages que j’ai cités permettent de simuler une machine de Turing, et réciproquement, qu’une machine de Turing peut les simuler ! Ils sont donc tous aussi expressifs: pour un programme écrit en Java, il existe un programme en C qui fait la même chose, et vice et versa. Pas mal non ?
Mais j’entends une question dans le fond de la salle : « et il n’existe pas des supers-machines-de-Turing, qui sont encore plus fortes ? ».
C’est là qu’intervient un certain Church. Il énonce la célèbre thèse de Church-Turing [3]: « toutes les fonctions calculables le sont par des machines de Turing ». Autrement dit, imaginez un procédé pour calculer une suite de nombre. Eh bien ce procédé est imitable par une machine de Turing. Bon, Church (et les autres) n’ont pas de preuve formelle (c’est une thèse, pas un théorème), mais passons.
On n’a tout simplement pas de modèles de calculs “plus forts” que nos machines de Turing… La physique quantique invalide un peu cette idée, mais je ne vais pas m’étendre sur le sujet ; le directeur de l’IRIF a donné un cours au collège de France à ce sujet l’année dernière, je vous invite à aller voir [4] !
Donc, pour résumer, d’une tous les langages usuels sont tous aussi expressifs, et de deux, rien ne les surpasse ! Bref, Java, C ou OCaml, c’est une histoire de goût :) Il existe même des trucs plus… étranges qui sont Turing Complet. Par exemple, Minecraft permet d’encoder une machine de Turing (si, si, la preuve est là [5]. Donc on peut écrire n’importe quel programme dans Minecraft).
Bon et pour finir, il existe bien sûr des langages qui ne sont pas Turing Complet. Imaginez un langage de programmation où tous les programmes terminent forcément un jour (sans boucle infinie donc). Eh bien un tel langage n’est pas Turing Complet : il ne permet pas de faire une boucle infinie, ce que peut faire Java, C ou une machine de Turing.
Je vous vois venir avec vos gros sabots. « Mais Alexandre, c’est nul un langage moins puissant… ». Eh bien détrompez-vous ! Il existe de tels langages, comme celui de l’assistant de preuve Coq[6]. C’est normal : si l’on ne peut pas faire de boucles infinies, on gagne des garanties très fortes sur les choses que l’on écrit, ce qui permet de faire des maths par exemple. Mais je garde cette histoire pour une prochaine fois…
Alexandre Moine
Sources : [1] : https://fr.wikipedia.org/wiki/Turing-complet [2] : https://fr.wikipedia.org/wiki/Machine_de_Turing [3] : https://fr.wikipedia.org/wiki/Th%C3%A8se_de_Church [4] : https://www.college-de-france.fr/site/frederic-magniez/p50450114447848887content.htm [5] : https://www.youtube.com/watch?v=itgPhvTMSZQ [6] : https://fr.wikipedia.org/wiki/Coq(logiciel)