Question – Ecrire la machine de Turing Copie. Etat de départ, un bloc de 1 - le pointeur sur le 1 le lus à gauche. Etat d'arrivé : le bloc original suivi d'un 0 puis d'une copie du bloc original. Exemple :

…0111110… --> …0111110111110…

Réponses

L'idée est de "marquer" le 1 en cours de copie, afin de savoir où on en est à chaque tour.

(q0, 1, q1, 0) on marque le 1

(q0, 0, qf, G) on a presque fini

(q1, 0, q2, D) on est sur la marque, on se déplace à droite

(q2, 1, q2, D) on passe tous les 1 vers la droite

(q2, 0, q3, D) on passe le 0 séparateur

(q3, 1, q3, D) on passe tous les 1 de la copie (en cours)

(q3, 0, q4, 1) on écrit un nouveau 1

(q4, 1, q4, G) on revient à gauche (on passe la copie)

(q4, 0, q5, G) on passe le 0 séparateur

(q5, 1, q5, G) on passe tous les 1 (on passe ce qui reste à copier de l'original)

(q5, 0, q6, 1) on restaure le 1 à la place de la marque

(q6, 1, q0, D) on se remet dans l'état initial

(qf, 1, qf, G) on revient vers la gauche (on passe tous les 1 de l'original)

(qf, 0, qF, D) on se remet sur la position d'origine