440
13 L’ordinateur ` a ADN
x =⇒ D y
et on dit que y d´ erive de x par la loi de production de la d´ el´ etion. Cette loi est
repr´ esent´ ee par le triplet (x 1 , u, x 2 ) D .
Ainsi, les lois d’insertion et de d´ el´ etion peuvent ˆ etre trait´ ees comme des ´ el´ ements de
(X
∗ )
3 .
Notation On introduit alors la notation g´ en´ erale x =⇒ y pour dire que y a ´ et´ e
obtenu de x par une des lois de production. Si y a ´ et´ e obtenu par application `
a x de
plusieurs lois de production l’une apr` es l’autre, on utilise la notation
x =⇒
∗ y.
D´ efinition 13.42 Un syst` eme d’insertion–d´ el´ etion est un triplet
ID = (X, I, D),
o` u X est un alphabet, I est l’ensemble des r` egles d’insertion, et D est l’ensemble des
r` egles de d´ el´ etion. Dans le cas de l’ADN, l’alphabet X = {A, G, T, C} est constitu´ e des
quatre bases azot´ ees. I et D sont tous deux des sous-ensembles de (X
∗ )
3 .
Th´ eoriquement, ce mod` ele est tr` es efficace. En effet, nous allons prouver qu’on peut
calculer n’importe quelle fonction r´ ecursive et r´ esoudre n’importe quel probl` eme exprimable r´ ecursivement en utilisant l’insertion–d´ el´ etion. Cependant, il est souvent assez
difficile de trouver un algorithme pratique pour r´ esoudre des probl` emes math´ ematiques
` a l’aide d’une suite d’insertions et de d´ el´ etions.
Th´ eor` eme 13.43 [5] Pour chaque machine de Turing, il existe un syst` eme d’insertion–
d´ el´ etion qui ex´ ecute le mˆ eme programme.
Remarque Cet ´ enonc´ e est assez vague. Le donner rigoureusement requerrait d’introduire plusieurs notions difficiles de l’informatique th´ eorique comme les langages formels, les grammaires, etc. En langage courant, il signifie que, pour chaque machine
de Turing (que l’on peut identifier `
a un programme), on peut construire un syst` eme
d’insertion–d´ el´ etion qui effectue le programme, donc qui r´ ealise les instructions de la
machine de Turing. Pour qu’une machine de Turing effectue une op´ eration, il faut une
entr´ ee du ruban, l’´ etat de la machine et la position du pointeur. Aux triplets compos´ es
d’une entr´ ee du ruban, d’un ´ etat de la machine de Turing et de la position du pointeur, on fait correspondre une chaˆ ıne d’ADN. Une portion de la chaˆ ıne contient l’entr´ ee
du ruban, une autre l’information sur l’´ etat et une autre, la position du pointeur. La
preuve ci-dessous donne, pour chaque instruction de la machine de Turing, un ensemble
d’insertions et de d´ el´ etions transformant la chaˆ ıne correspondant ` a l’ancien triplet en
une chaˆ ıne correspondant au nouveau triplet. Cet ensemble d’insertions et de d´ el´ etions
doit donc transformer la portion de chaˆ ıne repr´ esentant l’entr´ ee du ruban pour qu’elle
corresponde ` a la nouvelle entr´ ee du ruban. Il doit aussi couper la portion de chaˆ ıne
13 L’ordinateur ` a ADN
x =⇒ D y
et on dit que y d´ erive de x par la loi de production de la d´ el´ etion. Cette loi est
repr´ esent´ ee par le triplet (x 1 , u, x 2 ) D .
Ainsi, les lois d’insertion et de d´ el´ etion peuvent ˆ etre trait´ ees comme des ´ el´ ements de
(X
∗ )
3 .
Notation On introduit alors la notation g´ en´ erale x =⇒ y pour dire que y a ´ et´ e
obtenu de x par une des lois de production. Si y a ´ et´ e obtenu par application `
a x de
plusieurs lois de production l’une apr` es l’autre, on utilise la notation
x =⇒
∗ y.
D´ efinition 13.42 Un syst` eme d’insertion–d´ el´ etion est un triplet
ID = (X, I, D),
o` u X est un alphabet, I est l’ensemble des r` egles d’insertion, et D est l’ensemble des
r` egles de d´ el´ etion. Dans le cas de l’ADN, l’alphabet X = {A, G, T, C} est constitu´ e des
quatre bases azot´ ees. I et D sont tous deux des sous-ensembles de (X
∗ )
3 .
Th´ eoriquement, ce mod` ele est tr` es efficace. En effet, nous allons prouver qu’on peut
calculer n’importe quelle fonction r´ ecursive et r´ esoudre n’importe quel probl` eme exprimable r´ ecursivement en utilisant l’insertion–d´ el´ etion. Cependant, il est souvent assez
difficile de trouver un algorithme pratique pour r´ esoudre des probl` emes math´ ematiques
` a l’aide d’une suite d’insertions et de d´ el´ etions.
Th´ eor` eme 13.43 [5] Pour chaque machine de Turing, il existe un syst` eme d’insertion–
d´ el´ etion qui ex´ ecute le mˆ eme programme.
Remarque Cet ´ enonc´ e est assez vague. Le donner rigoureusement requerrait d’introduire plusieurs notions difficiles de l’informatique th´ eorique comme les langages formels, les grammaires, etc. En langage courant, il signifie que, pour chaque machine
de Turing (que l’on peut identifier `
a un programme), on peut construire un syst` eme
d’insertion–d´ el´ etion qui effectue le programme, donc qui r´ ealise les instructions de la
machine de Turing. Pour qu’une machine de Turing effectue une op´ eration, il faut une
entr´ ee du ruban, l’´ etat de la machine et la position du pointeur. Aux triplets compos´ es
d’une entr´ ee du ruban, d’un ´ etat de la machine de Turing et de la position du pointeur, on fait correspondre une chaˆ ıne d’ADN. Une portion de la chaˆ ıne contient l’entr´ ee
du ruban, une autre l’information sur l’´ etat et une autre, la position du pointeur. La
preuve ci-dessous donne, pour chaque instruction de la machine de Turing, un ensemble
d’insertions et de d´ el´ etions transformant la chaˆ ıne correspondant ` a l’ancien triplet en
une chaˆ ıne correspondant au nouveau triplet. Cet ensemble d’insertions et de d´ el´ etions
doit donc transformer la portion de chaˆ ıne repr´ esentant l’entr´ ee du ruban pour qu’elle
corresponde ` a la nouvelle entr´ ee du ruban. Il doit aussi couper la portion de chaˆ ıne