13.4 Les machines de Turing et les syst` emes d’insertion–d´ el´ etion
439
13.4 Les machines de Turing et les syst` emes
d’insertion–d´ el´ etion de l’ordinateur ` a ADN
Nous avons vu comment une machine de Turing peut ex´ ecuter un programme.
Construisons de la mˆ eme mani` ere un ordinateur `
a ADN. Comme pour les machines
de Turing, nous aurons besoin d’un alphabet X constitu´ e d’un ensemble fini de symboles. Pour un ordinateur `
a ADN, l’alphabet naturel est bien sˆ ur constitu´ e des quatre
bases azot´ ees. Nous aurons donc
X = {A, C, G, T }.
Cet alphabet peut sembler restreint, mais rappelons que les ordinateurs conventionnels
ne disposent que d’un alphabet binaire compos´ e du 0 et du 1.
On construit alors des chaˆ ınes avec les symboles de cet alphabet et on d´ efinit X
∗
comme l’ensemble des chaˆ ınes finies qu’il est possible de construire par la m´ ethode de
la d´ efinition 13.3. Dans le cas de l’ADN, X
∗ repr´ esente donc l’ensemble des chaˆ ınes
simples d’ADN de longueur finie pouvant ˆ etre construites avec les quatre bases azot´ ees,
plus la chaˆ ıne nulle.
Dans une machine de Turing, les mots sont les entr´ ees du ruban. La machine de
Turing a un ensemble fini d’instructions qui transforment une entr´ ee du ruban en une
autre entr´ ee du ruban.
Ici, les instructions transformeront des chaˆ ınes d’ADN en d’autres chaˆ ınes d’ADN.
Un des mod` eles les plus connus de calcul par ordinateur ` a ADN est celui de l’insertion–
d´ el´ etion. L’id´ ee est d’utiliser des enzymes pour effectuer deux types d’op´ erations :
• l’op´ eration de d´ el´ etion qui consiste ` a retirer une sous-chaˆ ıne d’ADN d´ etermin´ ee ` a
un endroit prescrit par des marqueurs ;
• l’op´ eration d’insertion qui consiste `
a ins´ erer une sous-chaˆ ıne d´ etermin´ ee dans une
autre `
a un endroit prescrit par des marqueurs.
Voyons maintenant comment on peut d´ ecrire l’insertion et la d´ el´ etion de mani` ere
rigoureuse. Nous dirons par la suite que l’insertion et la d´ el´ etion sont deux r` egles de
production.
D´ efinition 13.41 1. Insertion. Si x = x 1 x 2 est une portion d’un mot z = v 1 xv 2 dans
X
∗ , on peut ins´ erer une chaˆ ıne u ∈ X
∗ entre x 1 et x 2 , ce qui donne le mot w = v 1 yv 2
o` u y = x 1 ux 2 . Pour all´ eger la notation, on ´ ecrit l’op´ eration sous la forme simplifi´ ee
x =⇒ I y
et on dit que y d´ erive de x par la loi de production de l’insertion. (Il est sousentendu que x et y peuvent ˆ etre des parties de mots plus longs.) Cette loi est
repr´ esent´ ee par le triplet (x 1 , u, x 2 ) I .
2. D´ el´ etion. Si x = x 1 ux 2 est une portion d’un mot z = v 1 xv 2 dans X
∗ , on peut
retrancher la chaˆ ıne u, ce qui donne le mot w = v 1 yv 2 o` u y = x 1 x 2 . On ´ ecrit encore
une fois
439
13.4 Les machines de Turing et les syst` emes
d’insertion–d´ el´ etion de l’ordinateur ` a ADN
Nous avons vu comment une machine de Turing peut ex´ ecuter un programme.
Construisons de la mˆ eme mani` ere un ordinateur `
a ADN. Comme pour les machines
de Turing, nous aurons besoin d’un alphabet X constitu´ e d’un ensemble fini de symboles. Pour un ordinateur `
a ADN, l’alphabet naturel est bien sˆ ur constitu´ e des quatre
bases azot´ ees. Nous aurons donc
X = {A, C, G, T }.
Cet alphabet peut sembler restreint, mais rappelons que les ordinateurs conventionnels
ne disposent que d’un alphabet binaire compos´ e du 0 et du 1.
On construit alors des chaˆ ınes avec les symboles de cet alphabet et on d´ efinit X
∗
comme l’ensemble des chaˆ ınes finies qu’il est possible de construire par la m´ ethode de
la d´ efinition 13.3. Dans le cas de l’ADN, X
∗ repr´ esente donc l’ensemble des chaˆ ınes
simples d’ADN de longueur finie pouvant ˆ etre construites avec les quatre bases azot´ ees,
plus la chaˆ ıne nulle.
Dans une machine de Turing, les mots sont les entr´ ees du ruban. La machine de
Turing a un ensemble fini d’instructions qui transforment une entr´ ee du ruban en une
autre entr´ ee du ruban.
Ici, les instructions transformeront des chaˆ ınes d’ADN en d’autres chaˆ ınes d’ADN.
Un des mod` eles les plus connus de calcul par ordinateur ` a ADN est celui de l’insertion–
d´ el´ etion. L’id´ ee est d’utiliser des enzymes pour effectuer deux types d’op´ erations :
• l’op´ eration de d´ el´ etion qui consiste ` a retirer une sous-chaˆ ıne d’ADN d´ etermin´ ee ` a
un endroit prescrit par des marqueurs ;
• l’op´ eration d’insertion qui consiste `
a ins´ erer une sous-chaˆ ıne d´ etermin´ ee dans une
autre `
a un endroit prescrit par des marqueurs.
Voyons maintenant comment on peut d´ ecrire l’insertion et la d´ el´ etion de mani` ere
rigoureuse. Nous dirons par la suite que l’insertion et la d´ el´ etion sont deux r` egles de
production.
D´ efinition 13.41 1. Insertion. Si x = x 1 x 2 est une portion d’un mot z = v 1 xv 2 dans
X
∗ , on peut ins´ erer une chaˆ ıne u ∈ X
∗ entre x 1 et x 2 , ce qui donne le mot w = v 1 yv 2
o` u y = x 1 ux 2 . Pour all´ eger la notation, on ´ ecrit l’op´ eration sous la forme simplifi´ ee
x =⇒ I y
et on dit que y d´ erive de x par la loi de production de l’insertion. (Il est sousentendu que x et y peuvent ˆ etre des parties de mots plus longs.) Cette loi est
repr´ esent´ ee par le triplet (x 1 , u, x 2 ) I .
2. D´ el´ etion. Si x = x 1 ux 2 est une portion d’un mot z = v 1 xv 2 dans X
∗ , on peut
retrancher la chaˆ ıne u, ce qui donne le mot w = v 1 yv 2 o` u y = x 1 x 2 . On ´ ecrit encore
une fois