Salut à tous,
Je suis en 1ère année à la fac et on me demande de faire une machine de Turing en python, voici en gros le principe de fonctionnement : http://machinedeturing.net/

voici mon code :

mais je suis perdu dans mon raisonnement, pouvez vous m'aidez? Sachant que l'on a comme conditions d'avoir les 4 argument de la fonction, et d'utiliser la fonction d'association (la première fonction de l'image)

Merci d'avance

Tu peux nous dire où tu bloques et ce qui te gêne ? Ton code est pas assez explicite.

Et aussi nous dire comment tu comptes faire ça.

En fait je bloque surtout sur le lien entre les deux fonctions. la fonction "assoc" doit rendre un couple du style (a,b,c); Celle-ci marche mais je n'arrive pas à l'intégrer dans la fonction "turing". De plus je n'arrive pas à definir l'etat initial et le final en arguments de la fonction.

je compte faire un programme qui, étant donné ces 4 arguments : les etats initial et final, un ruban (une liste de chaîne de caractères) et une fonction de transition (qui est la fonction " assoc");
renvoie pour chaque action le ruban et l'etat.

je c'est pas si c'est un peu plus clair

Je sais pas si t'as montré le code entier et je vais sûrement dire des trucs que t'as déjà fait (je comprends pas trop ce que tu fais en fait) mais déjà j'imagine qu'il te faut une table de transition qui contient l'ensemble des transitions possibles.
Je suis pas un pro du Python mais pourquoi pas utiliser un dictionnaire pour associer un tuple (q, r) à un tuple (q', w, D) avec q et q' des états, r le caractère lu sur le ruban, w' le caractère écrit sur le ruban, D = {L, R} la direction.

Il faudra sûrement trouver des moyens d'encoder tout ça. Tu peux utiliser un caractère spécial pour dire "peu importe ce qui est lu faire ..." ou alors ajouter la même transition pour chaque caractères.

Ensuite t'as le ruban qu'on représente sous la forme d'une liste.
L'encodage est très important il te faudra un moyen d'encoder le mot "blanc" qui représente une case vierge sur le ruban. Tu peux utiliser ' ' ou 'b' ou ce que tu veux.

La machine de Turing ne parcours pas son ruban mais une table de transition qui contient toutes les règles qu'elle soit suivre. Une table de transition c'est un peu le programme d'une machine de Turing.

Ensuite il faudra que la machine de Turing sache :

• Dans quel état elle est (tu peux représenter ça par une chaîne de caractère)
• Quel est le caractère lu sur le ruban
• La position sur le ruban par stockage d'indice (tête de lecture)

Tu peux stocker ça dans des variables. Cela représente un peu la tête de lecture en fait.

Au départ disons qu'elle se trouve par défaut à l'état "q0".
La machine va parcourir la table de transition et chercher une transition pour q0 et le symbole lu. Le ruban est vierge donc il faudra qu'elle trouve une règle ("q0", ' ') -> ... dans la table de transition.
Si on a ("q0", ' ') -> ("q1", '1', 'L') il faudra que la machine interprète ça et se dise :

• Je dois aller à l'état "q1" donc je stocke "q1" dans la variable qui contient mon état actuel
• Il y a un "1" donc je dois écrire 1 sur le ruban (dans ce cas là tu l'écris où tu veux)
• (par une condition) s'il y a un 'L' je décale ma position vers la gauche, s'il y a un R vers la droite

Et ensuite le comportement de la machine de Turing évolue par changements successif d'états puis elle s'arrête ou ne s'arrête pas.

Désolé pour le double-post vu que cela est un peu HS, mais souvent quand je vois du code en Python, les variables c'est juste des lettres et pas des mots explicites, c'est une convention des développeurs Python ou quoi ?

Je veux bien quand c'est pour des fonctions mathématiques où les noms servent à rien mais là mettre des noms de variables plus explicites aurait pu te permettre d'éviter de mettre des commentaires pour décrire ce qu'elles représentent.

HS :
Je tiens à dire que ce n'est pas du tout une convention python, qui au contraire incite à programmer de manière claire^^. Par contre je viens de voir du R ces derniers temps, et eux semblent suivre la règle : "nommez vos variables de la manière la plus illisible, la plus obscure et la plus illogique, en tout temps, quoi qu'il arrive".

Le nommage de manière claire est une des bases du code lisible.
Il n'y a que pour les calculs mathématiques et les variables à très courtes durées de vie (bloc de 2-3 lignes) où cela peut avoir un sens.

Voir le livre clean code de Uncle Bob pour plus d'info et détails.