Calculabilité

Machine de Turing

Il s'agit de simuler à l'aide du langage Python l'exécution d'une machine de Turing

Voici les conventions utilisées

• Les états sont les entiers naturels
• L'état initial est l'entier 0
• L'état final est le plus grand des entiers parmi les états
• L'alphabet d'entrée avec lequel on écrit les mots est {0,1}
• L'alphabet de bande est {0,1,-1}, -1 désigne le caractère blanc
• La bande est une liste Python dont la taille est suffisamment grande au départ
• Au départ la tête de lecture se trouve sur la première cellule de la bande
• A l'état initial l'entrée est placée au début de la bande
• Les déplacements sont codés par 1 pour aller à droite et -1 à gauche
• Les transitions est un dictionnaire ,dont les clefs sont des couples (état,symbole lu) et dont les valeurs sont des triplets (état,symbole écrit,déplacement)

1. Traduire l'automate du cours pour la multiplication par 2 en un dictionnaire des transitions dico_mult_2
2. Définir un dictionnaire dico_div_2 pour la division par 2

Implémentation d'une classe Machine de Turing

• table :un dictionnaire de transitions (voir ci-dessus)
• etat :l'état courant de la machine de Turing
• entree :une liste de 0 et 1
• ruban : une liste de 0, 1 et -1
• pos: un entier la position de la tête
• etat_final:un entier l'état final

Voici le constructeur

class M_T:
    long_ruban = 10
    def __init__(self,table:dict,entree:list,etat_final:int):
        self.table = table
        self.etat = 0
        self.entree = entree
        self.ruban = entree+[-1]*(M_T.long_ruban - len(entree))
        self.pos = 0
        self.etat_final = etat_final

1. Définir les méthodes
• transition_possible() qui renvoie Vrai si une transition est possible à partir de l'état courant et du symbole lu

• calculer() qui renvoie() -1 s'il y a blocage sinon renvoie le tuple constitué de l'entrée et de la bande si la machine arrive à l'état final

  On suppose que la table de transitions ne génère pas de calcul infini

2. Tester la machine de Turing avec les automates du cours

La fonction eval() de Python

La fonction eval() de Python permet d'évaluer une expression

Par exemple

>>> x = 2
>>> y = 5
>>> eval('x+y')
7

>>> x = 2
>>> y = 5
>>> eval('x>y')
False 

Par contre une instruction comme x = 5 n'est pas une expression de même qu'une boucle for ou while

Pour évaluer un code Python contenant plusieurs instructions avec éventuellement une boucle for ou while, on utilise la fonction exec()

Un programme Python comme une chaîne de caractères

Par exemple on peut afficher le plus grand de deux nombres x et y ainsi

>>> max_2 = "if x > y:print(x)\nelse:print(y)"
>>> x = 5
>>> y = 2
>>> exec(max_2)
5

On affiche la valeur maximale contenue dans une liste d'entiers l

>>> max_l = "m = l[0]\nfor i in range(len(l)):\n\tif l[i] > m:m = l[i]\nprint(m)"
>>> l = [2, 5, 1]
>>> exec(max_l)
5

On utilise \t pour l'indentation on aurait pu aussi utiliser 4 caractères

Un programme universel

Un programme universel Python exécutant n'importe quel programme Python prgm en entrée sous la forme d'une chaîne de caractères à partir de n'importe quel entrée *args est (à condition de bien écrire prgm )

def universel(prgm,*args):
    exec(prgm)

>>> prgm="res=''\nfor mot in args:res += mot\nprint(res)"
>>> universel(prgm,'py','thon')
python

Ecrire le programme du tri par sélection sous la forme d'une chaîne de caractères et l'exécuter sur une liste d'entiers quelconque