13
L’ordinateur ` a ADN
1
L’essentiel du chapitre peut se traiter presque compl` etement en deux semaines de cours.
Il est cependant possible de ne consacrer qu’une semaine ` a ce chapitre. Dans ce dernier cas, et avec des ´ etudiants ayant un bagage plutˆ ot math´ ematique, on construit les
fonctions r´ ecursives ` a partir des fonctions de base et des op´ erations de composition,
r´ ecurrence et minimalisation. On explique le fonctionnement d’une machine de Turing
et on montre par des exemples comment construire les machines de Turing calculant
certaines fonctions simples (section 13.3). On ´ enonce sans preuve le th´ eor` eme 13.39,
` a savoir que toute fonction r´ ecursive est Turing-calculable. Ici, on a le choix : on peut
d´ ecider de pr´ esenter une partie de la preuve ou encore, passer directement ` a l’ordinateur `
a ADN. Dans ce dernier cas, on a seulement le temps de voir des op´ erations
biologiques possibles sur l’ADN et l’exemple du probl` eme du chemin hamiltonien r´ esolu
par Adleman (section 13.2).
Avec des ´ etudiants ayant un bagage plus informatique, il est int´ eressant de consacrer
deux semaines au chapitre. On privil´ egie la description des machines de Turing et on
fait au moins une ´ etape de la preuve des th´ eor` emes sur la nature Turing-calculable
de toute fonction r´ ecursive (th´ eor` emes 13.31 et 13.39). On introduit les syst` emes
d’insertion–d´ el´ etion (section 13.4) et on explique que les enzymes peuvent r´ ealiser des
insertions et des d´ el´ etions sur des brins d’ADN. On ´ enonce le th´ eor` eme 13.43 `
a savoir que, pour toute machine de Turing, il existe un syst` eme d’insertion–d´ el´ etion qui
ex´ ecute le mˆ eme programme, en insistant sur la signification du th´ eor` eme. On examine un des cas de la preuve. Si le temps ne le permet pas, on laisse tomber l’exemple
d’Adleman.
1 Ce chapitre a ´ et´ e ´ ecrit par H´ el` ene Antaya et Isabelle Ascah-Coallier pendant qu’elles
effectuaient un stage d’´ et´ e financ´ e par une bourse de recherche du premier cycle du CRSNG.
L’ordinateur ` a ADN
1
L’essentiel du chapitre peut se traiter presque compl` etement en deux semaines de cours.
Il est cependant possible de ne consacrer qu’une semaine ` a ce chapitre. Dans ce dernier cas, et avec des ´ etudiants ayant un bagage plutˆ ot math´ ematique, on construit les
fonctions r´ ecursives ` a partir des fonctions de base et des op´ erations de composition,
r´ ecurrence et minimalisation. On explique le fonctionnement d’une machine de Turing
et on montre par des exemples comment construire les machines de Turing calculant
certaines fonctions simples (section 13.3). On ´ enonce sans preuve le th´ eor` eme 13.39,
` a savoir que toute fonction r´ ecursive est Turing-calculable. Ici, on a le choix : on peut
d´ ecider de pr´ esenter une partie de la preuve ou encore, passer directement ` a l’ordinateur `
a ADN. Dans ce dernier cas, on a seulement le temps de voir des op´ erations
biologiques possibles sur l’ADN et l’exemple du probl` eme du chemin hamiltonien r´ esolu
par Adleman (section 13.2).
Avec des ´ etudiants ayant un bagage plus informatique, il est int´ eressant de consacrer
deux semaines au chapitre. On privil´ egie la description des machines de Turing et on
fait au moins une ´ etape de la preuve des th´ eor` emes sur la nature Turing-calculable
de toute fonction r´ ecursive (th´ eor` emes 13.31 et 13.39). On introduit les syst` emes
d’insertion–d´ el´ etion (section 13.4) et on explique que les enzymes peuvent r´ ealiser des
insertions et des d´ el´ etions sur des brins d’ADN. On ´ enonce le th´ eor` eme 13.43 `
a savoir que, pour toute machine de Turing, il existe un syst` eme d’insertion–d´ el´ etion qui
ex´ ecute le mˆ eme programme, en insistant sur la signification du th´ eor` eme. On examine un des cas de la preuve. Si le temps ne le permet pas, on laisse tomber l’exemple
d’Adleman.
1 Ce chapitre a ´ et´ e ´ ecrit par H´ el` ene Antaya et Isabelle Ascah-Coallier pendant qu’elles
effectuaient un stage d’´ et´ e financ´ e par une bourse de recherche du premier cycle du CRSNG.