Logiciel pour le simulateur de machine de Turing

Voici la liste des programmes disponibles. Pour charger un programme dans le simulateur, utiliser simplement copier-coller à partir du fichier texte (seul un retournement de la demande sur le marché pourrait me conduire à ajouter au simulateur un menu pour lire ou écrire dans un fichier...) ; appuyer sur le bouton Restaurer la configuration initiale avant de lancer l'exécution.

  1. Test d'égalité de deux mots.

  2. Addition en base 2, avec une variante (écrite par François Seimandi) concernant le traitement de la retenue.

  3. Addition récursive.

  4. Crible d'Eratosthène : si la configuration initiale comporte n marques, en fin d'exécution les indices des cellules marquées b ou c constituent la liste des nombres premiers inférieurs à n ; l'indice de la cellule marquée c est le plus petit nombre premier dont le carré est supérieur à n.

    Cet exemple montre que l'absence d'instruction arithmétique dans le modèle de calcul des machines de Turing, n'empêche pas de réaliser, avec peu de règles, un calcul relativement sophistiqué.

  5. Examen de la première session 2005-2006 : simulation d'une instruction LOAD pour un seul symbole, extension au cas de k symboles, et simulation d'une instruction STORE.

  6. Devoir 2005 : exemple de simulation d'une machine avec un alphabet de 4 caractères (0, 1, x et blanc) par une machine avec un alphabet de deux caractères (a et b) ; voir l'énoncé pour les détails.

    Le fichier contient deux ensembles de règles, l'un pour la machine simulée, l'autre pour la machine simulante ; si on exécute le fichier tel quel, c'est la seconde configuration initiale qui est prise en compte ; il faut "commenter" la ligne Init aaaabbbbba… pour que le simulateur lise la première configuration initiale Init 110… lorsqu'on appuie sur le bouton de droite (Rembobiner, c'est-à-dire restaurer la configuration initiale).

    Cet exemple illustre une propriété générale des machines de Turing : un alphabet minimal (deux caractères, dont le caractère blanc) suffit pour obtenir un modèle universel.