Éléments d’Informatique Théorique Série 7 Machines de Turing

Turing Machines probably epitomize the worst nightmare of programmers and computer scientists, but they are an invaluable tool used by mathematicians to define and establish complexity classes. Adriano BARENCO

Exercice 7.1 Construisez les machines de Turing acceptant les langages définis sur Σ = { a, b, c}.

L_{1} = {w cw | w ∈ { a, b}^{+}},
L_{2} = {w cw^{R} | w ∈ { a, b}^{+}},
L_{3} = { a^{n} b^{n^{2}} | n ≥ 1},
L_{4} = {w ∈ Σ^{∗} | # a = # b ou # a = # c}.

(“#x” signifie le nombre de symboles x). Donnez la définition complète de la MT pour L_{1} avec une représentation graphique de sa fonction de transition, puis donnez une définition simplifiée des machines pour L_{2}, L_{3} et L_{4} sous forme d’algorithme.

Exercice 7.2 Construisez une MT à une bande acceptant le langage L défini sur ∑ = { a, b} suivant: L = { a^{n} b^{n} | n ≥ 0} ∪ { a^{n} b^{2n} | n ≥ 0}.

Exercice 7.3 Construisez les machines de Turing calculant les fonctions suivantes .

1) n^{2},  2) n!,  3) ⌊log_{2} n⌋.

Exercice 7.4 Construisez des machines de Turing non déterministes acceptant les langages:

L_{1} = {(a)^{∗}(abb)^{∗}(baa)^{∗}},
L_{2} = {ww^{R}uu^{R} | w, u ∈ {a, b}^{∗}},
L_{3} = {a^{n} | n = p^{2} + q^{2} et p, q ≥ 0}.

Exercice 7.5 Construisez une machine de Turing calculant les coefficients binômiaux:

( \begin{matrix}n \\ k \end{matrix} ) = \{ \begin{matrix}( \begin{matrix}n − 1 \\ k − 1 \end{matrix} ) + ( \begin{matrix}n − 1 \\ k \end{matrix} ) & si 0 < k < n \\ 1 & sinon \end{matrix}

Exercice 7.6 Montrez qu’un langage L est accepté par une MT à une bande infinie des deux côtés ssi L est accepté par une MT à 1 seule bande.