13.7 Exercices
455
3. a) Construire une machine de Turing permettant de translater un nombre de n
cases.
b) Construire une machine de Turing permettant de translater k nombres de n
cases.
c) Construire une machine de Turing permettant de translater un nombre pr´ ec´ ed´ e
d’un nombre arbitraire de B sur le ruban pour le remettre juste ` a la droite du
premier symbole B : BBBBBBxB devient BxB.
4. Construire une machine de Turing qui calcule la fonction pr´ ed´ ecesseur.
5. Construire une machine de Turing effectuant la fonction cosgn : N → N d´ efinie par
cosgn(n) =
1, n = 0,
0, n ≥ 1.
6. V´ erifier que les ´ egalit´ es
|¬P 1 | = cosgn(p 1 ),
|P 1 ∨ P 2 | = sgn(p 1 + p 2 ),
|P 1 ∧ P 2 | = p 1 ∗ p 2 ,
correspondent bien aux fonctions valeurs des op´ erateurs bool´ eens ET, OU et NON.
Les tables de v´ erit´ e de ces op´ erateurs sont donn´ ees ` a la section 15.7 du chapitre 15.
7. a) Expliquer comment construire une machine de Turing qui calcule la fonction
f : N × N → {0, 1} ⊂ N
d´ efinie par
f (x, y) =
1, x = y,
0, sinon.
b) Expliquer comment construire une machine de Turing qui calcule la fonction
f : N × N → {0, 1} ⊂ N
d´ efinie par
f (x, y) =
1, x ≥ y,
0, sinon.
8. Construire une machine de Turing qui intervertit deux nombres sur le ruban : si
BxByB est la configuration initiale, alors la machine s’arrˆ etera sur ByBxB. L’exercice est plus simple si on utilise l’alphabet de ruban {B, 1, A}, o` u A sert de marqueur