428
13 L’ordinateur ` a ADN
Nous pouvons voir sur la figure 13.9 les ´ etapes suivies par cette machine. Apr` es
l’´ etat initial, q 0 , les i − 1 premiers ´ etats prescrivent de remplacer chacune des entr´ ees
des nombres x 1 , . . . , x i−1 par le caract` ere blanc. La machine atteint alors l’´ etat q i qui
prescrit de balayer x i sans le changer. Les ´ etats q i+1 ` a q n prescrivent de remplacer x i+1
` a x n par des blancs. L’´ etat q n+1 prescrit de positionner le pointeur `
a droite de x i , et q n+2
de positionner le pointeur `
a gauche de x i . La machine s’arrˆ ete ` a cette position puisque
ϕ(q n+2 , B) n’est pas d´ efinie. Notons que, dans cet exemple, la machine ne s’arrˆ ete pas
sur la case de d´ epart, soit la case ` a l’extrˆ eme gauche.
Nous aurions pu ajouter des instructions pour translater le r´ esultat x i au d´ ebut du
ruban, le laissant seulement pr´ ec´ ed´ e du symbole B, et pour arrˆ eter le pointeur sur le
premier B (voir l’exercice 3), comme c’´ etait le cas dans les derniers exemples. Ce n’est
cependant pas requis par la d´ efinition d’une fonction calculable (d´ efinition 13.5).
13.3.2 Les fonctions primitives r´ ecursives et les fonctions r´ ecursives
Nous avons vu dans la section pr´ ec´ edente qu’il existe des fonctions num´ eriques
qui sont calculables par une machine de Turing appropri´ ee. Nous pouvons maintenant
nous demander quels types de fonctions sont MT-calculables. Les fonctions primitives
r´ ecursives et les fonctions r´ ecursives dont nous parlerons ci-dessous en sont des exemples.
Avant de pr´ esenter les fonctions primitives r´ ecursives, nous avons besoin de quelques
d´ efinitions pr´ eliminaires.
Dans tout ce chapitre, on aura
N = {0, 1, 2, . . .}.
D´ efinition 13.11 Une fonction arithm´ etique est une fonction de la forme
f : N × N × · · · × N → N.
Exemple 13.12 Les fonctions successeur
s : N → N,
x → x + 1,
et projection
p
(n)
i
: N × N × ... × N → N,
(x 1 , x 2 , ..., x n ) → x i ,
sont des fonctions arithm´ etiques.
On peut identifier une fonction f : X → Y `
a un sous-ensemble de X × Y. Ainsi, si
(x, y) ∈ f , on note y = f (x).
D´ efinition 13.13 Une fonction f : X → Y est dite totale si elle respecte les deux
conditions suivantes :
13 L’ordinateur ` a ADN
Nous pouvons voir sur la figure 13.9 les ´ etapes suivies par cette machine. Apr` es
l’´ etat initial, q 0 , les i − 1 premiers ´ etats prescrivent de remplacer chacune des entr´ ees
des nombres x 1 , . . . , x i−1 par le caract` ere blanc. La machine atteint alors l’´ etat q i qui
prescrit de balayer x i sans le changer. Les ´ etats q i+1 ` a q n prescrivent de remplacer x i+1
` a x n par des blancs. L’´ etat q n+1 prescrit de positionner le pointeur `
a droite de x i , et q n+2
de positionner le pointeur `
a gauche de x i . La machine s’arrˆ ete ` a cette position puisque
ϕ(q n+2 , B) n’est pas d´ efinie. Notons que, dans cet exemple, la machine ne s’arrˆ ete pas
sur la case de d´ epart, soit la case ` a l’extrˆ eme gauche.
Nous aurions pu ajouter des instructions pour translater le r´ esultat x i au d´ ebut du
ruban, le laissant seulement pr´ ec´ ed´ e du symbole B, et pour arrˆ eter le pointeur sur le
premier B (voir l’exercice 3), comme c’´ etait le cas dans les derniers exemples. Ce n’est
cependant pas requis par la d´ efinition d’une fonction calculable (d´ efinition 13.5).
13.3.2 Les fonctions primitives r´ ecursives et les fonctions r´ ecursives
Nous avons vu dans la section pr´ ec´ edente qu’il existe des fonctions num´ eriques
qui sont calculables par une machine de Turing appropri´ ee. Nous pouvons maintenant
nous demander quels types de fonctions sont MT-calculables. Les fonctions primitives
r´ ecursives et les fonctions r´ ecursives dont nous parlerons ci-dessous en sont des exemples.
Avant de pr´ esenter les fonctions primitives r´ ecursives, nous avons besoin de quelques
d´ efinitions pr´ eliminaires.
Dans tout ce chapitre, on aura
N = {0, 1, 2, . . .}.
D´ efinition 13.11 Une fonction arithm´ etique est une fonction de la forme
f : N × N × · · · × N → N.
Exemple 13.12 Les fonctions successeur
s : N → N,
x → x + 1,
et projection
p
(n)
i
: N × N × ... × N → N,
(x 1 , x 2 , ..., x n ) → x i ,
sont des fonctions arithm´ etiques.
On peut identifier une fonction f : X → Y `
a un sous-ensemble de X × Y. Ainsi, si
(x, y) ∈ f , on note y = f (x).
D´ efinition 13.13 Une fonction f : X → Y est dite totale si elle respecte les deux
conditions suivantes :