La machine de Turing ou les prémices de l’ordinateur moderne

Aujourd’hui, on utilise les ordinateurs couramment, sans vraiment se poser de questions. Il est devenu en peu de temps un outil incontournable au quotidien et cela va s’accroître car de plus en plus de procédures seront faisables seulement par le biais du numérique et donc d’un ordinateur. 

Mais qui a pensé ces ordinateurs ? Comment l’idée est venue ? Pour cela, il faut d’abord savoir qui est son inventeur et comment il a créé sa machine. 

  • Qui est Alan Turing ? 

Alan Turing est un mathématicien anglais né en 1912 et mort en 1954. Il est également à l’origine du craquage de la machine ENIGMA. La machine ENIGMA était une machine utilisée par les allemands lors de la seconde guerre mondiale pour crypter les messages que le commandement envoyait au soldat. Les services secrets des différents pays alliés pouvaient intercepter le message sans jamais le comprendre. En effet, le système est très simple : quand on appuyait sur une lettre pour écrire un mot, il y avait un circuit électrique fermé qui éclairait une ampoule correspondant à la lettre codée. Par exemple : on tapait la lettre A et c’est la lettre D qui s’illuminait et donc si le mot comportait la lettre A, celle-ci se transformait en D. De plus, cette technique était réversible, il suffisait donc pour les soldats allemands de retaper le message avec le code approprié et le message était décrypté. Il y avait plusieurs clés possibles de décryptage. Effectivement, la machine fonctionnait avec 5 rotors comportant chacun les 26 lettres de l’alphabet. A la suite de cela, il y a une boîte de câblage transformant 10 paires de lettres (donc 20 lettres sur 26 lettres de l’alphabet) et les 6 autres lettres restent inchangées. La machine ENIGMA transforme une lettre en une autre selon 158 962 555 217 826 360 000 possibilités. Il faudrait plusieurs millions d’années pour pouvoir déchiffrer un tel code. 

Alan Turing et son équipe ont réussi à craquer le code de la machine grâce à un bulletin météo que les allemands édictaient tous les matins afin de donner le code du jour. Le craquage de cette machine a permis de sauver des milliers de vie et de gagner la guerre. 

En 1937, Alan Turing écrit un article en vue de définir l’algorithme et cet article sera à l’origine des premiers calculateurs universels appelés aujourd’hui ordinateurs. Dans cet article il y présente sa machine : La Machine de Turing. 

  • Qu’est-ce que la machine de Turing ? 

Cette machine est la base de l’informatique moderne ainsi que de la programmation. En effet, c’est l’étalon qui a défini les langages informatiques.

La machine de Turing est « est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur ». Alan Turing a amorcé l’idée dans son article de 1936 : “on Computable Numbers, With An Application To The Entscheidungsproblem”. Dans cet article, Turing répond au problème posé par un mathématicien à savoir s’il existe un algorithme qui décide si une proposition énoncée dans un système logique est valide ou non. 

La machine de Turing est un des fondements de l’informatique car c’est la machine qui est la plus simple qu’on puisse concevoir et qui permet de satisfaire aux critères universels et informels définissant l’algorithme. De plus, elle est utilisée dans beaucoup de théories comme celle de la calculabilité (« La calculabilité cherche d’une part à identifier la classe des fonctions qui peuvent être calculées à l’aide d’un algorithme et d’autre part à appliquer ces concepts à des questions fondamentales des mathématiques. »)

La machine de Turing est une machine abstraite à calculer, elle permet de calculer tous les calculs. On entend par calcul tout ce que l’on peut faire intuitivement avec un crayon, une feuille de papier, des données initiales et visant la production d’un résultat précis. Ce qui est calculable par la machine de Turing l’est par un ordinateur. La réciproque est aussi vrai : ce qui n’est pas calculable par la machine de Turing et donc par un ordinateur n’est donc pas calculable.

  • Comment fonctionne la machine de Turing ? 

Alan Turing définira l’utilisation de sa machine comme une machine à écrire que l’on peut contrôler à l’aide d’un programme.

Cette machine contient : 

  • Un ruban infini divisé en case consécutives et chaque case contient un symbole d’un alphabet fini donné. Généralement l’alphabet se compose de 1 et 0.
  • Une tête de lecture qui peut lire et écrire ce qu’il y a sur le ruban. Elle se déplace sur la gauche ou sur la droite du ruban.
  • Un registre d’état qui retient l’état courant où est la machine de Turing. 
  • Une table d’action qui permet de savoir quel symbole écrire sur le ruban et les instructions pour déplacer la tête de lecture (soit à droite, à gauche), de savoir dans quel nouvel état se trouve la machine en fonction du symbole que lit la tête de lecture et l’état courant dans lequel se trouve la machine.

C’est donc bien comme une machine à écrire : une machine à écrire peut effacer et écrire sur une bande et reculer ou avancer d’un ou plusieurs caractères. Sauf que la machine de Turing, au lieu de faire cela sur une feuille de papier en deux dimensions, le fait sur un ruban infini divisé en cases.

Si aucune action existe pour une combinaison, la machine s’arrête. C’est en suivant les instructions que la machine fonctionne et que les calculs peuvent se faire. C’est sur cette base que fonctionne les ordinateurs. On peut donc assurer que la machine de Turing et donc Alan Turing sont les précurseurs de nos ordinateurs. 

Julie HAVY

M2 Cyberjustice- Promotion 2019-2020

Sources

https://fr.wikipedia.org/wiki/Machine_de_Turing

http://villemin.gerard.free.fr/Wwwgvmm/Logique/IAturing.htm

https://www.gralon.net/articles/materiel-et-consommables/materiel-informatique-et-consommable-informatique/article-alan-turing—le-fondateur-de-l-informatique-moderne-3857.htm

http://www.bibmath.net/crypto/index.php?action=affiche&quoi=debvingt/enigmaguerre

http://zanotti.univ-tln.fr/turing/

https://fr.wikipedia.org/wiki/Th%C3%A9orie_de_la_calculabilit%C3%A9

http://www.journaldunet.com/developpeur/tutoriel/theo/060119-machine-turing-complet.shtml

Laisser un commentaire