13.3 Machines de Turing et fonctions r´ ecursives
429
1. ∀x ∈ X, ∃y ∈ Y tel que (x, y) ∈ f ;
2. si (x, y 1 ) ∈ f et (x, y 2 ) ∈ f , alors y 1 = y 2 .
Cette d´ efinition est celle qu’on utilise d’ordinaire pour une fonction dont le domaine
est X. Nous jugeons important de la donner ici pour distinguer les fonctions totales des
fonctions partielles qui seront d´ efinies plus tard.
Les fonctions primitives r´ ecursives sont g´ en´ er´ ees ` a partir des fonctions de base suivantes.
Fonctions de base de la classe des fonctions primitives r´ ecursives :
1. la fonction successeur s : s(x) = x + 1 ;
2. la fonction z´ ero z : z(x) = 0 ;
3. les fonctions projection p i
(n) : p i
(n) (x 1 , x 2 , . . . , x n ) = x i , 1 ≤ i ≤ n.
Remarquons que la fonction identit´ e fait partie des fonctions de base, car elle est ´ egale
` a p
(1)
1 .
Les fonctions primitives r´ ecursives se construisent avec deux types d’op´ erations que
l’on peut it´ erer sur les fonctions de base d´ efinies pr´ ec´ edemment. Ces op´ erations, la
composition et la r´ ecurrence, permettent de conserver la MT-calculabilit´ e des fonctions,
ce que nous montrerons plus tard.
D´ efinition 13.14 Soient g 1 , g 2 , . . . , g k des fonctions arithm´ etiques de n variables et h
une fonction arithm´ etique de k variables. Soit f la fonction d´ efinie par
f (x 1 , x 2 , . . . , x n ) = h(g 1 (x 1 , x 2 , . . . , x n ), . . . , g k (x 1 , x 2 , . . . , x n )).
f est appel´ ee la composition de h et de g 1 , g 2 , . . . , g k , not´ ee f = h ◦ (g 1 , g 2 , . . . , g k ).
Exemple 13.15 Soient h(x 1 , x 2 ) = s(x 1 ) + x 2 , g 1 (x) = x
3 et g 2 (x) = x
2 + 9.
Soit f (x) = h ◦ (g 1 , g 2 )(x) pour x ≥ 0. Alors, f peut s’´ ecrire de mani` ere simplifi´ ee
f (x) = x
3 + x
2 + 10.
Nous pouvons maintenant d´ efinir la r´ ecurrence.
D´ efinition 13.16 Soient g et h des fonctions arithm´ etiques totales de n et n + 2 variables respectivement. La fonction f de n + 1 variables d´ efinie par
1. f (x 1 , x 2 , . . . , x n , 0) = g(x 1 , x 2 , . . . , x n ) ;
2. f (x 1 , x 2 , . . . , x n , y + 1) = h(x 1 , x 2 , . . . , x n , y, f(x 1 , x 2 , . . . , x n , y)),
est appel´ ee r´ ecurrence de base g et de pas h. On permet n = 0 avec la convention qu’une
fonction de z´ ero variable est une constante.
Nous avons maintenant tous les outils n´ ecessaires pour d´ efinir les fonctions primitives
r´ ecursives.
429
1. ∀x ∈ X, ∃y ∈ Y tel que (x, y) ∈ f ;
2. si (x, y 1 ) ∈ f et (x, y 2 ) ∈ f , alors y 1 = y 2 .
Cette d´ efinition est celle qu’on utilise d’ordinaire pour une fonction dont le domaine
est X. Nous jugeons important de la donner ici pour distinguer les fonctions totales des
fonctions partielles qui seront d´ efinies plus tard.
Les fonctions primitives r´ ecursives sont g´ en´ er´ ees ` a partir des fonctions de base suivantes.
Fonctions de base de la classe des fonctions primitives r´ ecursives :
1. la fonction successeur s : s(x) = x + 1 ;
2. la fonction z´ ero z : z(x) = 0 ;
3. les fonctions projection p i
(n) : p i
(n) (x 1 , x 2 , . . . , x n ) = x i , 1 ≤ i ≤ n.
Remarquons que la fonction identit´ e fait partie des fonctions de base, car elle est ´ egale
` a p
(1)
1 .
Les fonctions primitives r´ ecursives se construisent avec deux types d’op´ erations que
l’on peut it´ erer sur les fonctions de base d´ efinies pr´ ec´ edemment. Ces op´ erations, la
composition et la r´ ecurrence, permettent de conserver la MT-calculabilit´ e des fonctions,
ce que nous montrerons plus tard.
D´ efinition 13.14 Soient g 1 , g 2 , . . . , g k des fonctions arithm´ etiques de n variables et h
une fonction arithm´ etique de k variables. Soit f la fonction d´ efinie par
f (x 1 , x 2 , . . . , x n ) = h(g 1 (x 1 , x 2 , . . . , x n ), . . . , g k (x 1 , x 2 , . . . , x n )).
f est appel´ ee la composition de h et de g 1 , g 2 , . . . , g k , not´ ee f = h ◦ (g 1 , g 2 , . . . , g k ).
Exemple 13.15 Soient h(x 1 , x 2 ) = s(x 1 ) + x 2 , g 1 (x) = x
3 et g 2 (x) = x
2 + 9.
Soit f (x) = h ◦ (g 1 , g 2 )(x) pour x ≥ 0. Alors, f peut s’´ ecrire de mani` ere simplifi´ ee
f (x) = x
3 + x
2 + 10.
Nous pouvons maintenant d´ efinir la r´ ecurrence.
D´ efinition 13.16 Soient g et h des fonctions arithm´ etiques totales de n et n + 2 variables respectivement. La fonction f de n + 1 variables d´ efinie par
1. f (x 1 , x 2 , . . . , x n , 0) = g(x 1 , x 2 , . . . , x n ) ;
2. f (x 1 , x 2 , . . . , x n , y + 1) = h(x 1 , x 2 , . . . , x n , y, f(x 1 , x 2 , . . . , x n , y)),
est appel´ ee r´ ecurrence de base g et de pas h. On permet n = 0 avec la convention qu’une
fonction de z´ ero variable est une constante.
Nous avons maintenant tous les outils n´ ecessaires pour d´ efinir les fonctions primitives
r´ ecursives.