430
13 L’ordinateur ` a ADN
D´ efinition 13.17 Une fonction est primitive r´ ecursive si elle peut ˆ etre obtenue de la
fonction successeur, de la fonction z´ ero et des fonctions projection, par l’application
d’un nombre fini de compositions et de r´ ecurrences.
Exemple 13.18 (la fonction add) Nous pouvons d´ efinir l’addition, add(m, n) =
m + n, `
a partir de la fonction successeur, des fonctions projection p
(1)
1
et p
(3)
3
et
d’une r´ ecurrence de base g(x) = p
(1)
1 (x) = x et de pas h(x, y, z) = s ◦ p
(3)
3 (x, y, z) =
s(p
(3)
3 (x, y, z)) = s(z).
add(m, 0) = g(m) = m,
add(m, n + 1) = h(m, n, add(m, n)) = s(add(m, n)).
Exemple 13.19 (la fonction mult) `
A partir de la fonction addition pr´ ec´ edemment
d´ efinie, des fonctions projection p
(3)
1
et p
(3)
3 , et d’une r´ ecurrence de base g(x) = 0 et
de pas h(x, y, z) = add(p
(3)
1 (x, y, z), p
(3)
3 (x, y, z)) = add(x, z), nous pouvons d´ efinir la
multiplication.
mult(m, 0) = g(m) = 0,
mult(m, n + 1) = h(m, n, mult(m, n)) = add(m, mult(m, n)).
Exemple 13.20 (la fonction exp) De fa¸ con similaire on peut d´ efinir la fonction exponentielle exp(m, n) = m
n . Il suffit de choisir g(x) = 1 et h(x, y, z) = mult(x, z). Notons
ici que, dans le but d’all´ eger la notation, nous n’utilisons plus la fonction projection.
Nous avons alors :
exp(m, 0) = 1,
exp(m, n + 1) = mult(m, exp(m, n)).
Exemple 13.21 Pour d´ efinir la r´ ecursion add(m, n + 1), nous avons utilis´ e la fonction
successeur. Pour mult(m, n + 1), nous avons utilis´ e add et pour exp(m, n + 1), nous
avons utilis´ e mult. La prochaine fonction qui est form´ ee en suivant le mˆ eme processus
est une tour d’exponentielles. Notons add(m, n) = f 1 (m, n), mult(m, n) = f 2 (m, n),
exp(m, n) = f 3 (m, n). On d´ efinit f 4 par
f 4 (m, 0) = 1
f 4 (m, n + 1) = f 3 (m, f 4 (m, n)).
On a alors
f 4 (m, n) = m
m
m ... m
n fois
.