442
13 L’ordinateur ` a ADN
Plus tard, nous devrons effectuer une instruction (q j , x j ) → (q k , x k , c). Il faut
empˆ echer le syst` eme de commencer ` a effectuer cette op´ eration avant d’avoir effac´ e q i x i . La pr´ esence du O interm´ ediaire l’empˆ eche de reconnaˆ ıtre la chaˆ ıne q j x j
avant que la chaˆ ıne q i x i n’ait ´ et´ e effac´ ee.
2. Pour toutes les r` egles de la forme (q i , x i ) → (q j , x j , 1), nous devons ajouter
` a ID les six r` egles suivantes : (q i x i , q
i Ox j , ν) I , (μ, q i x i , q
i Ox j ) D , (ρσq
i , O, x j ) D ,
(q
i x j , q j R, ν) I , (μ, q
i , x j q j R) D , (τx j q j , R, ν) D , pour tous les μ, ν, ρ, σ, τ ∈ X.
Nous pouvons alors effectuer les op´ erations suivantes sur une chaˆ ıne de la forme
μq i x i ν :
μq i x i ν =⇒ I μq i x i q
i Ox j ν =⇒ D μq
i Ox j ν =⇒ D μq
i x j ν
=⇒ I μq
i x j q j Rν =⇒ D μx j q j Rν =⇒ D μx j q j ν.
On voit ici que les trois premi` eres op´ erations sont une r´ ep´ etition de celles que nous
avons ajout´ ees pour l’ex´ ecution des r` egles de la forme (q i , x i ) → (q j , x j , 0). Ces trois
op´ erations, une insertion et deux d´ el´ etions, permettent en effet de changer x i en x j
sans d´ eplacer la position du pointeur. On utilise un ´ etat artificiel q
i pour signifier
qu’on n’a pas termin´ e l’ex´ ecution de la commande de la machine de Turing. Les trois
op´ erations suivantes permettent de d´ eplacer le pointeur vers la droite et d’amener
celui-ci ` a l’´ etat q j d´ esir´ e. La machine est alors en position d’effectuer une commande
(q j , ν) → (q k , x k , c), c ∈ {−1, 0, 1}, si une telle commande existe.
Ici encore, on a recours aux symboles artificiels O et R et q
i pour forcer les insertions
et les d´ el´ etions ` a s’effectuer dans l’ordre exact qu’on a choisi. Par exemple, la r` egle
(ρσq
i , O, x j ) D est construite pour qu’on ne puisse pas enlever le O dans μq i x i q
i Ox j ν
avant d’avoir d’abord enlev´ e q i x i . En effet, dans μq i x i q
i Ox j ν, l’´ etat artificiel q
i n’est
pr´ ec´ ed´ e que d’un symbole de X, soit x i , lequel est pr´ ec´ ed´ e d’un ´ etat. On ne peut
enlever O que quand q
i est pr´ ec´ ed´ e de deux symboles de X (l’un d’eux pouvant ˆ etre
le symbole B). Nous laissons le lecteur se convaincre de l’utilit´ e des autres r` egles de
production.
3. Pour toutes les r` egles de la forme (q i , x i ) → (q j , x j , −1), nous devons ajouter `
a ID
les six r` egles suivantes : (q i x i , q
i Ox j , ν) I , (μ 2 , q i x i , q
i Ox j ) D , (ρσq
i , O, x j ) D ,
(μ 1 , q j L, μ 2 q
i x j ) I , (q j Lμ 2 , q
i , x j ) D , (q j , L, μ 2 x j ) D pour tous μ 1 , μ 2 , ν, ρ, σ ∈ X.
Nous pouvons alors effectuer les op´ erations suivantes sur une chaˆ ıne de la forme
μ 1 μ 2 q i x i ν :
μ 1 μ 2 q i x i ν =⇒ I μ 1 μ 2 q i x i q
i Ox j ν =⇒ D μ 1 μ 2 q
i Ox j ν
=⇒ D μ 1 μ 2 q
i x j ν =⇒ I μ 1 q j Lμ 2 q
i x j ν =⇒ D μ 1 q j Lμ 2 x j ν =⇒ D μ 1 q j μ 2 x j ν.
Et donc, toutes les commandes (q j , ν) → (q k , x k , c), c ∈ {−1, 0, 1}, peuvent ˆ etre
effectu´ ees par un syst` eme d’insertion–d´ el´ etion.
Ce th´ eor` eme montre qu’un syst` eme d’insertion–d´ el´ etion a au moins le mˆ eme pouvoir
th´ eorique de calcul qu’une machine de Turing : tout probl` eme r´ esoluble par une machine
13 L’ordinateur ` a ADN
Plus tard, nous devrons effectuer une instruction (q j , x j ) → (q k , x k , c). Il faut
empˆ echer le syst` eme de commencer ` a effectuer cette op´ eration avant d’avoir effac´ e q i x i . La pr´ esence du O interm´ ediaire l’empˆ eche de reconnaˆ ıtre la chaˆ ıne q j x j
avant que la chaˆ ıne q i x i n’ait ´ et´ e effac´ ee.
2. Pour toutes les r` egles de la forme (q i , x i ) → (q j , x j , 1), nous devons ajouter
` a ID les six r` egles suivantes : (q i x i , q
i Ox j , ν) I , (μ, q i x i , q
i Ox j ) D , (ρσq
i , O, x j ) D ,
(q
i x j , q j R, ν) I , (μ, q
i , x j q j R) D , (τx j q j , R, ν) D , pour tous les μ, ν, ρ, σ, τ ∈ X.
Nous pouvons alors effectuer les op´ erations suivantes sur une chaˆ ıne de la forme
μq i x i ν :
μq i x i ν =⇒ I μq i x i q
i Ox j ν =⇒ D μq
i Ox j ν =⇒ D μq
i x j ν
=⇒ I μq
i x j q j Rν =⇒ D μx j q j Rν =⇒ D μx j q j ν.
On voit ici que les trois premi` eres op´ erations sont une r´ ep´ etition de celles que nous
avons ajout´ ees pour l’ex´ ecution des r` egles de la forme (q i , x i ) → (q j , x j , 0). Ces trois
op´ erations, une insertion et deux d´ el´ etions, permettent en effet de changer x i en x j
sans d´ eplacer la position du pointeur. On utilise un ´ etat artificiel q
i pour signifier
qu’on n’a pas termin´ e l’ex´ ecution de la commande de la machine de Turing. Les trois
op´ erations suivantes permettent de d´ eplacer le pointeur vers la droite et d’amener
celui-ci ` a l’´ etat q j d´ esir´ e. La machine est alors en position d’effectuer une commande
(q j , ν) → (q k , x k , c), c ∈ {−1, 0, 1}, si une telle commande existe.
Ici encore, on a recours aux symboles artificiels O et R et q
i pour forcer les insertions
et les d´ el´ etions ` a s’effectuer dans l’ordre exact qu’on a choisi. Par exemple, la r` egle
(ρσq
i , O, x j ) D est construite pour qu’on ne puisse pas enlever le O dans μq i x i q
i Ox j ν
avant d’avoir d’abord enlev´ e q i x i . En effet, dans μq i x i q
i Ox j ν, l’´ etat artificiel q
i n’est
pr´ ec´ ed´ e que d’un symbole de X, soit x i , lequel est pr´ ec´ ed´ e d’un ´ etat. On ne peut
enlever O que quand q
i est pr´ ec´ ed´ e de deux symboles de X (l’un d’eux pouvant ˆ etre
le symbole B). Nous laissons le lecteur se convaincre de l’utilit´ e des autres r` egles de
production.
3. Pour toutes les r` egles de la forme (q i , x i ) → (q j , x j , −1), nous devons ajouter `
a ID
les six r` egles suivantes : (q i x i , q
i Ox j , ν) I , (μ 2 , q i x i , q
i Ox j ) D , (ρσq
i , O, x j ) D ,
(μ 1 , q j L, μ 2 q
i x j ) I , (q j Lμ 2 , q
i , x j ) D , (q j , L, μ 2 x j ) D pour tous μ 1 , μ 2 , ν, ρ, σ ∈ X.
Nous pouvons alors effectuer les op´ erations suivantes sur une chaˆ ıne de la forme
μ 1 μ 2 q i x i ν :
μ 1 μ 2 q i x i ν =⇒ I μ 1 μ 2 q i x i q
i Ox j ν =⇒ D μ 1 μ 2 q
i Ox j ν
=⇒ D μ 1 μ 2 q
i x j ν =⇒ I μ 1 q j Lμ 2 q
i x j ν =⇒ D μ 1 q j Lμ 2 x j ν =⇒ D μ 1 q j μ 2 x j ν.
Et donc, toutes les commandes (q j , ν) → (q k , x k , c), c ∈ {−1, 0, 1}, peuvent ˆ etre
effectu´ ees par un syst` eme d’insertion–d´ el´ etion.
Ce th´ eor` eme montre qu’un syst` eme d’insertion–d´ el´ etion a au moins le mˆ eme pouvoir
th´ eorique de calcul qu’une machine de Turing : tout probl` eme r´ esoluble par une machine