La Machine de Turing est l'un des concepts fondateurs de l'informatique moderne. Découvrez tout ce que vous devez savoir sur cette invention d'Alan Turing, sur laquelle reposent encore aujourd'hui nos ordinateurs...
Qui a créé la machine de Turing ?
En général, Babbage et Lovelace sont considérés comme les inventeurs des ordinateurs et de la programmation. Toutefois, on désigne bien souvent Alan Turing comme le père de la science informatique.
Pendant la Guerre mondiale, cet informaticien de génie a notamment aidé à concevoir des machines capables de déchiffrer le système de chiffrement de messages utilisé par l'armée allemande. En 1936, Alan Turing venait d'obtenir son diplôme de mathématiques au King's College de Cambridge. Il travaillait sur un problème mathématique lié à la Décidabilité et au Problème de l'arrêt : l'Entscheidungsproblem.
Son but était de démontrer qu'il n'y avait pas de procédure de décision générale pour la logique de premier ordre. Dans l'étude qu'il présenta à l'un de ses professeurs, Turing créa une machine imaginaire pouvant résoudre les algorithmes.
Il n'avait pas l'intention de construire cette machine, mais rédigea sa description mathématique pour prouver sa théorie. C'est ainsi qu'était née la machine de Turing.
Qu'est-ce qu'une machine de Turing ?
Une machine de Turing est une bande infiniment longue, divisée en cellules. Chaque cellule peut contenir un 1, un 0, ou un espace vide.
Au-dessus de chaque cellule de la bande se trouve une « tête», pouvant être déplacée vers la gauche ou la droite et capable de lire les symboles dans les cellules. Cette tête est aussi capable de remplacer les symboles par de nouveaux.
La direction dans laquelle la tête se déplace, les valeurs qu'elle remplace et les valeurs qu'elle entre dépendent d'un ensemble d'instructions fournies à la machine par le biais de la table de transition d'état.
Similaires aux automates finis, les machines de Turing ont l'avantage d'offrir une mémoire illimitée. Elles sont capables de simuler des ordinateurs classiques, et donc de résoudre n'importe quel problème qu'un ordinateur classique peut résoudre.
En utilisant ce simple système, Alan Turing a prouvé que n'importe quel problème mathématique calculable peut être calculé par une machine de Turing.
Comment fonctionne la machine de Turing ?
À la manière d'un algorithme, la machine de Turing s'exécute sur une chaîne de bits. On commence par écrire la chaîne de bits sur la bande, et la tête pointe initialement la première cellule. Les autres cellules sont vides.
La tête de la machine lit et écrit des symboles à mesure qu'elle se déplace le long de la bande. Chaque fois que la tête lit un symbole, elle décide quoi faire par la suite : quel symbole écrire sur la bande, et dans quelle direction se déplacer ensuite. Ses décisions dépendent de l'ensemble de fonctions de transitions associées à la machine.
La fonction de transition est en fait une ligne d'instruction spécifique dans le programme d'une machine de Turing. L'ensemble des fonctions de transition peut être considéré comme le programme complet indiquant à la machine de Turing ce qu'elle doit faire selon les entrées qu'elle reçoit.
Pendant l'opération, la tête de la bande est dans un certain état. À chaque étape, elle consulte la table de transition d'état et se base sur son état actuel et le symbole de la cellule qu'elle pointe pour obtenir son prochain choix : terminer l'opération, écrire un symbole dans la cellule actuelle, changer d'état, ou se déplacer vers la gauche ou la droite.
C'est ainsi qu'une machine de Turing peut simuler le fait qu'un programme est composé de nombreuses lignes, et dépend donc de la ligne exécutée par le programme. Elle peut aussi simuler le fait qu'un programme peut réagir différemment selon les données en mémoire.
La machine de Turing peut s'exécuter à l'infini, ou s'arrêter à un point. En cas d'arrêt, les contenus de la bande sont le résultat.
Qu'est-ce qu'une machine de Turing universelle ?
La machine de Turing universelle est dotée d'une configuration spéciale lui permettant de répliquer n'importe quelle autre machine de Turing.
Elle repose sur l'écriture de la configuration à dupliquer sur la bande. Pour ce faire, Alan Turing a créé un langage permettant d'encoder la configuration sur les tables. Ce langage permet d'encoder la bande de toutes les machines.
En utilisant des caractères comme « D », « C », « A », « R », « L », « N », « ; », il est possible d'encoder n'importe quelle configuration sur une bande. Ainsi, la machine de Turing universelle peut faire tout ce que les autres machines de Turing peuvent faire.
Sa fonctionnalité reste tout aussi simple, et seule la configuration change. Cette idée de stocker la configuration sur une bande est l'un des concepts fondateurs de l'informatique moderne.
Sans cette invention, il serait nécessaire d'acheter un ordinateur différent pour chaque cas d'usage. Vous auriez par exemple besoin d'un ordinateur pour gérer vos comptes, d'un PC pour jouer aux jeux vidéo et d'une autre machine pour consulter vos emails.
Aujourd'hui encore, les ordinateurs modernes fonctionnent de la même manière que Turing l'imaginait. L'architecture von Neumann utilisée par la plupart des systèmes actuels est fortement influencée par son papier daté de 1936…
Comment utiliser une machine de Turing ?
La configuration universelle et adaptable est ce qui permet à nos ordinateurs d'effectuer une immense variété de tâches. Le stockage des instructions sur une bande au lieu de les implémenter directement dans la machine est le principe de base des logiciels modernes. Le papier d'Alan Turing a posé les fondations des systèmes informatiques utilisés de nos jours.
Il existe de nombreux simulateurs sur le web, permettant de créer et d'exécuter une machine de Turing. Cette invention est utilisée encore aujourd'hui dans un grand nombre de domaines de l'informatique, notamment l'intelligence artificielle et la cybersécurité.
Afin de devenir expert en cybersécurité, vous pouvez choisir la Cyber University. Notre formation d'une durée de 365 heures vous permet d'acquérir toutes les compétences requises pour exercer le métier d'Analyste Cyberbesécurité Operationnelle.
À travers les modules du programme, vous découvrirez notamment les fondamentaux de la cybersécurité, les stratégies d'attaque et de défense, les composants de la cyberdéfense, la gestion de crise cyber ou encore le contexte juridique et normatif.
Notre formation tournée vers la pratique se distingue par l'utilisation d'un simulateur de cyberattaques, et par un projet fil rouge permettant d'appliquer les connaissances assimilées.
La Cyber University adopte une approche hybride Blended Learning alliant apprentissage sur une plateforme interactive et Masterclass. Cette formation s'effectue intégralement à distance, et permet d'obtenir une certification de formation de l'université Paris | La Sorbonne.
Vous pouvez compléter le programme en Formation Continue ou en Bootcamp, et notre organisme est éligible au CPF pour le financement. N'attendez plus et découvrez la Cyber University !
Vous savez tout sur la Machine de Turing. Pour plus d'informations, découvrez notre dossier complet sur l'informatique et notre dossier sur les NTIC.
.png)
.png)
