13.3 Machines de Turing et fonctions r´ ecursives
435
5. Si i < y, c’est-` a-dire si pp(i, y) = 1, la machine copie les variables et le compteur i
` a gauche de f (x 1 , . . . , x n , i). L’exercice 10 montre qu’une machine de Turing peut
calculer pp(i, y). Ainsi, on peut construire une machine de Turing qui se met dans
un ´ etat si pp(i, y) = 1 et dans un autre ´ etat sinon. On obtient alors la configuration
Bx 1 Bx 2 B . . . Bx n ByBiBx 1 Bx 2 B . . . Bx n BiBf (x 1 , . . . , x n , i)B.
On applique alors la fonction successeur au compteur pour obtenir la configuration
Bx 1 Bx 2 B . . . Bx n ByBi + 1Bx 1 Bx 2 B . . . Bx n BiBf (x 1 , . . . , x n , i)B.
La machine H op´ erant sur les n + 2 derni` eres variables, produit
Bx 1 Bx 2 B . . . Bx n ByBi + 1Bh(x 1 , . . . , x n , i, f(x 1 , . . . , x n , i))B.
Notons que h(x 1 , . . . , x n , i, f(x 1 , . . . , x n , i)) est ´ egal `
a f (x 1 , . . . , x n , i+1). Si le compteur marque i = y, c’est-` a-dire si pp(i, y) = 0, alors on compl` ete le calcul en effa¸ cant
les n + 2 premiers nombres sur le ruban. Le calcul de la machine se poursuit par
r´ ep´ etition de l’´ etape 5 jusqu’` a l’arrˆ et.
On peut se demander si toutes les fonctions arithm´ etiques totales qui sont calculables
par une machine de Turing sont des fonctions primitives r´ ecursives. Le th´ eor` eme suivant
r´ epond `
a cette question.
Th´ eor` eme 13.32 L’ensemble des fonctions primitives r´ ecursives est un sous-ensemble
propre des fonctions calculables par une machine de Turing, c’est-` a-dire qu’il existe une
fonction f , MT-calculable, qui n’est pas primitive r´ ecursive.
Exemple 13.33 La fonction d’Ackermann d´ efinie par
1. A(0, y) = y + 1,
2. A(x + 1, 0) = A(x, 1),
3. A(x + 1, y + 1) = A(x, A(x + 1, y)),
est MT-calculable, mais n’est pas primitive r´ ecursive. La fonction d’Ackermann a la
propri´ et´ e de « croˆ ıtre plus rapidement » que toutes les fonctions primitives r´ ecursives,
d’o` u son attrait. Mais puisqu’elle croˆ ıt plus rapidement que toute fonction primitive
r´ ecursive, elle ne peut en ˆ etre une. Les preuves de ces propri´ et´ es sont arides, nous nous
abstiendrons de les faire ici. Vous pouvez cependant les trouver dans [4].
Pour d´ efinir une nouvelle famille de fonctions qui contient celle des fonctions primitives r´ ecursives, nous utiliserons les op´ erateurs bool´ eens et les op´ erateurs de relation.
Ils nous permettront de d´ efinir une nouvelle op´ eration : la minimalisation.
435
5. Si i < y, c’est-` a-dire si pp(i, y) = 1, la machine copie les variables et le compteur i
` a gauche de f (x 1 , . . . , x n , i). L’exercice 10 montre qu’une machine de Turing peut
calculer pp(i, y). Ainsi, on peut construire une machine de Turing qui se met dans
un ´ etat si pp(i, y) = 1 et dans un autre ´ etat sinon. On obtient alors la configuration
Bx 1 Bx 2 B . . . Bx n ByBiBx 1 Bx 2 B . . . Bx n BiBf (x 1 , . . . , x n , i)B.
On applique alors la fonction successeur au compteur pour obtenir la configuration
Bx 1 Bx 2 B . . . Bx n ByBi + 1Bx 1 Bx 2 B . . . Bx n BiBf (x 1 , . . . , x n , i)B.
La machine H op´ erant sur les n + 2 derni` eres variables, produit
Bx 1 Bx 2 B . . . Bx n ByBi + 1Bh(x 1 , . . . , x n , i, f(x 1 , . . . , x n , i))B.
Notons que h(x 1 , . . . , x n , i, f(x 1 , . . . , x n , i)) est ´ egal `
a f (x 1 , . . . , x n , i+1). Si le compteur marque i = y, c’est-` a-dire si pp(i, y) = 0, alors on compl` ete le calcul en effa¸ cant
les n + 2 premiers nombres sur le ruban. Le calcul de la machine se poursuit par
r´ ep´ etition de l’´ etape 5 jusqu’` a l’arrˆ et.
On peut se demander si toutes les fonctions arithm´ etiques totales qui sont calculables
par une machine de Turing sont des fonctions primitives r´ ecursives. Le th´ eor` eme suivant
r´ epond `
a cette question.
Th´ eor` eme 13.32 L’ensemble des fonctions primitives r´ ecursives est un sous-ensemble
propre des fonctions calculables par une machine de Turing, c’est-` a-dire qu’il existe une
fonction f , MT-calculable, qui n’est pas primitive r´ ecursive.
Exemple 13.33 La fonction d’Ackermann d´ efinie par
1. A(0, y) = y + 1,
2. A(x + 1, 0) = A(x, 1),
3. A(x + 1, y + 1) = A(x, A(x + 1, y)),
est MT-calculable, mais n’est pas primitive r´ ecursive. La fonction d’Ackermann a la
propri´ et´ e de « croˆ ıtre plus rapidement » que toutes les fonctions primitives r´ ecursives,
d’o` u son attrait. Mais puisqu’elle croˆ ıt plus rapidement que toute fonction primitive
r´ ecursive, elle ne peut en ˆ etre une. Les preuves de ces propri´ et´ es sont arides, nous nous
abstiendrons de les faire ici. Vous pouvez cependant les trouver dans [4].
Pour d´ efinir une nouvelle famille de fonctions qui contient celle des fonctions primitives r´ ecursives, nous utiliserons les op´ erateurs bool´ eens et les op´ erateurs de relation.
Ils nous permettront de d´ efinir une nouvelle op´ eration : la minimalisation.