456
13 L’ordinateur ` a ADN
sur le ruban. Notons qu’il n’est pas n´ ecessaire que le B ` a la gauche du y soit le premier sur le ruban (c’est-` a-dire qu’il n’est pas n´ ecessaire de vous soucier de translater
le r´ esultat).
9. Expliquer comment construire une machine de Turing permettant de calculer la
fonction factorielle en supposant connue une machine de Turing M qui calcule la
fonction multiplication.
10. On consid` ere les fonctions pp, pg et eg d´ efinies en (13.1).
a) Expliquer comment construire une machine de Turing qui calcule pp(x, y).
b) Expliquer comment construire une machine de Turing qui calcule pg(x, y).
c) Expliquer comment construire une machine de Turing qui calcule eg(x, y).
Les fonctions r´ ecursives
11. Montrer que les fonctions sgn et cosgn d´ efinies comme suit
sgn(0) = 0,
sgn(y + 1) = 1,
cosgn(0) = 1,
cosgn(y + 1) = 0,
sont des fonctions primitives r´ ecursives.
12. Montrer que la fonction f : N × N → N donn´ ee par f (m, n) = mn + 3n
2 + 1 est
primitive r´ ecursive.
13. Montrer que les fonctions suivantes sont r´ ecursives.
a) abs(x, y) = |x − y|.
b) max(x, y) =
x, x ≥ y,
y, x < y.
c) f (x) = log 2 (x). Ici f (x) est une fonction totale qui, ` a x, associe la partie
enti` ere de log 2 (x).
d) div(x, y) = x/y. Ici div(x, y) est la partie enti` ere du quotient de x par y.
Ainsi div(7, 3) = 2.
e) rest(x, y) = x mod y. Nous voulons ici le reste de la division enti` ere. Ainsi
rest(31, 7) = 3.
f) f (x) =
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
5,
x = 0,
2,
x = 1,
4,
x = 2,
3x, x > 3.
14. Montrer que, si g est une fonction primitive r´ ecursive de n + 1 variables, alors
f (x 1 , . . . , x n , y) =
y
i=0
g(x 1 , . . . , x n , i)