Machine de Turing (1)⚓︎
Une machine de Turing est une machine abstraite imaginée par Turing en 1936. Elle est composée de quatre éléments:
-
un ruban de longueur infinie sur lequel on peut lire et écrire;
-
une tête de lecture et écriture, qui peut lire, écrire et se déplacer sur le ruban;
-
un état interne qui peut changer à chaque étape;
-
une table des transitions qui décrit les règles de "calcul", (écriture, déplacement, changement d'état), basées sur l'état en cours de la machine et ce qui est lu sur le ruban.
Le nombre d'états est fini et il y a un état initial. Le ruban est divisé en cases qui contiennent chacune un symbole. La tête peut se déplacer d'une case vers la gauche ou vers la droite. Elle peut lire ou écrire un symbole sur la case du ruban qui lui fait face.
Les différents états peuvent être notés "e_0", "e_1", "e_2", ..., "e_0" étant l'état initial.
Pour les symboles lus et écrits, on se limite à "0", "1", ou "_", ce dernier symbole représentant un blanc.
Pour les déplacements, on utilise "g" et "d" pour un déplacement de la tête vers la gauche ou vers la droite.
Une règle de calcul, une instruction, peut être représentée par un quadruplet. Par exemple la règle ("e_2", "1", "0", "e_1") signifie que si la machine est dans l'état "e_2" et
qu'elle lit sur le ruban un "1", alors elle écrit un "0", (à la place du "1"), et passe dans l'état "e_1". La règle ("e_1", "0", "g", "e_1") signifie que si la machine
est dans l'état "e_1" et qu'elle lit sur le ruban un "0", alors elle se déplace d'une case vers la gauche et reste dans l'état "e_1".
De manière générale, à chaque étape, soit la machine écrit un symbole, soit elle se déplace, soit elle s'arrête. Ce dernier cas se produit s'il n'y a pas de règle correspondant à l'état en cours avec le symbole lu.
Une machine de Turing particulière peut être considérée comme un algorithme ou comme une fonction écrite en langage Python.
Implémentation⚓︎
Pour gagner en efficacité, la table des transitions est réprésentée par un dictionnaire. Par exemple les deux règles ("e_0", "0", "d", "e_0") et ("e_0", "1", "0", "e_0")
sont représentées par le dictionnaire: {("e_0", "0"): ("d", "e_0"), ("e_0", "1"): ("0", "e_0")} signifiant que
si la machine est dans l'état "e_0" et lit un "0" la tête se déplace vers la droite et la machine reste dans l'état "e_0", si elle
est dans l'état "e_0" et lit un "1" la tête écrit un "0" et la machine reste dans l'état "e_0".
Si le couple (etat, symbole_lu) n'est pas une clé du dictionnaire, la machine s'arrête.
Le ruban est représenté par une liste ruban. Chaque élément de la liste correspond à une case du ruban et la position de la tête est repérée par un indice.
Un élément de la liste peut être un "0", un "1" ou un "_". On l'obtient avec ruban[i].
Écrire "_" à la place d'un "0" ou d'un "1", soit ruban[i] = "_", revient à effacer le contenu de la case.
Les instructions i = i - 1 et i = i + 1 correspondent respectivement à un déplacement vers la gauche ou vers la droite de la tête.
Une machine de Turing doit produire un résultat après un nombre fini d'étapes donc n'utilise qu'un nombre fini de cases du ruban et un temps limité. On suppose donc la liste suffisammment grande pour pouvoir exécuter l'algorithme.
Question 1
Compléter la fonction machine qui prend en paramètres un dictionnaire, une liste et un entier, le dictionnaire et la liste
représentant respectivement une table des transitions et un ruban décrits précédemment, l'entier est l'indice représentant la position initiale de la tête sur le ruban.
Cet indice sera toujours le plus petit indice tels que le caractère lu par la tête est soit un "0" soit un "1".
La fonction modifie le ruban à l'aide de la table des transitions.
Cette fonction machine simule une machine de Turing universelle, c'est-à-dire que pour chaque table des transitions passée en argument, elle se comporte comme une machine de Turing particulière.
Exemple
L'exemple qui suit ne nécessite qu'un seul état, l'état initial "e_0". À chaque étape, si la tête lit un "0", elle se déplace vers la droite, sinon si elle lit un "1" elle écrit un "0", sinon elle s'arrête.
>>> table = {("e_0", "0"): ("d", "e_0"), ("e_0", "1"): ("0", "e_0")} # la table
>>> ruban = ['_', '_', '1', '0', '1', '1', '0', '1', '_', '_'] # le ruban
>>> machine(table, ruban, 2) # la tête est positionnée sur l'élément d'indice 3
>>> ruban
['_', '_', '0', '0', '0', '0', '0', '0', '_', '_']
Question 2
Compléter, en utilisant le minimum d'états distincts, la table des transitions table pour une machine qui remplace les "0" par des "1" et les "1" par des "0".
Le nom de l'état initial est toujours "e_0".
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
Question 3
Compléter, en utilisant le minimum d'états distincts, la table des transitions table pour une machine qui remplace les "0" et les "1" par des "_". Autrement dit, la machine efface le ruban.
Le nom de l'état initial est toujours "e_0".
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)