438
13 L’ordinateur ` a ADN
3. On copie les entr´ ees et j ` a la droite des valeurs d´ ej` a pr´ esentes sur le ruban. On
obtient alors la configuration suivante :
Bx 1 Bx 2 B . . . Bx n BjBx 1 Bx 2 B . . . Bx n BjB.
4. La machine Π est appliqu´ ee ` a la copie des entr´ ees et de j, ce qui nous permet
d’obtenir
Bx 1 Bx 2 B . . . Bx n BjBp(x 1 , . . . , x n , j)B.
5. Si p(x 1 , . . . , x n , j) = 1, alors f (x 1 , . . . , x n ) = j, et on efface toutes les autres entr´ ees.
Sinon la valeur de p(x 1 , . . . , x n , j) est effac´ ee, et la fonction successeur est appliqu´ ee
` a l’indice de minimalisation. On reprend alors les ´ etapes 3 `
a 5.
Si la fonction f (x 1 , . . . , x n ) est d´ efinie, alors on obtient la valeur recherch´ ee. Dans
le cas contraire, la machine continue ses calculs ind´ efiniment, ce qui correspond `
a la
d´ efinition pr´ ec´ edemment ´ enonc´ ee de la MT-calculabilit´ e (d´ efinition 13.5).
Ce th´ eor` eme montre qu’un grand nombre de fonctions sont calculables par une
machine de Turing. En fait, la relation entre les machines de Turing et les fonctions
r´ ecursives est encore plus forte, comme l’indique le th´ eor` eme suivant que nous ne
d´ emontrerons pas.
Th´ eor` eme 13.40 [8] Une fonction est MT-calculable si et seulement si elle est r´ ecursive.
Nous allons maintenant introduire la th` ese de Church-Turing qui fait le lien entre
« calculabilit´ e » et MT-calculabilit´ e. Cette th` ese peut prendre plusieurs formes, mais,
toutes ces formes s’´ etant av´ er´ ees ´ equivalentes, nous retenons celle qui a un lien avec le
th´ eor` eme ci-dessus.
Th` ese de Church Une fonction partielle est « calculable » si et seulement si elle est
r´ ecursive.
Ainsi, d’apr` es cette th` ese, toutes les fonctions « calculables » seraient MT-calculables.
On en vient mˆ eme ` a accepter la d´ efinition suivante de calculabilit´ e comme ´ etant : une
fonction est calculable s’il existe une machine de Turing qui peut la calculer.
Le probl` eme, c’est qu’il est impossible de « d´ emontrer » cette th` ese tant qu’on n’a
pas de d´ efinition math´ ematique de « calculabilit´ e ». Il serait possible de l’infirmer en
trouvant une fonction qui soit calculable par un algorithme pr´ ecis, mais qu’aucune
machine de Turing ne puisse calculer. Cependant, la notion d’« algorithme » n’est pas
assez claire pour qu’on puisse prouver que, si un algorithme existe pour calculer une
fonction, alors elle est MT-calculable. Il est toutefois int´ eressant de noter que toutes les
tentatives faites pour d´ efinir la notion d’algorithme tendent `
a valider la th` ese de Church
puisqu’` a chaque tentative, on arrive toujours `
a calculer exactement les fonctions MTcalculables.
13 L’ordinateur ` a ADN
3. On copie les entr´ ees et j ` a la droite des valeurs d´ ej` a pr´ esentes sur le ruban. On
obtient alors la configuration suivante :
Bx 1 Bx 2 B . . . Bx n BjBx 1 Bx 2 B . . . Bx n BjB.
4. La machine Π est appliqu´ ee ` a la copie des entr´ ees et de j, ce qui nous permet
d’obtenir
Bx 1 Bx 2 B . . . Bx n BjBp(x 1 , . . . , x n , j)B.
5. Si p(x 1 , . . . , x n , j) = 1, alors f (x 1 , . . . , x n ) = j, et on efface toutes les autres entr´ ees.
Sinon la valeur de p(x 1 , . . . , x n , j) est effac´ ee, et la fonction successeur est appliqu´ ee
` a l’indice de minimalisation. On reprend alors les ´ etapes 3 `
a 5.
Si la fonction f (x 1 , . . . , x n ) est d´ efinie, alors on obtient la valeur recherch´ ee. Dans
le cas contraire, la machine continue ses calculs ind´ efiniment, ce qui correspond `
a la
d´ efinition pr´ ec´ edemment ´ enonc´ ee de la MT-calculabilit´ e (d´ efinition 13.5).
Ce th´ eor` eme montre qu’un grand nombre de fonctions sont calculables par une
machine de Turing. En fait, la relation entre les machines de Turing et les fonctions
r´ ecursives est encore plus forte, comme l’indique le th´ eor` eme suivant que nous ne
d´ emontrerons pas.
Th´ eor` eme 13.40 [8] Une fonction est MT-calculable si et seulement si elle est r´ ecursive.
Nous allons maintenant introduire la th` ese de Church-Turing qui fait le lien entre
« calculabilit´ e » et MT-calculabilit´ e. Cette th` ese peut prendre plusieurs formes, mais,
toutes ces formes s’´ etant av´ er´ ees ´ equivalentes, nous retenons celle qui a un lien avec le
th´ eor` eme ci-dessus.
Th` ese de Church Une fonction partielle est « calculable » si et seulement si elle est
r´ ecursive.
Ainsi, d’apr` es cette th` ese, toutes les fonctions « calculables » seraient MT-calculables.
On en vient mˆ eme ` a accepter la d´ efinition suivante de calculabilit´ e comme ´ etant : une
fonction est calculable s’il existe une machine de Turing qui peut la calculer.
Le probl` eme, c’est qu’il est impossible de « d´ emontrer » cette th` ese tant qu’on n’a
pas de d´ efinition math´ ematique de « calculabilit´ e ». Il serait possible de l’infirmer en
trouvant une fonction qui soit calculable par un algorithme pr´ ecis, mais qu’aucune
machine de Turing ne puisse calculer. Cependant, la notion d’« algorithme » n’est pas
assez claire pour qu’on puisse prouver que, si un algorithme existe pour calculer une
fonction, alors elle est MT-calculable. Il est toutefois int´ eressant de noter que toutes les
tentatives faites pour d´ efinir la notion d’algorithme tendent `
a valider la th` ese de Church
puisqu’` a chaque tentative, on arrive toujours `
a calculer exactement les fonctions MTcalculables.