13.3 Machines de Turing et fonctions r´ ecursives
433
D´ efinition 13.29 Un pr´ edicat est primitif r´ ecursif si sa fonction valeur est primitive
r´ ecursive.
Exemple 13.30 Les pr´ edicats « x < y », « x > y » et « x = y » de l’exemple 13.27
sont primitifs r´ ecursifs. Nous avons en effet construit leur fonction valeur en (13.1) par
composition de fonctions primitives r´ ecursives.
Maintenant que nous avons introduit les fonctions primitives r´ ecursives, nous pouvons
faire le lien entre cet ensemble de fonctions et les machines de Turing.
Th´ eor` eme 13.31 Toutes les fonctions primitives r´ ecursives sont MT-calculables.
Preuve Puisque nous avons d´ ej` a construit les machines de Turing qui calculent les
fonctions successeur, z´ ero et projection, il suffit de montrer que l’ensemble des fonctions
MT-calculables est ferm´ e sous la composition et sous la r´ ecurrence.
Commen¸ cons par montrer la fermeture sous la composition. Soit
f (x 1 , . . . , x n ) = h ◦ (g 1 (x 1 , . . . , x n ), . . . , g k (x 1 , . . . , x n )),
o` u g i , i = 1, . . . , k, et h sont des fonctions arithm´ etiques totales et calculables par
une machine de Turing. Nous noterons H et G i les machines permettant de calculer les
fonctions h et g i respectivement. Nous allons construire la machine de Turing permettant
de calculer f (x 1 , . . . , x n ) ` a partir des machines pr´ ec´ edemment mentionn´ ees.
1. Le calcul de f (x 1 , . . . , x n ) commence avec la configuration de ruban
Bx 1 Bx 2 B . . . Bx n B.
2. On copie cette partie du ruban `
a droite :
Bx 1 B . . . Bx n B
x 1 B . . . Bx n B
.
La machine copiant la configuration initiale du ruban sera construite dans l’exercice 2.
3. On utilise la machine G 1 pour obtenir
Bx 1 Bx 2 B . . . Bx n Bg 1 (x 1 , . . . , x n )B.
On peut maintenant copier de nouveau l’entr´ ee Bx 1 Bx 2 B . . . Bx n B ` a la fin du ruban
pour obtenir la configuration
Bx 1 Bx 2 B . . . Bx n Bg 1 (x 1 , . . . , x n )Bx 1 Bx 2 B . . . Bx n B.
Il est possible d’utiliser G 2 sur les n derniers nombres. On effectue ces ´ etapes k fois
afin d’obtenir la configuration
Bx 1 Bx 2 B . . . Bx n Bg 1 (x 1 , . . . , x n )B . . . Bg k (x 1 , . . . , x n )B.
433
D´ efinition 13.29 Un pr´ edicat est primitif r´ ecursif si sa fonction valeur est primitive
r´ ecursive.
Exemple 13.30 Les pr´ edicats « x < y », « x > y » et « x = y » de l’exemple 13.27
sont primitifs r´ ecursifs. Nous avons en effet construit leur fonction valeur en (13.1) par
composition de fonctions primitives r´ ecursives.
Maintenant que nous avons introduit les fonctions primitives r´ ecursives, nous pouvons
faire le lien entre cet ensemble de fonctions et les machines de Turing.
Th´ eor` eme 13.31 Toutes les fonctions primitives r´ ecursives sont MT-calculables.
Preuve Puisque nous avons d´ ej` a construit les machines de Turing qui calculent les
fonctions successeur, z´ ero et projection, il suffit de montrer que l’ensemble des fonctions
MT-calculables est ferm´ e sous la composition et sous la r´ ecurrence.
Commen¸ cons par montrer la fermeture sous la composition. Soit
f (x 1 , . . . , x n ) = h ◦ (g 1 (x 1 , . . . , x n ), . . . , g k (x 1 , . . . , x n )),
o` u g i , i = 1, . . . , k, et h sont des fonctions arithm´ etiques totales et calculables par
une machine de Turing. Nous noterons H et G i les machines permettant de calculer les
fonctions h et g i respectivement. Nous allons construire la machine de Turing permettant
de calculer f (x 1 , . . . , x n ) ` a partir des machines pr´ ec´ edemment mentionn´ ees.
1. Le calcul de f (x 1 , . . . , x n ) commence avec la configuration de ruban
Bx 1 Bx 2 B . . . Bx n B.
2. On copie cette partie du ruban `
a droite :
Bx 1 B . . . Bx n B
x 1 B . . . Bx n B
.
La machine copiant la configuration initiale du ruban sera construite dans l’exercice 2.
3. On utilise la machine G 1 pour obtenir
Bx 1 Bx 2 B . . . Bx n Bg 1 (x 1 , . . . , x n )B.
On peut maintenant copier de nouveau l’entr´ ee Bx 1 Bx 2 B . . . Bx n B ` a la fin du ruban
pour obtenir la configuration
Bx 1 Bx 2 B . . . Bx n Bg 1 (x 1 , . . . , x n )Bx 1 Bx 2 B . . . Bx n B.
Il est possible d’utiliser G 2 sur les n derniers nombres. On effectue ces ´ etapes k fois
afin d’obtenir la configuration
Bx 1 Bx 2 B . . . Bx n Bg 1 (x 1 , . . . , x n )B . . . Bg k (x 1 , . . . , x n )B.