TD 1 : Problème de l’arrêt, Fonctions calculables, Castors affairés

Énoncé (pas les mêmes numéros d’exercices)

Chargé de TD : Adrien Koutsos

TD1

EX1

ABS : Si $H$ existait, on considère la machine $N$ définie par

\[N(a) = \begin{cases} \bot(a) \text{ si } H(D(a))=1 \\ Vrai(a) \text{ sinon } \end{cases}\]

Si $N([N])$ s’arrête, $H(D([N])) = H(⟨[N], [N]⟩) = 0$ : faux

Si $N([N])$ ne s’arrête pas, $H(D([N])) = H(⟨[N], [N]⟩) = 1$ : faux

Contradiction.

EX2

1.

• $𝛴$ : quelconque
• $Q = {(skip, 𝛼)}{𝛼∈𝛴} ∪ {(test, 𝛼)}{𝛼∈𝛴} ∪ {return} ∪ {get}$

Initial state : $return$

$∀𝛼, 𝛽 ∈ 𝛴$ :

• $𝛿(get, 𝛼) = ((skip, 𝛼), $, ⟶)$
• $𝛿((skip, 𝛼), 𝛽) = ((skip, 𝛼), 𝛽, ⟶)$
• $𝛿((skip, 𝛼), B) = ((test, 𝛼), B, ⟵)$
• $𝛿((skip, 𝛼), 𝛽) = ((skip, 𝛼), 𝛽, ⟶)$
• $𝛿((test, 𝛼), $) = ((accept, 𝛼), B, \downarrow)$
• $𝛿((test, 𝛼), 𝛼) = (return, B, ⟵)$
• $𝛿((test, 𝛼), 𝛽\neq 𝛼) = (reject, B, \downarrow)$
• $𝛿(return, 𝛽) = (return, 𝛽, ⟵)$
• $𝛿(return, $) = (get, $, ⟶)$
• $𝛿(get, B) = (accept, B, \downarrow)$

2.

3. v = vu

État initial : $q_1$

	$	0	1	v	B
$q_0$	($q_0$, $, →)	($q_{1,back}$, v, ←)	($q_0$, 1,→)	($q_0$, v,→)	reject
$q_1$	($q_1$, $, →)	($q_1$, 0, →)	($q_0$, v,←)	($q_1$,v,→)	accept
$q_{0,back}$	($q_0$, $, →)	($q_{0,back}$,v,←)	($q_{0,back}$,v,←)	($q_{0,back}$,v,←)	($q_{0,back}$,v,←)
$q_{1,back}$	($q_1$, $, →)	($q_{1,back}$,v,←)	($q_{1,back}$,v,←)	($q_{1,back}$,v,←)	($q_{1,back}$,v,←)

---

Preuve : Par récurrence sur la taille du ruban en ignorant les “v” : “Les mots acceptés sont exactement ceux ayant plus de 0 que de 1”

• Immédiat pour le mot vide.
• Pour une taille de ruban $n$ : si l’état courant est
  • $q_0$ : on supprime un 0 (en le remplaçant par un “v”) et on revient au début. Puis : hypothèse de récurrence sur le ruban.
  • idem pour $q_1$
  • pour les autres : évident.

EX 3

• $f_1$ est calculable car elle est constante dans tous les cas.
• $f_2$ :
  • Si $f_2(n) = 0$ : quelque part dans $𝜋$ (en base 2), il y a une sous-séquence de taille $n$ de 1’s. Dans tous les cas : il existe un $N ∈ ℝ ∪ {+∞}$ tel que : \(f_2 = \begin{cases} 0 \text{ si } n \leq N \\ 1 \text{ sinon.} \end{cases}\)

EX 5

1) NB : rester sur place n’augmente pas le pouvoir d’expression des machines de Turing ⟶ on peut supposer, sans perte de généralité, qu’on reste pas sur place à aucun moment.

Obligatoirement :

	1	B
$q_1$		$q_2$ → 1
$q_2$		←

Condition nécessaire

Cette MT convient :

	1	B
$q_1$	$q_2$ ← 1	$q_2$ → 1
$q_2$	accept	$q_1$ ← 1

MT telle que $f(M)=1$

⟹ $SCORE(2) \geq 4$

En fait : $SCORE(2) = 4$ (il y a 32 possibilités).

2) Mq $SCORE$ n’est pas calculable.

ABS : Supposons que $M_f$ calcule $SCORE$ : \(∀n, M_f(n) = SCORE(n)\)

Il existe une machine $M_{2x}$ telle que \(∀n, M_{2x}(n) = 2n\)

Soit $M’$ une machine qui

• écrit $m$ 1’s sur la bande (vers la gauche).
• applique $M_{2x}$
• applique $M_f$ ⟶ on a donc $SCORE(2m)$ 1’s sur la bande.

$M’$ a $m+c+n$ états ($c, n$: nombre d’états de $M_f, M_{2x}$)

Par définition de $SCORE$ : \(SCORE(m+c+n) \geq SCORE(2m)\)

Avec $m = c + n + 1$ : \(SCORE(2m+2c+2n+1) \geq SCORE(2m+2c+2n+2)\)

Impossible, car $SCORE$ croît.

NB : On aurait pu utiliser le problème de l’arrêt.

EX 6

1) On numérote les lettres de l’alphabet de $1$ à $n$, et au lieu d’écrire ces lettres, on écrit leur représentation binaire sur le ruban, en les séparant par des blancs (on devra ajouter des états “intermédiaires” de lecture de la représentation binaire des lettres).