Qu'est-ce que la complétude de Turing?
La complétude de Turing se produit lorsqu'un langage de programmation est capable d'exécuter les fonctions d'une machine de Turing. Ceci est un concept pour un ordinateur mécanique très basique, parfois décrit comme la machine la plus simple pouvant être considérée comme un ordinateur. Pratiquement tous les langages de programmation utilisés de nos jours et, en théorie, les ordinateurs qui les exécutent sont complets.
Le concept de complétude de Turing vient d’Alan Turing, un informaticien britannique dont les travaux comprenaient le déchiffrement de messages codés pendant la Seconde Guerre mondiale. Parmi ses travaux sur l'informatique figurait l'élaboration d'une philosophie de ce qu'un ordinateur pourrait réellement faire. Cela incluait le concept selon lequel les ordinateurs fonctionnent simplement en exécutant des algorithmes. C'est-à-dire qu'ils suivent un ensemble de règles fixes pour traiter les données et résoudre les problèmes. Cela signifie qu'un ordinateur ne "pense" pas et ne prend pas de décisions comme une personne peut le faire.
Pour illustrer ce concept, Turing a décrit une machine hypothétique qu’il a appelée "une machine", le "a" signifiant automatique; d'autres l'ont appelée plus tard la machine de Turing. La machine traiterait une bobine de bande pouvant se déplacer en avant et contenant une ligne de symboles. A tout moment, la machine peut traiter un symbole et, si nécessaire, le modifier. Aux fins du concept, la bobine de bande pourrait être infiniment longue, ce qui signifie que la mémoire de l'ordinateur n'était pas intrinsèquement limitée. Il s'agit d'une analogie avec l'idée qu'une fois qu'un ordinateur doit suivre un ensemble d'instructions, la quantité de données à laquelle il peut appliquer ces instructions est uniquement soumise à des limites physiques.
Ironiquement, la plupart des ordinateurs actuels n’ont pas réellement la complétude de Turing. En effet, ils ont des limites en termes d'espace de stockage disponible et donc de données qu'ils peuvent traiter. Ils ont également des limitations physiques, notamment le fait qu'ils finiront par s'user. C'est en réalité le langage de programmation qui a la complétude de Turing. Pour cette raison, un ordinateur exécutant un tel programme n'est pas un ordinateur Turing, mais peut être utilisé pour en simuler un.
L'exhaustivité de Turing ne doit pas être confondue avec le test de Turing. Il s’agissait d’une expérience conçue par Turing pour voir si les ordinateurs pouvaient converser en langage naturel. Le principe du test est le suivant: si un humain ne peut pas faire la différence entre une conversation en mode texte uniquement avec l'ordinateur et un autre humain, l'ordinateur réussit le test. Bien que certains ordinateurs aient réussi le test lorsque le nombre de sujets de conversation est restreint, aucun ne l’a fait dans une conversation sans restriction.