ALAN TURING AND HIS IMPACT ON SOCIETY
“Sometimes it is the people no one can imagine anything of who do the things no one can imagine.”
LA MACHINE DE TURING
La machine de Turing n’est pas une machine comme les autres, elle est abstraite. En effet, en 1936, Alan Turing imagine sa machine, et espère s’en servir comme modèle pour effectuer n’importe quel calcul. Il s’inspire d’une simple machine à écrire et en crée une version minimaliste que l’on doit utiliser avec un programme. En effet, lors du temps de Turing, on commence à se demander comment l’on peut définir une machine ou un algorithme pouvant résoudre sans intervention extérieure le maximum de problèmes possibles.
La machine de Turing est composée de plusieurs parties :
Un ruban infini : c’est la feuille de papier de la machine, elle va écrire dessus. Le ruban fait en effet office de mémoire et l’on va pouvoir faire balader une tête de lecture et d’écriture au dessuis de celui-ci.
Système de contrôle : c’est de la que le mathématicien va contrôler la machine et piloter la tête de lecture et d’écriture. Comme l’on est sur un ruban infini, on va pouvoir se déplacer à gauche ou à droite. On va même pouvoir demander à la tête de tout supprimer sur le ruban pour effectuer un autre calcul.
Une tête de lecture/ d’écriture : C’est elle qui va analyser le contenu de la case (en mode lecture) et elle qui va remplir la case d’un nombre, soit 1 ou 0.
La machine de Turing est ainsi définie par :
Q nombres d’états possibles que la machine peut rencontrer que l’on peut écrire sous la forme de : (q,s) => (q’, s’, d) ou (s) est le numéro vu par la machine, (q) étant l’état du nouveau site.
Un cercle reliant l’état (q( à l’état (q’), qui indique la transition : (q,s)=>(q’, s’,d).
Pour mieux comprendre, voici le calcul d’une addition. Les petites cases sont des cases qui n’ont pas été remplies. Le problème est que nous travaillons avec une machine de Turing en binaire et cela veut dire qu’il faut rajouter un bit a une valeur. Pour faire cela, il suffit d’incrémenter un nombre binaire, c’est à dire de remplacer un bit par 1 si c’est un 0 et passer à droite, mais si c’est un 1, la machine doit remplacer ce bit par 0 et l’incrémentation doit se faire à partir du bit précédent, à gauche. En effet, le binaire est sur une base de deux (voir l’article sur les ordinateurs ou la cryptologie.
Ici, la machine effectue une incrémentation
Pour calculer la somme de deux entiers binaires, il suffit de donner les deux entiers, séparés d’un «+ » ou d’un symbole prédéfini pour une somme. La machine de Turing va ensuite décrémenter (inverse d’incrémenter : soustraire un bit) le deuxième entier, puis d’incrémenter l’autre. A la fin du calcul, lorsque le deuxième entier est nul, la machine va arrêter d’incrémenter le premier entier et afficher celui-ci.
Voici un schéma montrant le cycle d’incrémentation/ de décrémentation.
Comme vous l’aurez compris, une machine de Turing peut faire des calculs basiques, qui vont ensuite être répétés en chaine pour effectuer des calculs bien plus complexes. Il faut de même impérativement utiliser un programme pour utiliser la machine.
De même, on peut voir que dans l’article fondateur de la machine, « On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society » écrit en 1936, que l’on peut construire une Machine de Turing universelle capable de reproduire ce qu’une machine de Turing (mode calculateur) ferait, si et seulement si la machine universelle a le même programme.