Machine de Turing

Une machine de Turing se compose des éléments suivants (simplifiés) :

• Un ensemble limité d'états (avec un état marqué comme état de départ ; en cours de fonctionnement, une machine de Turing a toujours un état actuel)
• Une bande infinie avec des cellules de stockage et un dispositif de lecture/écriture qui peut se déplacer sur la bande
• Une définition de la fonction dite de transition

Il faut également définir un alphabet de travail (ensemble de caractères).

Lorsqu'une machine de Turing est mise en marche, un mot (de l'alphabet de travail) doit être présent sur la bande infinie de la machine. L'appareil de lecture/écriture sur le premier caractère lit alors le premier caractère et, selon l'état actuel de la machine de Turing, l'appareil de lecture/écriture écrase le caractère avec un nouveau ou déplace une cellule vers la gauche ou vers la droite. En outre, l'état actuel de la machine peut être modifié.

Les machines de Turing qui décident des langues

Pour la théorie de la décidabilité, on dit qu'une machine de Turing décide d'une langue si elle est toujours capable de déterminer si un mot donné est contenu dans une certaine langue ou non. Par conséquent, la machine a généralement deux états spéciaux marqués comme Accepter et Rejeter. Au bout d'un certain temps, l'un des deux états est atteint (en fonction du mot d'entrée) et la machine est arrêtée. Si un seul de ces deux états est atteint, la machine de Turing est dite semi-décider d'une langue.

Les machines de Turing qui calculent les fonctions

Si une machine de Turing est utilisée pour le calcul des fonctions, elle n'a qu'un seul état final. Lorsque la machine arrive à cet état, elle est arrêtée et le résultat de la fonction (en fonction de l'entrée) peut être trouvé sur la bande.

Les machines de Turing n'ont pas été inventées pour être construites dans la réalité, mais elles sont très importantes pour l'informatique théorique car elles sont l'un des modèles les plus simples pour les ordinateurs. La thèse de Turing affirme que tous les ordinateurs ne sont pas plus puissants que les machines de Turing. Cela peut être utilisé pour prouver si un problème peut être résolu par un ordinateur ou non.

• Une machine de Turing peut être constituée de plusieurs bandes infinies (et de plusieurs dispositifs de lecture/écriture). Il est toutefois prouvé que ces machines ne sont pas plus puissantes que les machines à bande unique. Les machines à bandes multiples sont utiles pour traiter des problèmes plus complexes.
• Si une machine de Turing a une fonction de transition non déterministe, il peut y avoir plusieurs transitions d'un état à plusieurs autres lors de la lecture d'un caractère. Là encore, cela ne renforce pas la puissance des machines de Turing. Cependant, les machines de Turing non déterministes (comme on les appelle alors) peuvent éventuellement réduire le temps de calcul de manière importante. Cette question est traitée dans la discussion P contre NP et n'est pas encore résolue. La plupart des scientifiques pensent cependant que les machines non déterministes peuvent travailler beaucoup plus rapidement sur certains problèmes.
• Une machine de Turing universelle est une variante qui peut simuler une machine de Turing avec une entrée.