Scribd
Importer
151 vues4 pages

Exercices sur les Machines de Turing

Le document présente des exercices sur la programmation de machines de Turing, incluant des diagrammes pour diverses opérations sur des chaînes binaires et des calculs comme le PGCD. Il contient également des éléments de réponse pour simuler le fonctionnement d'une machine de Turing. Les exercices portent sur l'ajout, la soustraction, et des conditions sur les chaînes binaires.

Transféré par

Amine SNOUSSI
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PPTX, PDF, TXT ou lisez en ligne sur Scribd
151 vues4 pages

Exercices sur les Machines de Turing

Le document présente des exercices sur la programmation de machines de Turing, incluant des diagrammes pour diverses opérations sur des chaînes binaires et des calculs comme le PGCD. Il contient également des éléments de réponse pour simuler le fonctionnement d'une machine de Turing. Les exercices portent sur l'ajout, la soustraction, et des conditions sur les chaînes binaires.

Transféré par

Amine SNOUSSI
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PPTX, PDF, TXT ou lisez en ligne sur Scribd

Programmation d’une MT

Devoir Libre 1
Exercice 1:
Donner les diagrammes de machines de Turing correspondants aux
énoncés suivants
1) Ajouter d’ 1 à droite d’une chaine binaire,
2) Ecrire une chaine infinie 101010..
3) Soustraction unaire avec x<y

4) Écrire 1 à droite si une chaine binaire contient un nombre pair de 0


5) Écrire 1 à droite si une chaine binaire contient un nombre pair de 0 et un nombre
pair de 1
6) PGCD de deux nombres unaires en appliquant l’algorithme d’Euclide
TANT QUE x>0 FAIRE
Si (y>x) alors pgcd<- y-x
sinon pgcd<- x-y
FIN TANT QUE
Programmation d’une MT
Devoir Libre 1
Exercice 2: Que calcule la machine de Turing suivante? (Penser à faire une simulation)
B / n, 
a / a, R a / B, L

b / b, R b / a, R B / B, L

a / a, R
a / b, R B / a, R
b / a, R

b / y, 
a / a, R
b / a, R

B / B, L

b / n, 

2
a / B, L
Programmation d’une MT
Eléments de réponses
Diagramme pour toute fin utile dans l’exercices 1:
0 / 0, R
B/B, R

Q3 1/
0, R
, R
1/ 1
0/ 0, L
B/ B, L
Q2 1/
0, L L Q4
1 /1,

Q1
B/ B, R
B / B, L

B / 1, B/ 1,
Q5 Qf Q6
Programmation d’une MT
Eléments de réponses
Exécution pour toute fin utile dans l’exercices 2:

q4 q1

B 1 0 B 01 1 B B 1 0 B 0 1 1 B

q2 q5

B 0 0 B 0 1 1 B B B 0 0B 0 1 1 B

Vous aimerez peut-être aussi