Discussion :

[acacia]

Bonsoir,

Je voudrai faire décaler un mot de l'alphabet {0, 1} d'une position à droite dans le ruban de Turing.

j'ai raisonné comme suit:

On se déplace à droite
q0, $, $, droite, q1

On se place à l'autre bout du mot
q1, 1, 1, droite, q1
q1, 0, 0, droite, q1

Arrivé à la fin
q1, #, #, droite, q2

maintenant je n'arrive pas à trouver comment réécrire chaque symbole en remplaçant les blancs.

Je sais qu'il y a surement une meilleure idée pour faire ce décalage

Help please

[Jedai]

Ta dernière transition devrait plutôt être :
q1, #, #, gauche, q2

Puis :
q2, 0, #, droite, q3
q2, 1, #, droite, q4
q3, #, 0, gauche, q1
q4, #, 1, gauche, q1

Et la machine s'arrêtera lorsque q2 rencontrera un blanc.

--
Jedaï

[acacia]

Ta dernière transition devrait plutôt être :
q1, #, #, gauche, q2

Puis :
q2, 0, #, droite, q3
q2, 1, #, droite, q4
q3, #, 0, gauche, q1
q4, #, 1, gauche, q1

Et la machine s'arrêtera lorsque q2 rencontrera un blanc.

--
Jedaï

Merci j'ai déroulé et j'ai très bien compris les transitions.

mais je ne vois pas comment q2 pourrait rencontrer un blanc! ce n'est pas un $ qui va indiquer l'arrêt?

[ToTo13]

Bonsoir,

si tu veux décaler ton mot vers la droite, il te faut démarrer de la gauche
Tu démarres d'un état initial qui mémorise le premier symbole et le remplace par ton symbole vide.
Ensuite, tu sauvegardes ton état en remplaçant par l'état précédent ainsi de suite jusqu'à arriverà la droite du mot.

[acacia]

Bonsoir,

si tu veux décaler ton mot vers la droite, il te faut démarrer de la gauche
Tu démarres d'un état initial qui mémorise le premier symbole et le remplace par ton symbole vide.
Ensuite, tu sauvegardes ton état en remplaçant par l'état précédent ainsi de suite jusqu'à arriverà la droite du mot.

Merci je crois que c'est ce qu'on a fait pour décaler le mot à droite.

maintenant pour le décaler à gauche c'est presque la même procédure sauf qu'au lieu de démarrer de la gauche on démarre de la droite. non?

[Jedai]

Merci j'ai déroulé et j'ai très bien compris les transitions.

mais je ne vois pas comment q2 pourrait rencontrer un blanc! ce n'est pas un $ qui va indiquer l'arrêt?

Je n'avais pas fait attention mais si effectivement ton ruban est rempli de $ avant les données (ou tu as un ruban semi-infini), effectivement q2 ne rencontrera pas de blanc mais bien le premier $.
En tout cas il s'arrêtera, après je n'ai pas toutes les spécifications de tes machines de Turing donc je ne sais pas très bien comment signaler un succès, mais par exemple si tu utilises un état pour signaler le succès, tu peux rajouter cette transition :
q2, $, $, _, qSuccès

Néanmoins la proposition de Toto13 est plus efficace, un seul parcours suffit pour effectuer le décalage d'un rang vers la droite :
q0, $, $, droite, q1

q1, 0, #, droite, q2 -- # ou $ selon ta convention ??
q1, 1, #, droite, q3 -- idem

q2, 0, 0, droite, q2
q2, 1, 0, droite, q3
q2, #, 0, _, qSuccès

q3, 0, 1, droite, q2
q3, 1, 1, droite, q3
q3, #, 1, _, qSuccès

--
Jedaï

[ToTo13]

Néanmoins la proposition de Toto13 est plus efficace, un seul parcours suffit pour effectuer le décalage d'un rang vers la droite :
q0, $, $, droite, q1

q1, 0, #, droite, q2 -- # ou $ selon ta convention ??
q1, 1, #, droite, q3 -- idem

q2, 0, 0, droite, q2
q2, 1, 0, droite, q3
q2, #, 0, _, qSuccès

q3, 0, 1, droite, q2
q3, 1, 1, droite, q3
q3, #, 1, _, qSuccès

Je pense que c'est la meilleure façon de faire : un seul parcours avec mémorisation.

[acacia]

Je vous remercie beaucoup pour vos explications.

q0, $, $, droite, q1

q1, 0, #, droite, q2 -- # ou $ selon ta convention ??
q1, 1, #, droite, q3 -- idem

q2, 0, 0, droite, q2
q2, 1, 0, droite, q3
q2, #, 0, _, qSuccès

q3, 0, 1, droite, q2
q3, 1, 1, droite, q3
q3, #, 1, _, qSuccès

Le $ est un caractère qui marque le début du ruban et on ne peut l'effacer ou le remplacer, par contre le # signifie un blanc.