Calculabilité et complexité/Exercices/Machine de Turing

Exercice 1

Pour $\Sigma =\{a,b\}$ écrire la machine de Turing qui efface les « b » mais pas les « a » et qui s'arrête au premier espace.

Solution

Représentation matricielle de $\delta$

		$\sigma$
		$\triangleright$	$\mathrm {\textvisiblespace}$	$a$	$b$
$K$	$q_{0}$	$(q_{0},\to )$	$(h,\mathrm {\textvisiblespace} )$	$(q_{0},\to )$	$(q_{1},\mathrm {\textvisiblespace} )$
	$q_{1}$	$(q_{1},\to )$	$(q_{0},a)$	$(q_{0},b)$	$(q01,\to )$

 

Exercice 2

Écrire la machine de Turing qui efface les « a », qui s'arrête au premier espace et ramène la tête de lecture à la position de départ.

Solution

Cette solution n'a pas été rédigée. Vous pouvez le faire en modifiant le paramètre « contenu » du modèle. ^{Comment faire ?}