Informatique II

Informatique II - Travaux Pratiques

Série d'exercices pratiques no 3

Partie 1 : Turing machine (plus difficile, demande beaucoup de réflexion)

Les applets des machines de Turing ne fonctionnent pas toujours. En utilisant qqs tricks, on arrive a les faire fonctionner. Le truc pour reussir est le suivant:

1) fermer netscape
2) rouvrir netscape et la page de l'applet
3) un certificat apparait, cliquer sur le bouton ALWAYS

Pour ces exercices, il faut ouvrir le fichier TM.dat, qui contient le code et l'initialisation pour plusieurs machines de Turing.
Ensuite créer un fichier pour chaque machine (commande import dans l'applet), copier et coller les règles et l'appliquer avec un OK. Pour l'initialisation copier et coller.

Si nécessaire renouveller la page web pour pouvoir charger les fichiers enregistrés dans l'applet.

Pour utiliser l' "appletviewer", utiliser la commande suivante :
appletviewer http://diwww.epfl.ch/mantra/ex/course/8/1/index.html

Partie 1 : (suite) Turing machine

Dans ces exercices, le ruban de la machine ITM est infini seulement vers la droite, contrairement au cas général présenté en cours. A gauche, le ruban a une extrémité. C'est à cette extrémité que se situe la position de départ de la machine.
  1. Pour la question 1., le ruban de la machine étant fini à gauche, il s'agit d'effacer le ruban à droite de la position de départ jusqu'à la fin du code. La fin du code sur le ruban peut par exemple être indiquée par un (ou plusieurs) blanc(s). L'alphabet à considérer, les symboles à effacer sont {0,1}.
    Si l'on avait souhaité s'attacher au cas général d'une machine qui présente un ruban infini, il aurait d'abord fallu aller chercher vers la gauche le début du code à effacer.
  2. Pour la question 2., il s'agit de représenter les entiers intervenant dans la soustraction par le nombre correspondant de "1" (par exemple le nombre "5" est représenté par le code "11111").
    Il convient ensuite de séparer les deux nombres à soustraire par un symbole, par exemple "-", puis déterminer le début du code à l'aide d'un symbole spécial (par exemple "s").

    Exemple : 

    code :           s111-11bbb... -> s1bbb...
signification :  3 - 2  -> 1

retour à la page principale du cours : Informatique II
Saskia Delpretti
Last modified: Thu Apr 22 12:22:36 CEST 2004