13.6 Retour sur les ordinateurs ` a ADN
447
a
1
1 v 1 . Les chaˆ ınes qui codent des chemins du graphe o` u x 1 = 1 sont alors attir´ ees par
leurs compl´ ements tandis que les chaˆ ınes qui ne repr´ esentent pas des solutions restent
en suspension dans l’´ eprouvette.
On attire alors les billes de fer au bord de l’´ eprouvette ` a l’aide d’un aimant, ce qui
plaque les chaˆ ınes qui y sont attach´ ees contre la paroi, et on vide les autres chaˆ ınes dans
une autre ´ eprouvette (´ eprouvette B). Ensuite, on remet les chaˆ ınes accroch´ ees aux billes
de fer (celles qui codent des chemins o` u x 1 = 1) en suspension dans l’´ eprouvette A.
Pour que x 1 ∨ x 2 ait la valeur 1, il se peut aussi que x 2 ait la valeur 1 et x 1 , la
valeur 0. Il faut donc transvaser dans l’´ eprouvette A toutes les chaˆ ınes de l’´ eprouvette
B pour lesquelles la valeur de x 2 est 1. Pour ce faire, on extrait ces chaˆ ınes d’ADN de
l’´ eprouvette B en utilisant la m´ ethode des billes de fer, et on ajoute les chaˆ ınes ainsi
isol´ ees ` a l’´ eprouvette A. On peut d´ ej` a jeter le contenu de l’´ eprouvette B.
L’´ eprouvette A contient `
a pr´ esent toutes les chaˆ ınes qui donnent la valeur de v´ erit´ e
1 `
a la proposition C 1 . Reste ` a extraire de l’´ eprouvette A toutes les solutions qui correspondent ` a la valeur de v´ erit´ e 1 de C 2 , car pour que C 1 ∧ C 2 soit vrai, il faut `
a la fois
que C 1 soit vrai et que C 2 soit vrai : on ne peut donc trouver des solutions que dans
l’´ eprouvette A.
Dans notre exemple, C 2 = ¬x 3 . Il faut donc extraire de l’´ eprouvette A toutes les
chaˆ ınes o` u la valeur de x 3 est 0. Ainsi, il ne restera dans l’´ eprouvette que les chaˆ ınes
v´ erifiant chacun des C i et, par cons´ equent, la conjonction de ces C i .
On peut se demander en quoi les manipulations de l‘ADN peuvent aider `
a r´ esoudre
le probl` eme une fois que l’´ equation logique est sous la forme conjonctive normale. Supposons que α = C 1 ∧ C 2 ∧ C 3 ∧ · · · ∧ C m et que les C i sont form´ es de n variables x j et de
leurs n´ egations ¬x j (toutes les variables n’apparaissent pas n´ ecessairement dans chaque
C i ). On a donc 2
n chemins possibles dans le graphe. Par contre, comme on l’a vu, on a
au plus n v´ erifications `
a faire pour chacun des C i , soit au plus mn v´ erifications. Donc,
la m´ ethode propos´ ee est une am´ elioration par rapport `
a l’exploration syst´ ematique de
tous les chemins, sauf si m est tr` es grand par rapport ` a n.
13.6 Retour sur les ordinateurs ` a ADN
13.6.1 Probl` eme du chemin hamiltonien et insertion–d´ el´ etion
Nous avons montr´ e ` a la section 13.4 qu’un ordinateur ` a ADN peut calculer toute
fonction r´ ecursive en utilisant des insertions et des d´ el´ etions, et pourtant, la solution
d’Adleman au probl` eme du chemin hamiltonien ne fait appel ` a aucune insertion ou
d´ el´ etion.
Comme nous l’avons mentionn´ e dans l’introduction, les algorithmes de la th´ eorie des
fonctions r´ ecursives sont souvent loin d’ˆ etre les meilleurs. C’est ´ egalement le cas pour
les machines de Turing. Consid´ erons la fonction add(m, n) = m + n. Comme c’est une
fonction primitive-r´ ecursive, la preuve du th´ eor` eme 13.31 nous fournit un moyen de la
447
a
1
1 v 1 . Les chaˆ ınes qui codent des chemins du graphe o` u x 1 = 1 sont alors attir´ ees par
leurs compl´ ements tandis que les chaˆ ınes qui ne repr´ esentent pas des solutions restent
en suspension dans l’´ eprouvette.
On attire alors les billes de fer au bord de l’´ eprouvette ` a l’aide d’un aimant, ce qui
plaque les chaˆ ınes qui y sont attach´ ees contre la paroi, et on vide les autres chaˆ ınes dans
une autre ´ eprouvette (´ eprouvette B). Ensuite, on remet les chaˆ ınes accroch´ ees aux billes
de fer (celles qui codent des chemins o` u x 1 = 1) en suspension dans l’´ eprouvette A.
Pour que x 1 ∨ x 2 ait la valeur 1, il se peut aussi que x 2 ait la valeur 1 et x 1 , la
valeur 0. Il faut donc transvaser dans l’´ eprouvette A toutes les chaˆ ınes de l’´ eprouvette
B pour lesquelles la valeur de x 2 est 1. Pour ce faire, on extrait ces chaˆ ınes d’ADN de
l’´ eprouvette B en utilisant la m´ ethode des billes de fer, et on ajoute les chaˆ ınes ainsi
isol´ ees ` a l’´ eprouvette A. On peut d´ ej` a jeter le contenu de l’´ eprouvette B.
L’´ eprouvette A contient `
a pr´ esent toutes les chaˆ ınes qui donnent la valeur de v´ erit´ e
1 `
a la proposition C 1 . Reste ` a extraire de l’´ eprouvette A toutes les solutions qui correspondent ` a la valeur de v´ erit´ e 1 de C 2 , car pour que C 1 ∧ C 2 soit vrai, il faut `
a la fois
que C 1 soit vrai et que C 2 soit vrai : on ne peut donc trouver des solutions que dans
l’´ eprouvette A.
Dans notre exemple, C 2 = ¬x 3 . Il faut donc extraire de l’´ eprouvette A toutes les
chaˆ ınes o` u la valeur de x 3 est 0. Ainsi, il ne restera dans l’´ eprouvette que les chaˆ ınes
v´ erifiant chacun des C i et, par cons´ equent, la conjonction de ces C i .
On peut se demander en quoi les manipulations de l‘ADN peuvent aider `
a r´ esoudre
le probl` eme une fois que l’´ equation logique est sous la forme conjonctive normale. Supposons que α = C 1 ∧ C 2 ∧ C 3 ∧ · · · ∧ C m et que les C i sont form´ es de n variables x j et de
leurs n´ egations ¬x j (toutes les variables n’apparaissent pas n´ ecessairement dans chaque
C i ). On a donc 2
n chemins possibles dans le graphe. Par contre, comme on l’a vu, on a
au plus n v´ erifications `
a faire pour chacun des C i , soit au plus mn v´ erifications. Donc,
la m´ ethode propos´ ee est une am´ elioration par rapport `
a l’exploration syst´ ematique de
tous les chemins, sauf si m est tr` es grand par rapport ` a n.
13.6 Retour sur les ordinateurs ` a ADN
13.6.1 Probl` eme du chemin hamiltonien et insertion–d´ el´ etion
Nous avons montr´ e ` a la section 13.4 qu’un ordinateur ` a ADN peut calculer toute
fonction r´ ecursive en utilisant des insertions et des d´ el´ etions, et pourtant, la solution
d’Adleman au probl` eme du chemin hamiltonien ne fait appel ` a aucune insertion ou
d´ el´ etion.
Comme nous l’avons mentionn´ e dans l’introduction, les algorithmes de la th´ eorie des
fonctions r´ ecursives sont souvent loin d’ˆ etre les meilleurs. C’est ´ egalement le cas pour
les machines de Turing. Consid´ erons la fonction add(m, n) = m + n. Comme c’est une
fonction primitive-r´ ecursive, la preuve du th´ eor` eme 13.31 nous fournit un moyen de la