13.3 Machines de Turing et fonctions r´ ecursives
427
Fig. 13.7. Fonction z´ ero
Fig. 13.8. Fonction addition
Exemple 13.10 (les fonctions projection) Construisons une derni` ere machine
pour un type de fonctions qui sera important dans la prochaine section, les fonctions
projection. Nous d´ efinissons la fonction projection p i
(n) comme suit :
p i
(n) (x 1 , x 2 , . . . , x n ) = x i , 1 ≤ i ≤ n.
Pour construire cette fonction, nous devons effacer les i − 1 premiers nombres sur le
ruban, conserver le i
`
eme et effacer les n − i restants. L’alphabet de ruban reste celui des exemples pr´ ec´ edents. L’alphabet d’´ etat est {q i : i = 0, . . . , n + 2}, et la fonction ϕ est repr´ esent´ ee ` a la figure 13.9. Notons que le ruban a la configuration initiale
q 0 Bx 1 B . . . Bx n B et la configuration finale q f Bx i B.
Fig. 13.9. Fonction projection
427
Fig. 13.7. Fonction z´ ero
Fig. 13.8. Fonction addition
Exemple 13.10 (les fonctions projection) Construisons une derni` ere machine
pour un type de fonctions qui sera important dans la prochaine section, les fonctions
projection. Nous d´ efinissons la fonction projection p i
(n) comme suit :
p i
(n) (x 1 , x 2 , . . . , x n ) = x i , 1 ≤ i ≤ n.
Pour construire cette fonction, nous devons effacer les i − 1 premiers nombres sur le
ruban, conserver le i
`
eme et effacer les n − i restants. L’alphabet de ruban reste celui des exemples pr´ ec´ edents. L’alphabet d’´ etat est {q i : i = 0, . . . , n + 2}, et la fonction ϕ est repr´ esent´ ee ` a la figure 13.9. Notons que le ruban a la configuration initiale
q 0 Bx 1 B . . . Bx n B et la configuration finale q f Bx i B.
Fig. 13.9. Fonction projection