Calculabilité et complexité/Exercices/Machine de Turing

Exercice 1

Pour $\mathrm{\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$
		$▹$	$␣$	$a$	$b$
$K$	$q_0$	$(q_0,\to )$	$(h,␣)$	$(q_0,\to )$	$(q_1,␣)$
	$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 ?}