13.3 Machines de Turing et fonctions r´ ecursives
431
La fonction f 4 est appel´ ee t´ etration ou tour de puissance.
Similairement, pour i > 4, on peut d´ efinir f i (m, n) par
f i (m, 0) = 1,
f i (m, n + 1) = f i−1 (m, f i (m, n)).
Ces fonctions sont appel´ ees puissances it´ er´ ees de Knuth. Chaque fonction f i+1 croˆ ıt
inimaginablement plus vite que f i .
Exemple 13.22 La fonction factorielle est une fonction primitive r´ ecursive. On d´ efinit
la fonction factorielle comme suit :
fact(0) = 1,
fact(n + 1) = mult(n + 1, fact(n)).
Apr` es avoir montr´ e que l’addition est une fonction primitive r´ ecursive, on peut se
demander s’il en est de mˆ eme pour la soustraction. La soustraction usuelle n’est pas une
fonction totale dans N. En effet, si on prend f : N × N → N telle que f (x, y) = x − y,
on remarque que, par exemple, f (3, 5) n’est pas d´ efinie. Il faut donc d´ efinir un autre
type de soustraction pour avoir une fonction totale sur N × N. Nous allons appeler cette
fonction la soustraction propre.
D´ efinition 13.23 La soustraction propre est d´ efinie comme suit :
sous(x, y) = x − y si x ≥ y,
sous(x, y) = 0
si x < y.
Exemple 13.24 La soustraction propre est une fonction primitive r´ ecursive. Pour le
d´ emontrer, il faut proc´ eder en deux ´ etapes. On commence par d´ emontrer que la fonction
pr´ ed´ ecesseur est une fonction primitive r´ ecursive et on s’en sert pour construire la
soustraction propre.
D´ efinition 13.25 La fonction pr´ ed´ ecesseur se d´ efinit par r´ ecurrence :
pred(0) = 0,
pred(y + 1) = y.
Nous pouvons maintenant construire la soustraction propre en utilisant la r´ ecurrence et
la composition.
sous(m, 0) = m,
sous(m, n + 1) = pred(sous(m, n)).