# machine de turing reconnaissant m#m
# Alexis Nasr 9/12/2014
# correspond à l'exemple 3.10 (p 173) du livre
# Intro. to the theory of Computation (3rd edition) de Michael Sipser
# on efface un 0 et on va en 1
0 1 0 x D
# tant qu'on ne lit pas un # on saute tous les 0 et les 1
1 1 0 0 D
1 1 1 1 D
# on saute le #
1 2 # # D
# on saute les x
2 2 x x D
# on a trouve le 0 correspondant, on l'efface
2 3 0 x G
# on va vers la gauche en sautant les 0, 1 et x
3 3 0 0 G
3 3 1 1 G
3 3 x x G
# on saute le #
3 8 # # G
# on continue vers la gauche en sautant les 0 et 1
8 8 0 0 G
8 8 1 1 G
# on trouve un x, on se déplace d'une case vers la droite et on retourne en 0
8 0 x x D
# même chose avec les 1
0 4 1 x D
4 4 0 0 D
4 4 1 1 D
4 5 # # D
5 5 x x D
5 3 1 x G
0 6 # # D
6 6 x x D
6 7 $ $ D
1 7