Eléments d’ informatique théorique Série 12

Exercice 11.1 Donnez les machines de Turing résolvant les problèmes ci-dessous et analysez les différentes complexités de leur calcul ! Envisagez d’éventuelles modifications afin d’améliorer ces dernières !

1. soustraire deux entiers en base 2,

2. reconnaître le langage L = {a^{n}b^{n}c^{n} | n ≥ 1},

3. reconnaître le langage L = {a^{n}b^{n^{2}} | n ≥ 1},

4. reconnaître le langage L = {a^{n}b^{n} | n ≥ 1} ∪ {a^{n}b^{2n} | n ≥ 1}.

Définition 1 Crossing Sequence Intuitivement une “crossing sequence” pour une position z est la suite des états qui franchissent la limite entre la z^{ème} et la z + 1^{ème} position à partir d’un certain état de départ q_{t_{0}}. On note cette “crossing sequence” par CS(z). Pour l’illustration ci-dessous CS(z) = {q_{t_{r}}, q_{t_{r+1}}, q_{t_{r+2}}, … }.

1  ^{Chemin suivit par la tête}  z z + 1 q_{t_{0}}  q_{t_{r}} q_{t_{r+1}} q_{t_{r+2}}

Exercice 11.2 Donnez une définition formelle de CS(z) pour une machine de Turing à une bande.

Exercice 11.3 Trouvez une machine de Turing à une bande acceptant L = {wcw^{R} | w ∈ {0, 1}^{∗}}, évaluez CS(z) de cette machine ainsi que sa complexité en temps.