Qu’est ce que : Définition de la machine de Turing

Alors que le monde se dirigeait vers une nouvelle conflagration mondiale dans les années 1930, l’informatique progressait également, guidée dans de nombreux cas par la préparation à l’effort de guerre que certains prévoyaient déjà.C’est dans ce contexte que le mathématicien britannique Alan Turing (considéré plus tard comme l’un des pères de l’informatique moderne) a développé ses travaux et a postulé, en 1936, ce qui allait devenir les fondements de l’ordinateur moderne.

La ‘machine de Turing’ est un dispositif théorique capable de traiter des données selon des règles données.

Les deux, les règles et les données, sont séparées ; en fait, Turing imaginait que les règles seraient stockées dans une sorte de support fixe, tandis que les données seraient stockées sur des bandes que la machine elle-même pourrait modifier en fonction de la table des règles.
Nous voyons clairement dans ce modèle conceptuel un avant-goût de ce que seront les ordinateurs modernes : même si l’on a un niveau utilisateur simple, on peut facilement voir la distinction entre l’application ‘immuable’ (avec des nuances, mais dans ce cas, prenons-la comme telle) et les données, qui peuvent être modifiées en suivant les règles, ce qui serait de la programmation.
–

Bien que la machine théorique de Turing soit terriblement simple, n’effectuant que des opérations très basiques comme le changement d’état, la lecture et l’écriture, elle est capable d’effectuer tous les calculs mathématiques qu’un ordinateur mécanique peut réaliser au moyen d’un algorithme.

En d’autres termes, si un problème peut être exprimé au moyen d’un algorithme écrit, il peut être traité – du moins, à un niveau théorique – par une machine de Turing.
Alan Turing l’a conçu comme un exercice visant à démontrer qu’il existait des problèmes mathématiques que les ordinateurs ne pouvaient pas résoudre.
La bande de données, que Turing concevait comme infinie, peut être déplacée par la machine de droite à gauche et de gauche à droite, comme une vieille cassette ou une bande de film que l’on peut rembobiner ou avancer à volonté.
L’ensemble de règles peut également être compris comme un langage de programmation, puisqu’il doit avoir une syntaxe logique et cohérente.

Par la suite, d’autres mathématiciens ont réalisé des versions plus sophistiquées de la machine de Turing.

Il existe donc des machines déterministes à deux bandes, ou même une machine de Turing quantique qui peut nous aider, comme l’a fait son illustre ancêtre, à jeter les bases de l’informatique quantique tant attendue.
Photo Fotolia : Chrisdorney / Steve Simmons