Calculabilité et complexité/Exercices/Machine de Turing

Leçons de niveau 17
Une page de Wikiversité, la communauté pédagogique libre.
Machine de Turing
Image logo représentative de la faculté
Exercices no1
Leçon : Calculabilité et complexité

Exercices de niveau 17.

Exo préc. :Sommaire
En raison de limitations techniques, la typographie souhaitable du titre, « Exercice : Machine de Turing
Calculabilité et complexité/Exercices/Machine de Turing
 », n'a pu être restituée correctement ci-dessus.




Exercice 1[modifier | modifier le wikicode]

Pour écrire la machine de Turing qui efface les « b » mais pas les « a » et qui s'arrête au premier espace.

Exercice 2[modifier | modifier le wikicode]

É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.