436
13 L’ordinateur ` a ADN
D´ efinition 13.34 Soient P un pr´ edicat de (n + 1) variables et p = |P | sa fonction
valeur associ´ ee. L’expression μz[p(x 1 , . . . , x n , z)] repr´ esente le plus petit nombre naturel
z, s’il existe, tel que p(x 1 , . . . , x n , z) = 1, c’est-` a-dire tel que P (x 1 , . . . , x n , z) soit vrai.
Sinon, l’expression n’est pas d´ efinie. Cette construction s’appelle la minimalisation de
p, et μz est appel´ e l’op´ erateur μ.
Un pr´ edicat de (n + 1) variables permet de d´ efinir une fonction f de n variables,
f (x 1 , . . . , x n ) = μz[p(x 1 , . . . , x n , z)],
dont le domaine est l’ensemble des (x 1 , . . . , x n ) pour lesquels il existe z tel que
P (x 1 , . . . , x n ) est vrai.
Exemple 13.35 Consid´ erons la « fonction »
f : N → N,
x →
√
x.
Ce n’est pas une fonction au sens usuel, mais la d´ efinition 13.5 permet d’imaginer une
machine de Turing qui calcule
f : {0, 1, 4, 9, . . . } = U → N
et qui ne s’arrˆ ete pas si x n’est pas un carr´ e parfait. Dans notre exemple, on a pu
d´ elimiter facilement le domaine U , mais dans d’autres cas, il peut ˆ etre difficile de
d´ eterminer le domaine de la fonction. On va donc introduire la notion de fonction
partielle (d´ efinition 13.36 ci-dessous). `
A l’aide de l’op´ erateur μ, la fonction f s’´ ecrit
f (x) = μz[eg(x, z ∗ z)].
Cette fonction peut ˆ etre trait´ ee comme une proc´ edure de recherche. En partant de z = 0,
on v´ erifie s’il y a bien ´ egalit´ e. Si c’est le cas, la valeur de z est trouv´ ee. Sinon, on
applique la fonction successeur `
a z, et on v´ erifie de nouveau l’´ egalit´ e. Pous les valeurs
de x qui n’appartiennent pas ` a {0, 1, 4, 9, . . . }, il n’y aura jamais ´ egalit´ e. Ainsi, le calcul
se poursuivra ind´ efiniment.
D´ efinition 13.36 Une fonction partielle f : X → Y est un sous-ensemble de X × Y
tel que, si (x, y 1 ) ∈ f et (x, y 2 ) ∈ f , alors y 1 = y 2 . On dit que f est d´ efinie pour x s’il
existe y ∈ Y tel que (x, y) ∈ f ; sinon f n’est pas d´ efinie pour x.
Nous sommes donc certains que la fonction f de l’exemple 13.35 n’est pas une fonction primitive r´ ecursive puisque toute fonction de ce type est totale. Ainsi, mˆ eme si un
pr´ edicat p est primitif r´ ecursif, la fonction bˆ atie par la minimalisation de p n’est pas
n´ ecessairement une fonction primitive r´ ecursive. Elle fait cependant partie de l’ensemble
des fonctions r´ ecursives que nous d´ efinissons maintenant.
13 L’ordinateur ` a ADN
D´ efinition 13.34 Soient P un pr´ edicat de (n + 1) variables et p = |P | sa fonction
valeur associ´ ee. L’expression μz[p(x 1 , . . . , x n , z)] repr´ esente le plus petit nombre naturel
z, s’il existe, tel que p(x 1 , . . . , x n , z) = 1, c’est-` a-dire tel que P (x 1 , . . . , x n , z) soit vrai.
Sinon, l’expression n’est pas d´ efinie. Cette construction s’appelle la minimalisation de
p, et μz est appel´ e l’op´ erateur μ.
Un pr´ edicat de (n + 1) variables permet de d´ efinir une fonction f de n variables,
f (x 1 , . . . , x n ) = μz[p(x 1 , . . . , x n , z)],
dont le domaine est l’ensemble des (x 1 , . . . , x n ) pour lesquels il existe z tel que
P (x 1 , . . . , x n ) est vrai.
Exemple 13.35 Consid´ erons la « fonction »
f : N → N,
x →
√
x.
Ce n’est pas une fonction au sens usuel, mais la d´ efinition 13.5 permet d’imaginer une
machine de Turing qui calcule
f : {0, 1, 4, 9, . . . } = U → N
et qui ne s’arrˆ ete pas si x n’est pas un carr´ e parfait. Dans notre exemple, on a pu
d´ elimiter facilement le domaine U , mais dans d’autres cas, il peut ˆ etre difficile de
d´ eterminer le domaine de la fonction. On va donc introduire la notion de fonction
partielle (d´ efinition 13.36 ci-dessous). `
A l’aide de l’op´ erateur μ, la fonction f s’´ ecrit
f (x) = μz[eg(x, z ∗ z)].
Cette fonction peut ˆ etre trait´ ee comme une proc´ edure de recherche. En partant de z = 0,
on v´ erifie s’il y a bien ´ egalit´ e. Si c’est le cas, la valeur de z est trouv´ ee. Sinon, on
applique la fonction successeur `
a z, et on v´ erifie de nouveau l’´ egalit´ e. Pous les valeurs
de x qui n’appartiennent pas ` a {0, 1, 4, 9, . . . }, il n’y aura jamais ´ egalit´ e. Ainsi, le calcul
se poursuivra ind´ efiniment.
D´ efinition 13.36 Une fonction partielle f : X → Y est un sous-ensemble de X × Y
tel que, si (x, y 1 ) ∈ f et (x, y 2 ) ∈ f , alors y 1 = y 2 . On dit que f est d´ efinie pour x s’il
existe y ∈ Y tel que (x, y) ∈ f ; sinon f n’est pas d´ efinie pour x.
Nous sommes donc certains que la fonction f de l’exemple 13.35 n’est pas une fonction primitive r´ ecursive puisque toute fonction de ce type est totale. Ainsi, mˆ eme si un
pr´ edicat p est primitif r´ ecursif, la fonction bˆ atie par la minimalisation de p n’est pas
n´ ecessairement une fonction primitive r´ ecursive. Elle fait cependant partie de l’ensemble
des fonctions r´ ecursives que nous d´ efinissons maintenant.