Machines de Turing
Machine de Turing
La machine de Turing à été inventée par Alan Turing en 1936. Elle représente le fonctionnement d’un appareil mécanique de calcul comme par exemple un ordinateur, c’est ce qui a donner une idée précise du concept de l’algorithme Le concept de Machine de Turing a été inventé avant l’ordinateur. Elle devait représenter une personne virtuelle qui devait exécuter une procédure définie par l’utilisateur qui consiste à changer le contenu des cases d’un ruban infini, et en choisissant ce contenu parmi un ensemble fini de symbole.
Définition
La machine de Turing est composée:
- D' un ruban infini à droite et à gauche sur lequel il y a des cases, chaque case peut contenir des symboles. Si il n’y a pas de symboles, c’est des cases blanches
- D’une tête de lecture / écriture : lit et écrit les symboles sur le rubans puis se déplace à droite ou à gauche selon la procédure
- Un registre d’état : c’est un registre mémorise l’état dans lequel il se trouve, il existe un spécial, c’est l’état de départ qui initialise la machine avant l'exécution de celle ci
- Table d’action : la table indique à la machine quel symbole écrire et comment se déplacer la tête de lecture et elle dit aussi le nouvel état à exécuter. Si il n’y a plus d’action à faire, la machine s’arrête.
Exemple
La machine de Turing à pour symbole {‘0’,’1’} et un autre qui correspond au symbole de la case vide. Nous avons en entrée de cette machine une suite de 1 et de 0. La tête de lecture/écriture se trouve à gauche de la suite de nombre
En exemple on va ajouter 1 à un nombre binaire. Pour cette fonction il nous faut 3 états.
Exemple pour ajouter 1 au nombre : { 10101 }
La machine commence par l’état 1, qui lit le symbole VIDE (une case blanche) puis le remplace par le symbole VIDE puis se déplace à gauche.
Elle passe à l’état 2, elle remplace le symbole lu par le même symbole et se déplace à gauche et quand se retrouve tout à droite du nombre et rencontre un symbole VIDE elle écrit VIDE et se déplace à droite .
Elle passe à l’état 3, quand elle lit un symbole 0 elle écrit 1 puis se déplace à droite et c’est la FIN du programme, quand elle lit un symbole 1 elle écrit 0 puis se déplace à droite et quand elle lit le symbole VIDE elle écrit 1 puis se déplace à droite et c’est la FIN du programme.
Voici quelques exemples de machine de Turing en python
Ajouter 1 : Fichier:Ajouter 1 turing v2.txt
Soustraire 1 : Fichier:Soustraire 1.txt
Multiplier par 2 : Fichier:Multiplier par 2.txt
Machine de Turing universelle
La machine de Turing universelle est une machine qui prend en paramètre une autre machine de Turing, ce qui nous permet de faire n’importe quel calculs. Grâce à la machine de Turing universelle, l'ordinateur peut éditer n'importe quel programme.
Voici un programme qui représente une machine de Turing universelle.Fichier:Machine universelle.txt