Une page de Wikiversité, la communauté pédagogique libre.
En raison de limitations techniques, la typographie souhaitable du titre, «
Exercice : Machine de TuringCalculabilité et complexité/Exercices/Machine de Turing », n'a pu être restituée correctement ci-dessus.
Pour
Σ
=
{
a
,
b
}
{\displaystyle \Sigma =\{a,b\}}
Solution
Représentation matricielle de
δ
{\displaystyle \delta }
σ
{\displaystyle \sigma }
▹
{\displaystyle \triangleright }
␣
{\displaystyle \mathrm {\textvisiblespace} }
a
{\displaystyle a}
b
{\displaystyle b}
K
{\displaystyle K}
q
0
{\displaystyle q_{0}}
(
q
0
,
→
)
{\displaystyle (q_{0},\to )}
(
h
,
␣
)
{\displaystyle (h,\mathrm {\textvisiblespace} )}
(
q
0
,
→
)
{\displaystyle (q_{0},\to )}
(
q
1
,
␣
)
{\displaystyle (q_{1},\mathrm {\textvisiblespace} )}
q
1
{\displaystyle q_{1}}
(
q
1
,
→
)
{\displaystyle (q_{1},\to )}
(
q
0
,
a
)
{\displaystyle (q_{0},a)}
(
q
0
,
b
)
{\displaystyle (q_{0},b)}
(
q
01
,
→
)
{\displaystyle (q01,\to )}
É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 ?
