Projets
  Déroulement du projet MT
  • Le projet est à réaliser par groupe de 4 (pas nécessairement dans le même groupe de TD)
  • Les soutenances de projet auront lieu le vendredi 14/04/2017 sur le créneau d'APNEE
  • Tous les membres du groupe doivent être présent le jour de la soutenance
  • La soutenance consiste en
    1. une présentation de 5 min (où chacun présente ce qu'il a fait)
    2. une démo de 5 min (qui doit être bien préparée)
    3. une séance de questions individuelle (sans limite de temps)
  • Le projet comporte plusieurs étapes : chaque étape rapporte 1 point si elle est réussie
  • La note de projet est individuelle : elle correspond ? la note du groupe +/- 3 points selon vos réponses aux questions
  Les étapes du projet "Des Machines de Turing pour de vrai"

  • 2017 : tous les fichiers du projet dans une archive : MT2017.tar

    • NEW 10/04/2017
      • Correction d'un bug (ligne 92) dans Band.ml
      • Le module Alphabet.Bits utilise Bit_Vector.Made_of pour créer exactement les bit vectors dont vous avez besoin
    • NEW 03/04/2017: pour compiler sur Mandelbrot
      • le fichier Bytes.ml qui manquait pour compiler sur Mandelbrot.
        N'oubliez pas de l'ajouter dans le Makefile dans en tête de la liste des modules à compiler
        MODULES = Bytes Fresh ...
    • NEW 27/03/2017:
      • le fichier Emulator.ml avec un début de solution pour vous guider
    • NEW 21/03/2017:
      • le fichier Color.ml modifié pour supprimer la dépendance à la bibliothèque Graphics
      • le fichier Configuration.ml modifié pour supprimer la dépendance au module Date et à la bibliothèque Unix
      • le fichier Makefile modifié pour supprimer la dépendance au module Date et aux bibliothèques unix.cma et graphics.cma
    • Simulation de MT opérant sur un alphabet S à 2n symboles par des MT sur l'alphabet {B,D} (Emulator.ml à compléter)
      1. Conversion d'une bande sur S en une bande équivalente sur {B,D} et inversement
      2. Simulation d'une transition de MT opérant sur S en une séquence de transitions opérant sur {B,D}
      3. Comparaison du résultat après chaque simulation d'une transition
      4. Simulation de MT sur l'alphabet {B,Z,U} par {B,D,S} (pour la mise au point) (exemple)
      5. Simulation de MT sur un alphabet S à 2n symboles par des MT sur l'alphabet {B,D}
    • Une MT qui effectue la beta-réduction (LC_by_MT.ml à compléter)
      1. MT (à 3 bandes) qui sélectionne un terme bien parenthésés
      2. MT (à 3 bandes) qui effectue la substitution de chaque occurence d'une variable par un terme
      3. MT (à 4 bandes) qui effectue la substitution de chaque occurence d'une variable par un terme en tenant compte du masquage de variable par un lambda
      4. un affichage HTML plus élégant
      5. Simulation binaire de la MT qui effectue la beta-réduction
    • Bonus: (***) Génération de la MT binaire (avec fusion de certains états cf. TD1)
  • 2015
    1. Un interpréteur de Machine de Turing à une bande
    2. Des examples de MT à une bande
    3. Un interpréteur de Machine de Turing à plusieurs bandes
    4. Des examples de MT à plusieurs bandes
    5. Une interface graphique
    6. Des transitions génériques dans les MT
  Programmer en Ocaml
Responsable du site : Michaël PÉRIN