TP1 - Machines de Turing simples
Grands concepts d’informatique fondamentale
L3 Informatique - Semestre printemps - Année 2022-2023
Université Côte d’Azur
Christophe Crespelle
[Link]@[Link]
Pour faire les TP, vous utiliserez le simulateur de machine de Turing de [Link]
qui se trouve a l’adresse suivante : [Link] Un
des gros avantages de ce simulateur est qu’il est propose sous forme d’interface web, ce
qui ne necessite aucune installation speciale sur votre machine et fonctionne quel que soit
votre systeme d’exploitation.
Vous devez ecrire votre machine de Turing dans la fenetre centrale a fond blanc. La
syntaxe pour ce faire est decrite en dessous de la fenetre. Une fois votre machine ecrite,
vous pourrez la lancer sur un mot que vous entrez dans le champ initial input de la fenetre
de controle a fond gris qui se trouve a droite. Vous pouvez ensuite cliquer sur Run pour
voir la machine s’executer sur ce mot d’entree, ou sur Step pour faire evoluer la machine
d’une seule etape (c.a.d. transition) a chaque clic.
Dans cette fenetre se trouve un lien Advanced options qui vous permet de choisir l’etat
initial de la machine et le type de machine utilise. Pour le type, selectionnez Semi-infinite
tape, qui est la machine a ruban infini a droite seulement, que nous avons utilisee en
cours.
Deux choses tres importantes auxquelles vous devrez preter une grande attention lorsque
vous concevez des machines de Turing :
— Utilisez des noms d’etats qui disent explicitement ou en est la machine dans son
calcul et ce qu’elle cherche a faire dans cet etat, ex. : 1er-a-lu pour "premier a
lu", rec-proc-b-droite pour "recherche du prochain b vers la droite".
— Ecrivez exclusivement des machines qui sont deterministes, c’est a dire dans
lesquelles au plus une transition peut s’appliquer a partir d’une configuration don-
nee. Pretez y une attention toute particuliere lorsque vous utilisez le joker *. Par
exemple, une machine contenant les deux regles suivantes n’est pas deterministe :
q1 a b R q2
q1 * * R q2
Exercice 1.
a. Ecrivez une machine de Turing qui decide le langage des mots contenant une nombre
pair de ’a’.
b. Ecrivez une machine de Turing qui decide le langage des mots contenant un nombre
pair d’occurrences de la sous-chaine "ab".
Exercice 2.
Ecrivez une machine de Turing qui decide le langage {an bn | n ∈ N}.
Exercice 3.
Ecrivez une machine de Turing qui decide le langage {an bn cn | n ∈ N}.
Exercice 4.
Ecrivez une machine de Turing qui reconnait les palindromes.
Exercice 5.
a. Ecrivez une machine de Turing qui decale le contenu de son ruban d’une case vers
la droite et place un caractere special de debut de ruban dans la premiere case du
ruban.
b. Ecrivez une machine de Turing qui decale le contenu de son ruban d’une case vers
la gauche en ecrasant le contenu de la premiere case du ruban.
c. Faire une machine de Turing qui renverse le mot contenu sur son ruban.
Exercice 6.
a. Ecrivez une machine de Turing qui a partir de l’ecriture unaire d’un nombre ecrit
son ecriture binaire au debut du ruban, precedee par un caractere special de debut de
ruban.
b. Ecrivez une machine de Turing qui effectue la conversion reciproque : de l’ecriture
binaire vers l’ecriture unaire.
Exercice 7.
a. Ecrivez une machine de Turing qui a partir d’un nombre donne sur le ruban en
eriture decimale le remplace par le quotient et le reste de la division par 2 de ce
nombre, separes par un caractere special.
b. Ecrivez une machine de Turing qui calcule l’ecriture binaire d’un nombre donne en
ecriture decimale.
Exercice 8.
a. Ecrivez une machine de Turing qui ajoute un a un nombre, en ecriture decimale.
b. Ecrivez une machine de Turing qui effectue la multiplication par 2 d’un nombre,
en ecriture decimale.
c. Ecrivez une machine de Turing qui calule l’ecriture decimale un nombre ecrit en
binaire.
Exercice 9.
Ecrivez une machine de Turing qui effectue la divison euclidienne de D ∈ N par d ∈ N∗
dans les entiers naturels. La machine prendra en entree les deux nombres D ≥ 0 et
d > 0 en ecriture binaire separes par un # et ecrira a la suite sur le ruban, separe par
un #, le quotient q et le reste r de la division, toujours separes par un #. Vous pourrez
ajouter un caractere $ pour marquer le debut du ruban si cela vous aide.
Rappel : q et r sont definis comme l’unique couple d’entiers naturels tels que D = qd+r
et r < d.