422
13 L’ordinateur ` a ADN
Exemple 13.1 Soit un ruban non born´ e vers la droite et s´ epar´ e en cases distinctes tel
qu’illustr´ e dans la figure 13.4. Un symbole blanc, B, occupe la premi` ere case, suivi par
une suite de 1 et de 0 qui se termine par un autre B, chaque symbole occupant une
case distincte. L’ensemble des symboles {0, 1, B} forme ce qu’on appelle un alphabet.
Un pointeur dans un certain ´ etat, l’´ etat initial (parmi un nombre fini d’´ etats), indique
la premi` ere case. Notre but est de changer tous les 1 en 0 et tous les 0 en 1, puis de
ramener le pointeur vis-` a-vis de la premi` ere case.
Fig. 13.4. Un ruban semi-infini
Les actions possibles d´ ependent de l’´ etat du pointeur et du caract` ere point´ e. Elles
sont de trois types :
1. changer le caract` ere sur le ruban ;
2. changer l’´ etat du pointeur ;
3. se d´ eplacer d’une case vers la gauche ou vers la droite.
Voici l’algorithme qui nous permet d’effectuer la tˆ ache voulue. Lorsque le pointeur
rencontre le premier blanc, il se d´ eplace vers la droite. Par la suite, chaque fois qu’il
rencontre un 1, il le change pour un 0 et il se d´ eplace d’une case vers la droite ; chaque
fois qu’il rencontre un 0, il le change en 1 et il se d´ eplace d’une case vers la droite, le
tout jusqu’` a ce qu’il arrive `
a un deuxi` eme blanc. Il recule alors jusqu’au premier blanc.
Cet algorithme est repr´ esent´ e `
a la figure 13.5.
Fig. 13.5. Algorithme de l’exemple 13.1
D´ ecrivons ce type de diagramme de mani` ere plus d´ etaill´ ee puisqu’il sera utilis´ e ` a
quelques reprises dans ce chapitre. Les cercles repr´ esentent les ´ etats dans lesquels peut
13 L’ordinateur ` a ADN
Exemple 13.1 Soit un ruban non born´ e vers la droite et s´ epar´ e en cases distinctes tel
qu’illustr´ e dans la figure 13.4. Un symbole blanc, B, occupe la premi` ere case, suivi par
une suite de 1 et de 0 qui se termine par un autre B, chaque symbole occupant une
case distincte. L’ensemble des symboles {0, 1, B} forme ce qu’on appelle un alphabet.
Un pointeur dans un certain ´ etat, l’´ etat initial (parmi un nombre fini d’´ etats), indique
la premi` ere case. Notre but est de changer tous les 1 en 0 et tous les 0 en 1, puis de
ramener le pointeur vis-` a-vis de la premi` ere case.
Fig. 13.4. Un ruban semi-infini
Les actions possibles d´ ependent de l’´ etat du pointeur et du caract` ere point´ e. Elles
sont de trois types :
1. changer le caract` ere sur le ruban ;
2. changer l’´ etat du pointeur ;
3. se d´ eplacer d’une case vers la gauche ou vers la droite.
Voici l’algorithme qui nous permet d’effectuer la tˆ ache voulue. Lorsque le pointeur
rencontre le premier blanc, il se d´ eplace vers la droite. Par la suite, chaque fois qu’il
rencontre un 1, il le change pour un 0 et il se d´ eplace d’une case vers la droite ; chaque
fois qu’il rencontre un 0, il le change en 1 et il se d´ eplace d’une case vers la droite, le
tout jusqu’` a ce qu’il arrive `
a un deuxi` eme blanc. Il recule alors jusqu’au premier blanc.
Cet algorithme est repr´ esent´ e `
a la figure 13.5.
Fig. 13.5. Algorithme de l’exemple 13.1
D´ ecrivons ce type de diagramme de mani` ere plus d´ etaill´ ee puisqu’il sera utilis´ e ` a
quelques reprises dans ce chapitre. Les cercles repr´ esentent les ´ etats dans lesquels peut