Machines de Turing
Machine 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
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.
Machine de Turing universelle :
La machine de Turing universelle est une machine qui peut faire n’importe quel calculs, tout ce qui est calculable, n’importe quelle fonction récursive et peut analyser n’importe quel langage récursive