416
13 L’ordinateur ` a ADN
13.1 Introduction
Le sujet que nous pr´ esentons dans ce chapitre est en plein d´ eveloppement. L’ordinateur `
a ADN est encore du domaine de la fiction, mˆ eme s’il a d´ ej` a ´ et´ e utilis´ e afin de
r´ esoudre un probl` eme math´ ematique. La recherche sur le sujet est intense et r´ eunit des
´ equipes multidisciplinaires : informaticiens th´ eoriciens et biochimistes.
Faisons le parall` ele avec le d´ eveloppement de l’ordinateur classique. Il a commenc´ e lorsqu’on s’est rendu compte que des circuits ´ electriques pouvaient effectuer des
op´ erations. (Des exemples simples sont trait´ es ` a la section 15.7 du chapitre 15.) Les ordinateurs modernes sont des agencements d’un grand nombre de transistors. Au temps
des premiers ordinateurs, la programmation impliquait de comprendre le fonctionnement interne de l’ordinateur pour pouvoir d´ ecomposer le programme ` a ex´ ecuter en une
suite d’op´ erations ex´ ecutables par des circuits ´ electriques. Des raffinements sont ensuite
apparus dans plusieurs directions. Grˆ ace ` a ces progr` es, il est devenu de moins en moins
important de comprendre le fonctionnement interne d’un ordinateur pour en utiliser un.
On s’est alors pos´ e la question de savoir quelles questions ´ etaient r´ esolubles par un
ordinateur. Pour pouvoir y r´ epondre, il faut d´ efinir ce qu’est un « algorithme » et ce
qu’est un « ordinateur ». Les deux questions sont difficiles, quasi philosophiques. Plutˆ ot
que de parler d’algorithme, on parle souvent de fonctions « calculables ». Toutes les
approches de la calculabilit´ e ont conduit `
a des d´ efinitions ´ equivalentes. En particulier,
si on se limite aux fonctions f : N
n
→ N, les fonctions calculables sont les fonctions
r´ ecursives dont nous parlerons en d´ etail `
a la section 13.3.2. Faute de pouvoir imaginer
les ordinateurs complexes de l’avenir, on s’est pench´ e sur l’ordinateur le plus simple
que l’on puisse imaginer, soit la machine de Turing d´ ecrite ` a la section 13.3. Le grand
th´ eor` eme du sujet d´ emontre qu’une fonction f : N
n
→ N est r´ ecursive si et seulement
si elle est calculable par une machine de Turing (voir le th´ eor` eme 13.40 ci-dessous, qui
pr´ esente une des deux directions). Ceci a amen´ e Church `
a formuler sa fameuse th` ese,
` a savoir qu’une fonction est « calculable » si et seulement si elle est calculable par une
machine de Turing.
La th´ eorie pr´ ec´ edente donne une m´ ethode pour programmer le calcul de toute fonction r´ ecursive. Par contre, c’est souvent loin d’ˆ etre la solution la plus ´ el´ egante ou encore
la plus rapide. Lorsqu’on s’int´ eresse ` a la solution num´ erique d’un probl` eme, les algorithmes th´ eoriques dont on vient de parler ne sont d’aucune utilit´ e, et les algorithmes
retenus sont souvent tr` es loin de ces algorithmes th´ eoriques. Beaucoup de probl` emes
qui s’´ enoncent simplement tiennent encore en ´ echec les meilleurs ordinateurs. C’est le
cas de la factorisation de grands nombres entiers examin´ ee au chapitre 7 ou encore, du
probl` eme du chemin hamiltonien expos´ e ci-dessous : dans ce probl` eme, on se donne un
certain nombre de villes et de chemins orient´ es reliant certaines paires de villes et on
cherche s’il existe un itin´ eraire partant de la premi` ere ville, passant par chacune des
villes exactement une fois et se terminant `
a la derni` ere. Lorsque le nombre de villes est
assez grand (plus d’une centaine), le nombre de possibilit´ es ` a explorer devient trop grand
pour qu’un ordinateur, mˆ eme puissant, puisse en trouver la solution en explorant toutes
les possibilit´ es. Pour am´ eliorer la performance, les chercheurs s’emploient ` a trouver de
13 L’ordinateur ` a ADN
13.1 Introduction
Le sujet que nous pr´ esentons dans ce chapitre est en plein d´ eveloppement. L’ordinateur `
a ADN est encore du domaine de la fiction, mˆ eme s’il a d´ ej` a ´ et´ e utilis´ e afin de
r´ esoudre un probl` eme math´ ematique. La recherche sur le sujet est intense et r´ eunit des
´ equipes multidisciplinaires : informaticiens th´ eoriciens et biochimistes.
Faisons le parall` ele avec le d´ eveloppement de l’ordinateur classique. Il a commenc´ e lorsqu’on s’est rendu compte que des circuits ´ electriques pouvaient effectuer des
op´ erations. (Des exemples simples sont trait´ es ` a la section 15.7 du chapitre 15.) Les ordinateurs modernes sont des agencements d’un grand nombre de transistors. Au temps
des premiers ordinateurs, la programmation impliquait de comprendre le fonctionnement interne de l’ordinateur pour pouvoir d´ ecomposer le programme ` a ex´ ecuter en une
suite d’op´ erations ex´ ecutables par des circuits ´ electriques. Des raffinements sont ensuite
apparus dans plusieurs directions. Grˆ ace ` a ces progr` es, il est devenu de moins en moins
important de comprendre le fonctionnement interne d’un ordinateur pour en utiliser un.
On s’est alors pos´ e la question de savoir quelles questions ´ etaient r´ esolubles par un
ordinateur. Pour pouvoir y r´ epondre, il faut d´ efinir ce qu’est un « algorithme » et ce
qu’est un « ordinateur ». Les deux questions sont difficiles, quasi philosophiques. Plutˆ ot
que de parler d’algorithme, on parle souvent de fonctions « calculables ». Toutes les
approches de la calculabilit´ e ont conduit `
a des d´ efinitions ´ equivalentes. En particulier,
si on se limite aux fonctions f : N
n
→ N, les fonctions calculables sont les fonctions
r´ ecursives dont nous parlerons en d´ etail `
a la section 13.3.2. Faute de pouvoir imaginer
les ordinateurs complexes de l’avenir, on s’est pench´ e sur l’ordinateur le plus simple
que l’on puisse imaginer, soit la machine de Turing d´ ecrite ` a la section 13.3. Le grand
th´ eor` eme du sujet d´ emontre qu’une fonction f : N
n
→ N est r´ ecursive si et seulement
si elle est calculable par une machine de Turing (voir le th´ eor` eme 13.40 ci-dessous, qui
pr´ esente une des deux directions). Ceci a amen´ e Church `
a formuler sa fameuse th` ese,
` a savoir qu’une fonction est « calculable » si et seulement si elle est calculable par une
machine de Turing.
La th´ eorie pr´ ec´ edente donne une m´ ethode pour programmer le calcul de toute fonction r´ ecursive. Par contre, c’est souvent loin d’ˆ etre la solution la plus ´ el´ egante ou encore
la plus rapide. Lorsqu’on s’int´ eresse ` a la solution num´ erique d’un probl` eme, les algorithmes th´ eoriques dont on vient de parler ne sont d’aucune utilit´ e, et les algorithmes
retenus sont souvent tr` es loin de ces algorithmes th´ eoriques. Beaucoup de probl` emes
qui s’´ enoncent simplement tiennent encore en ´ echec les meilleurs ordinateurs. C’est le
cas de la factorisation de grands nombres entiers examin´ ee au chapitre 7 ou encore, du
probl` eme du chemin hamiltonien expos´ e ci-dessous : dans ce probl` eme, on se donne un
certain nombre de villes et de chemins orient´ es reliant certaines paires de villes et on
cherche s’il existe un itin´ eraire partant de la premi` ere ville, passant par chacune des
villes exactement une fois et se terminant `
a la derni` ere. Lorsque le nombre de villes est
assez grand (plus d’une centaine), le nombre de possibilit´ es ` a explorer devient trop grand
pour qu’un ordinateur, mˆ eme puissant, puisse en trouver la solution en explorant toutes
les possibilit´ es. Pour am´ eliorer la performance, les chercheurs s’emploient ` a trouver de