Informatique II - Travaux Pratiques

Série d'exercices no 5

Exercice 5-1 : Turing machine - codage

1. Décrire l'action de la machine de Turing qui présente le jeu de règles suivant.
   L'état de départ est '1'.
   

   1110100101000100110101010001001101000101000100111

Utiliser les codages de machine de Turing tels qu'ils ont été présentés en cours.

Exercice 5-2 : Turing machine - parenthesis checker

Donner le jeu de règles d'une machine de Turing qui vérifie si une suite de parenthèses jusqu'à n=3 jeux de parenthèses est balancée ou non. La machine renvoie R=1 si la suite de parenthèses est balancée, c'est-à-dire si les parenthèses sont correctement fermées (par ex "()(()())"). La machine renvoie R=0 si la suite de parenthèses est mal balancée (par ex "())((") ou s'il y a plus que n=3 jeux de parenthèses (par ex "(((())))").

Est-il possible de généraliser cette machine de Turing pour un nombre arbitraire de parenthèses ?

Exercice 5-3 : Problème de `Halting'

• Le programme H sait determiner l'arrêt (oui ou non) d'un programme P arbitraire avec une entrée X arbitraire. Le programme est identifié par son numéro nP et l'entrée par son numéro nX dans la liste correspondante.
• Le programme D utilise le résultat de H. L'entree de H est un nombre entier appelé n. D applique H au programme avec nP = n en utilisant une entrée avec nX = n. Si H dit oui, le programme D entre dans une boucle infinie et ne s'arrête jamais. Si H dit `non' le programme D finit avec une sortie égale 1.
• Supposons alors que le programme D a le numéro n=2387 dans la liste de tous les programmes. Construire la contradiction.

Exercice 5-4a : Problèmes de décidabilité

Quelle est la différence entre un problème décidable et un problème non-décidable?

Donner une description des problèmes suivants, et dire s'ils sont décidables ou non.

• Halting problem
• Tri d'une liste de chaînes de caractères
• Vérification de programme
• Tiling problem
• Décider si un nombre est premier ou non
• Problème du voyageur de commerce

Qu'est-ce qu'un problème de décision ? Parmi les problèmes cités ci-dessus, lesquels sont des problèmes de décision ?

Exercice 5-4b : Réflexion sur la décidabilité et l'intelligence 

Discuter la phrase suivante:

I am not a computer and here is the reason.
A computer, or at least anything we would want to call a 
computer, cannot be programmed to solve an undecidable
problem, such as the halting problem. Given enough time,
though, I am sure I could solve (using my human brain) any  
individual instance of one of these undecidable problems. 
After all, decidability or undecidability just asks if you 
can solve these, not how long will it take. The way I am 
better than a computer is that as a human I am creative and
I can tailor my solution to the particular instance rather 
than having to use the same procedure on all instances.
I have enough confidence in my problem-solving abilities to 
assert that with enough time I could solve any instance of 
the Halting problem. Therefore my brain is more powerful than 
any computer.

Que pensez-vous de ce discours. Etes-vous d'accord avec l'étudiant? Justifiez.

Exercice 5-5 : Turing machine - codage

Regardez de nouveau la machine de Turing de l'exercice 5.1., qui présente le jeu de règles suivant.

Reprendre ensuite le même jeu de règles et le transformer suivant le code à mettre sur le ruban d'une machine de Turing universelle (8 symboles différents).

Utiliser les codages de machine de Turing tels qu'ils ont été présentés en cours.

Exercice 5-6; Machine de Turing universelle - partie `address finder'.

S110x1ZY000x1x111x1x1Y100x1x111x1x1Y110x1x111x1x1Z

La position initiale de la tête de lecture est sur le premier Z.
L'état initial est l'état L tout à gauche sur le graphe au tableau.

Notons: il y a 3 règles, et c'est la 3e qui doit être trouvée.

Exercice 5-7 : Turing machine - copie d'une séquence (difficile, finir à la maison)

Donner les règles d'une machine de Turing qui copie les symboles du ruban, depuis son extrémité gauche jusqu'à un symbole spécial (par exemple "!") et les recopie à la droite de ce même symbole spécial.

Au départ, le début de la séquence est marqué par un "s" et le symbole spécial "!" est suivi par des blancs à sa droite. L'alphabet, les symboles à recopier sont l'ensemble des symboles {0,1}. Cependant, la machine est capable de lire et écrire 6 symboles différents {0,1,s,X,Y,!}.

Exemple :

Entrée : 10110!bbb...
Sortie : 10110!10110bbb...

Quelques conseils : Il faut se souvenir des symboles qui ont déjà été copiés. Pour faire cela on peut par exemple les remplacer par d'autres symboles.

Donner ensuite le schéma de la machine correspondante à états finis.

Expliquer pourquoi une machine de copie est un composant important d'une machine de Turing universelle.

Quelles sont les autres composants essentiels d'une machine de Turing universelle?