Définition de la machine de Turing

Alors que le monde se dirigeait vers une nouvelle conflagration mondiale, dans les années 1930, la science de l'informatique Il avançait également, guidé dans de nombreux cas par la préparation de l'effort de guerre que certains prévoyaient déjà arriver.

C'est dans ce contexte que le mathématicien britannique Alan Turing (considéré a posteriori comme l'un des pères de la l'informatique moderne) développe son œuvre et, en 1936, postule quels seront les fondements de la l'ordinateur moderne.

L'appel Machine de Turing C'est un dispositif théorique capable de traiter des données selon des règles données.

Les règles et les données sont distinctes; en fait, Turing a imaginé que les règles seraient stockées sur une sorte de support fixe, alors que les données seraient stockées sur des bandes que la même machine pourrait modifier selon la table des Règles.

On voit bien dans ce modèle conceptuel une avancée de ce que seront les ordinateurs modernes: même si l'on a un niveau de

Nom d'utilisateur simple, vous pouvez facilement voir la distinction entre le application "Immuable" (avec des nuances, mais dans ce cas prenons-le ainsi) et les données, qui peuvent être modifiées suivant les règles, qui seraient les programmation.

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

En d'autres termes, si un problème pouvait être exprimé par un algorithme A l'écrit, il pourrait être traité - au moins sur le plan théorique - par une machine de Turing.

Alan Turing l'a conçu comme un exercice pour montrer qu'il y avait des problèmes mathématiques que les ordinateurs ne pouvaient pas résoudre.

La bande de données, que Turing considérait 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 qui peut être rembobinée ou avancée pour discrétion.

L'ensemble de règles peut également être compris comme un langage de programmation, puisqu'il doit avoir une syntaxe logique et cohérente.

Avec le recul, d'autres mathématiciens ont créé des versions plus sophistiquées de la machine de Turing.

Ainsi, il existe des machines à deux bandes, des déterministes, ou encore une machine de Turing quantique qui peut aider, comme l'a fait son illustre ancêtre, à jeter les bases du calcul tant attendu quantum.

Photo Fotolia: Chrisdorney / Steve Simmons

Sujets dans la machine de Turing