La Minute Led #58

Puissant point.

On peut l’utiliser pour réaliser des jeux, des rapports de recherche, voir des présentations avec : mais peut-on envisager de tout faire avec ? Voici une thèse (et une vidéo) qui cherche à le prouver :

Mais pourquoi Turing-complet ?

« Turing » vient de Alan Turing, un grand mathématicien et cryptologue britannique. Ses compétences dans le domaine algorithmiques lui ont permis entre autres d’aider au déchiffrement d’Enigma, une machine utilisée par les nazis pour chiffrer leurs messages pendant la Seconde Guerre mondiale.

Il est également à l’origine du concept de « machine de Turing » d’où descend la notion de « Turing complet » ou Turing Completeness en anglais. La machine de Turing n’est pas un objet réel, bien que des modèles réels aient été réalisés, par exemple par l’ENS de Lyon.

Elle se compose

  • D’un ruban de longueur infini, subdivisé en cases contenant chacune un symbole issu d’un alphabet donné (binaire par exemple, donc soit 0, soit 1),
  • D’une tête de lecture/écriture, capable de lire la case sur laquelle elle est positionnée, d’écrire quelque chose dans la case et de faire avancer ou reculer le ruban,
  • D’un registre d’états définissant tous les états possibles de la machine ainsi que son état courant,
  • Et enfin d’une table de transitions définissant, pour un symbole lu dans la case et selon l’état dans laquelle se trouve la machine, que doit-elle écrire, dans quel état doit-elle passer et de combien de cases elle doit avancer/reculer le ruban. Si la combinaison symbole/état n’existe pas, la machine s’arrête.

Par exemple : on souhaite coder une machine capable de multiplier par deux quatre ; on rappelle qu’en binaire, multiplier par deux revient à ajouter un zéro à droite du nombre. 100, quatre en binaire, multiplié par deux, donne donc 1000 : huit.

La machine va donc inscrire successivement « 1-0-0-0 » avant de s’arrêter lorsqu’elle rencontrera un 0 dans l’état 4, qui n’est pas défini dans la table.

Quel est le rapport avec le terme « Turing-complet », me direz-vous ? On y vient ! La table de transition de la machine de Turing est capable de représenter n’importe quel algorithme. Or, vous savez que votre ordinateur ne fait qu’exécuter des programmes qui sont la réalisation d’algorithmes.

Il est donc possible de créer une table de transitions pour Windows, et d’utiliser Powerpoint ou la machine de nos amis de l’ENS pour faire les calculs. J’espère par contre que vous avez deux vies devant vous ou un stock d’Epice parce que ça risque de prendre un tout petit peu de temps.