13.3 Machines de Turing et fonctions r´ ecursives
437
D´ efinition 13.37 Les familles des fonctions et des pr´ edicats r´ ecursifs sont d´ efinies
comme suit.
1. Les fonctions successeur, z´ ero et projection sont r´ ecursives.
2. Soient g 1 , g 2 , . . . , g k et h des fonctions r´ ecursives. Soit f la composition de h et de
g 1 , g 2 , . . . , g k . Alors, f est une fonction r´ ecursive.
3. Soient g et h deux fonctions r´ ecursives. Soit f la r´ ecurrence de base g et de pas h.
Alors, f est une fonction r´ ecursive.
4. Un pr´ edicat est r´ ecursif si sa fonction valeur est r´ ecursive. Il est total si sa fonction
valeur est totale.
5. Soit P un pr´ edicat total r´ ecursif de n + 1 variables. La fonction f obtenue par
minimalisation de p = |P | est r´ ecursive.
6. Une fonction est r´ ecursive si elle peut ˆ etre obtenue par un nombre fini de compositions, de r´ ecurrences et de minimalisations `
a partir des fonctions successeur, z´ ero
et projection.
Les trois premiers points de la d´ efinition ci-dessus impliquent que toutes les fonctions
primitives r´ ecursives sont aussi r´ ecursives. L’exemple 13.35 nous montre que l’ensemble
des fonctions primitives r´ ecursives est un sous-ensemble propre de l’ensemble des fonctions r´ ecursives. Nous affirmons sans preuve le r´ esultat suivant.
Proposition 13.38 La fonction d’Ackermann d´ efinie dans l’exemple 13.33 est r´ ecursive.
Th´ eor` eme 13.39 Toutes les fonctions r´ ecursives sont MT-calculables.
Preuve Nous avons d´ ej` a d´ emontr´ e que les fonctions successeur, z´ ero et projection
sont MT-calculables. De plus, les preuves de la fermeture de la MT-calculabilit´ e sous
la composition et la r´ ecurrence ont ´ et´ e faites dans la d´ emonstration du th´ eor` eme 13.31.
Il ne nous reste qu’` a faire la preuve de la fermeture sous la minimalisation, c’est-` adire `
a montrer que l’ensemble des fonctions T -calculables contient la minimalisation des
pr´ edicats r´ ecursifs totaux.
Soit f (x 1 , . . . , x n ) = μz[p(x 1 , . . . , x n , z)] o` u p(x 1 , . . . , x n , z) est la fonction valeur
d’un pr´ edicat total P (x 1 , . . . , x n ) calculable par une machine de Turing. Soit Π, la
machine calculant la fonction valeur du pr´ edicat p.
1. Le ruban a comme configuration de d´ epart
Bx 1 Bx 2 B . . . Bx n B.
2. On ajoute la valeur 0 `
a droite des entr´ ees. On obtient alors
Bx 1 Bx 2 B . . . Bx n B0B.
On appelle le nombre `
a droite des entr´ ees, ici le nombre 0, l’indice de minimalisation,
not´ e j.
437
D´ efinition 13.37 Les familles des fonctions et des pr´ edicats r´ ecursifs sont d´ efinies
comme suit.
1. Les fonctions successeur, z´ ero et projection sont r´ ecursives.
2. Soient g 1 , g 2 , . . . , g k et h des fonctions r´ ecursives. Soit f la composition de h et de
g 1 , g 2 , . . . , g k . Alors, f est une fonction r´ ecursive.
3. Soient g et h deux fonctions r´ ecursives. Soit f la r´ ecurrence de base g et de pas h.
Alors, f est une fonction r´ ecursive.
4. Un pr´ edicat est r´ ecursif si sa fonction valeur est r´ ecursive. Il est total si sa fonction
valeur est totale.
5. Soit P un pr´ edicat total r´ ecursif de n + 1 variables. La fonction f obtenue par
minimalisation de p = |P | est r´ ecursive.
6. Une fonction est r´ ecursive si elle peut ˆ etre obtenue par un nombre fini de compositions, de r´ ecurrences et de minimalisations `
a partir des fonctions successeur, z´ ero
et projection.
Les trois premiers points de la d´ efinition ci-dessus impliquent que toutes les fonctions
primitives r´ ecursives sont aussi r´ ecursives. L’exemple 13.35 nous montre que l’ensemble
des fonctions primitives r´ ecursives est un sous-ensemble propre de l’ensemble des fonctions r´ ecursives. Nous affirmons sans preuve le r´ esultat suivant.
Proposition 13.38 La fonction d’Ackermann d´ efinie dans l’exemple 13.33 est r´ ecursive.
Th´ eor` eme 13.39 Toutes les fonctions r´ ecursives sont MT-calculables.
Preuve Nous avons d´ ej` a d´ emontr´ e que les fonctions successeur, z´ ero et projection
sont MT-calculables. De plus, les preuves de la fermeture de la MT-calculabilit´ e sous
la composition et la r´ ecurrence ont ´ et´ e faites dans la d´ emonstration du th´ eor` eme 13.31.
Il ne nous reste qu’` a faire la preuve de la fermeture sous la minimalisation, c’est-` adire `
a montrer que l’ensemble des fonctions T -calculables contient la minimalisation des
pr´ edicats r´ ecursifs totaux.
Soit f (x 1 , . . . , x n ) = μz[p(x 1 , . . . , x n , z)] o` u p(x 1 , . . . , x n , z) est la fonction valeur
d’un pr´ edicat total P (x 1 , . . . , x n ) calculable par une machine de Turing. Soit Π, la
machine calculant la fonction valeur du pr´ edicat p.
1. Le ruban a comme configuration de d´ epart
Bx 1 Bx 2 B . . . Bx n B.
2. On ajoute la valeur 0 `
a droite des entr´ ees. On obtient alors
Bx 1 Bx 2 B . . . Bx n B0B.
On appelle le nombre `
a droite des entr´ ees, ici le nombre 0, l’indice de minimalisation,
not´ e j.