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