Qui est Alan Turing ?

Alan Turing

Encore enfant, il a appris à lire tout seul en 3 semaines.
C’est l’un des génie de son époque. Alan Turing est connu pour deux travaux principaux :

  • Le décryptage d’Enigma, où ils participent à la victoire des alliés durant la 2nde guerre mondiale
  • La Machine de Turing

Le décryptage d’Enigma

Les allemands utilisent Enigma pour chiffrer les données confidentielles, par exemple l’heure et le lieu des frappes sur le territoires des alliés.

Comprendre ces chiffrements permettront aux alliés d’anticiper les attaques des allemands. Une équipe d’experts en cryptologie est mis en place en Grande-Bretagne et Turing en fait parti. L’objectif est de comprendre comment fonctionne la machine Enigma.

Il ne faut pas croire qu’Enigma est un simple changement alphabétique : le a qui est remplacé par le b, le c par le d. Au contraire, à chaque lettre, la substitution est différente.

Enigma fonctionne avec 8 rotors. La difficulté est que les positions des rotors sont réinitialisés tous les jours : même s’ils sont sur une bonne piste pour résoudre la cryptologie allemande le 1er jour, Turing et son équipe doivent recommencer le lendemain.

Heureusement pour eux, les allemands ont laissé des indices qui permettent de résoudre le cryptage :

  1. Chaque lettre ne peut pas être substituer par elle-même. La lettre « T » sera cryptée par n’importe quelle lettre de l’alphabet, hormis le « T ». Ce qui permet à Turing d’éliminer à chaque lettre, une chance sur 26 au niveau du cryptage. C’est peu mais non négligeable pour résoudre une machine aussi complexe qu’Enigma.
  2. Les allemands utilisent toujours le même type de mots, par exemple « Bulletin météo » dans leur textes cryptés. L’équipe scientifique britannique peut alors s’aider de ces mots récurrents pour résoudre plus facilement le codage.
  3. Très souvent, les messages allemands finissaient par un « Heil Hitler ». Comme pour « Bulletin météo », on peut deviner plus rapidement le décryptage, lorsque des mots apparaissent tous les jours.

La Machine de Turing

Il s’agit d’une machine abstraite. Ce modèle est une simplification de ce que les ordinateurs sont capables de réaliser. Il est utilisé aujourd’hui par les chercheurs qui souhaitent comprendre la complexité des problèmes en informatique.

En clair, tout ce que peut faire un ordinateur aujourd’hui, en terme de complexité, la machine de Turing est capable de le faire.

Pour réaliser une machine de Turing, il faut :

  • Un ruban de taille illimité découpé en cases
  • Une tête de lecture qui peut lire la case et écrire dans cette case
  • Un ensemble d’états
  • Une table d’actions

Prenons un exemple tout simple. Est-ce qu’un ordinateur est capable de transformer une chaîne de caractères composé de 0 et 1 en son opposé ? Oui. Donc la machine de Turing est aussi capable de le faire.

Si on donne au programme les caractères « 101 », alors le programme devra nous renvoyer « 010 ».

On donne des ordres à la machine (table d’actions). Pour cette exemple, on donne trois ordres :

  • si sur la case il est écrit un 0, alors écrit 1 et déplace la tête de lecture vers la droite
  • si sur la case il est écrit un 1, alors écrit 0 et déplace la tête de lecture vers la droite
  • si la case est vide, alors ARRÊT

La tête de lecture est sur le chiffre tout à gauche, 1. La tête de lecture est positionné sur cette case. Comme c’est le chiffre 1, on suit le 2ieme ordre. La machine écrit un 0 et déplace la tête de lecture vers la droite.

Le deuxième chiffre est un 0. On suit donc la première règle : on écrit un 1 et on se déplace vers la droite.

Le troisième chiffre est un 1, on suit la 2ième règle, on écrit un 0 et on se déplace une nouvelle fois vers la droite.

Enfin, on arrive dans une case vide. Le programme s’arrête.

On a donc transformé la chaîne de caractères « 101 » en « 010 ».

C’est un exemple tout simple, mais tout programme réalisable sur ordinateur est capable d’être réalisé grâce à une machine de Turing. Même si cette machine est abstraite, on est capable de la créer.

Vous trouverez plus d’infos dans les liens ci-dessous.

Plus d’infos…

Sur Turing

  • Page Wikipedia d’Alan Turing
  • Imitation Game (le film à voir absolument sur la vie d’Alan Turing et en particulier sur Enigma).

Sur Enigma

  • Imitation Game, le film

Sur la Machine de Turing

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *