jeudi 18 juin 2020, quatre-vingt ans après.

Machine de Turing

Implémentation en C d'une machine de Turing

Introduction

Il existe de nombreuses introductions à la machine de Turing dont : Wikipedia, Interstices.

Ici nous utiliserons :

Le programme se lance avec la commande turing table où table est la table de transition à appliquer. Il demande le contenu initial de la bande à lire. Une saisie vide (Entrée tout seul) arrête le programme.

La table de transition est l'ensemble des règles qu'applique la machine à chaque étape. Une règle comprend : l'état de la machine au moment de la lecture, le caractère lu, le caractère à écrire, le mouvement de la tête de lecture, et l'état de la machine à la fin de l'application de la règle.

Remarque

À la différence de certaines versions, ici c'est la tête de lecture qui se déplace sur le ruban et non le ruban qui glisse sous la tête de lecture. Ceci entraine qu'un mouvement à droite avance la lecture d'une case sur la droite. J'ai fait ce choix, parce que n'ayant jamais su ma droite de ma gauche, je n'avais pas besoin de complications supplémentaires.

Le fichier turing.h

Le fichier peut être téléchargé ici : turing.h.

 1 /* turing.h
 2 (C) 2020 by marnout à free pt fr  Released under the GPL
 3 */
 4 
 5 #include <stdio.h>
 6 #include <stdlib.h>
 7 #include <string.h>
 8 //#include <assert.h>
 9 #include <stdarg.h>
10 
11 #define REVERSE "\x1b[7m"
12 #define NORMAL "\x1b[0m"
13 #define BLK '\0' 
14 
15 int tape_size = 72;
16 
17 typedef struct tape {
18    char *cells; // array of symbols
19    int pos; // position for read and write symbol
20 } tapes;
21 
22 void tape_init();
23 
24 /** 
25 tape_print(tape) prints the tape
26 */
27 void tape_print(tapes);
28 
29 /**
30 tape_input(&tape) input from stdin a tape
31 returns number of characters read
32 */
33 int tape_input(tapes *);
34 
35 typedef struct rules {
36    int state; // machine state
37    char read; // char read
38    char write; // char write
39    char mv;
40    int new_state;
41 } rules;
42 
43 /**
44 Table of rules queue
45 */
46 typedef struct table {
47    rules rule;
48    struct table *next;
49 } *tableptr;
50 
51 /**
52 rule_print(rule) to print a rule
53 */
54 void rule_print(rules);
55 
56 /**
57 table_get(filename, &table) gets rules from file
58 filename: file to read
59 table to store
60 */
61 void table_get(char*, tableptr *);
62 
63 /**
64 The Turing machine
65 */
66 void Turing_machine(tableptr, tapes);
67 /*
68 Utilitie to abort program
69 Source: site www.suckless.org, program surf, file common.c
70 */
71 void die(const char *, ...);

Commentaires

Ligne 15

Longueur de la bande (à ajuster selon les besoins). Le tableau cells étant déclaré dynamiquement, on pourrait remplacer la ligne 88 par quelque chose comme :

(char*)realloc(tape.cells, tape_size = tape_size + 64);

et supprimer le contrôle de la ligne 66, pour s'affranchir du débordement et simuler un ruban de longueur infinie. La seule limite étant alors la mémoire disponible sur le tas.

Lignes 17 à 20

La structure tape contient le tableau de caractères cells et la position courante de lecture écriture pos.

Ligne 22

Initialise la bande :

Ligne 33

Fonction de saisie de la bande initiale. Les caractères sont limités selon la table de transition. Pour quitter le programme saisir une chaine vide.

Lignes 35 à 41

Structure définissant une règle.

Lignes 46 à 49

Structure de type pile ou file (stack or queue) qui recevra la table de transition. Voir lignes 46 à 54 pour l'empilement, les lignes 73 et 74 pour le parcours, et les lignes 29 à 33 pour vider la file.

Ligne 54

Affichage d'une règle sous la forme {state, read, write, mv, new_state}.

Exemple : {2, 1, 1, +, 3}

Ligne 61

Lecture de la table de transition depuis le disque dur.

ligne 66

La machine de Turing proprement dite.

Ligne 71

Utilitaire emprunté à l'excellent site suckless qui permet d'abandonner le programme en laissant un message. Très pratique.

Le code source turing.c

Le code source est disponible ici : turing.c.

  1 /*
  2 :w | !gcc \% -o .\%<
  3 :w | !gcc \% -o .\%< && ./.\%<
  4 */
  5 
  6 #include "turing.h"
  7 
  8 int main(int argc, char *argv[])
  9 {
 10    char *fn = argc == 2 ? argv[1] : "add_1";
 11    tapes tape;
 12    tape_init(&tape);
 13    printf("Turing machine, table: \%s∖n", fn);
 14    tableptr table;
 15    table_get(fn, &table);
 16 
 17    while(tape_input(&tape))
 18      Turing_machine(table, tape);
 19    free(tape.cells);
 20 }
 21 
 22 void table_get(char *fn, tableptr * table)
 23 {
 24    FILE *fp = fopen(fn, "r");
 25    if(fp == NULL) die("Failed to open \%s∖n", fn);
 26    int n, s, ns;
 27    char r[4], w[4], mv, line[81];
 28    // emty stack if any
 29    while(*table != NULL) {
 30       tableptr top = (*table)->next;;
 31       free(*table);
 32       *table = top;
 33    }
 34    // last 
 35    tableptr last = *table;
 36    // read file line by line
 37    while(fgets(line, 80, fp)) {
 38       rules rule;
 39       n = sscanf(line, "\%d\%s\%s \%c\%d",
 40          &(rule.state), &r, &w, &(rule.mv), &(rule.new_state));
 41       if(n != 5)
 42          die("\%s do not match a rule∖n", line);
 43 
 44       rule.read = strcmp(r, "BLK") ? *r : '\0';
 45       rule.write = strcmp(w, "BLK") ? *w : '\0';
 46       //Queue
 47       tableptr node = (tableptr)malloc(sizeof(struct table));
 48       node->rule = rule;
 49       node->next = NULL;
 50       if(*table == NULL)
 51          *table = node;
 52       else
 53          last->next = node;
 54       last = node;
 55    }
 56    fclose(fp);
 57 }
 58 
 59 void Turing_machine(tableptr table, tapes tape)
 60 {
 61    int state = 1;
 62    char c, read[4] = "";
 63    rules rule;
 64    tape_print(tape);
 65    tableptr p;
 66    while(state != 0 && tape.pos < tape_size) {
 67       // char read
 68       if(tape.pos < 0 || tape.pos >= strlen(tape.cells))
 69          c = BLK;
 70       else
 71          c = tape.cells[tape.pos];
 72       // find rule matching state and c
 73       for(p = table; p != NULL; p = p->next)
 74          if(p->rule.state == state && p->rule.read == c) break;
 75 
 76       if(p == NULL) { // rule not found
 77          if(c == BLK) strcpy(read, "BLK"); else *read = c;
 78          die("rule state = \%d and read = \%s not found∖n", state, read);
 79       }
 80 
 81       rule = p->rule;
 82       rule_print(rule);
 83       // write rule.write
 84       if(tape.pos >= 0)
 85          tape.cells[tape.pos] = rule.write;
 86       else {
 87          if(strlen(tape.cells) >= tape_size)
 88             die("tape overflow∖n");
 89          memmove(tape.cells + 1, tape.cells, strlen(tape.cells));
 90          tape.cells[0] = rule.write;
 91       }
 92       // move
 93       if(rule.mv == '-') (tape.pos)--;
 94       else if(rule.mv == '+') (tape.pos)++;
 95       // new state
 96       state = rule.new_state;
 97       tape_print(tape);
 98    }
 99 }
100 
101 void tape_init(tapes *tape)
102 {
103    tape->cells = (char *)malloc(tape_size + 1);
104    memset(tape->cells, BLK, tape_size + 1);
105    tape->pos = 0;
106 }
107 
108 void tape_print(tapes tape)
109 {
110    if(tape.pos < 0) {
111       printf("\%s \%s\%s∖n", REVERSE, NORMAL, tape.cells);
112    } else if (tape.pos >= strlen(tape.cells)) {
113       printf("\%s\%s \%s∖n", tape.cells, REVERSE, NORMAL);
114    } else {
115       char c = tape.cells[tape.pos];
116       char *dup;
117       printf(dup = strndup(tape.cells, tape.pos));
118       printf("\%s\%c\%s", REVERSE, c, NORMAL);
119       puts(tape.cells + tape.pos + 1);
120       free(dup);
121    }
122 }
123 
124 int tape_input(tapes *tape)
125 {
126    ssize_t nread;
127    char *line = NULL;
128    size_t len = 0;
129 
130    printf("∖ninitial tape: ");
131    memset(tape->cells, BLK, tape_size + 1);
132    nread = getline(&line, &len, stdin);
133    if(nread <= 1) return 0;
134    --nread;
135    line[nread] = 0; // take rid of new line character
136    strcpy(tape->cells, line);
137    return nread;
138 
139 }
140 
141 void rule_print(rules rule)
142 {
143    printf("{\%2d, ", rule.state);
144    if(rule.read) printf("\%3c, ", rule.read); else printf("BLK, ");
145    if(rule.write) printf("\%3c, ", rule.write); else printf("BLK, ");
146    printf("\%c, ", rule.mv);
147    printf("\%d}∖n", rule.new_state);
148 }
149 
150 /*
151 Source : 
152 program: surf, file: common.c site: http://www.suckless.org
153 */
154 void die(const char *errstr, ...)
155 {
156    va_list ap;
157 
158    va_start(ap, errstr);
159    vfprintf(stderr, errstr, ap);
160    va_end(ap);
161    exit(1);
162 }
163 

Commentaires

Lignes 8 à 20

Entrée du programme.

Ligne 10 : si un argument est présent sur la ligne de commande, c'est cette table de transition qui est utilisée. Par défaut c'est add_1.

Ligne 15 : Lecture de la table de transition depuis le disque dur.

Ligne 19 : Le tableau cells a été alloué dynamiquement.

Lignes 22 à 57

Lignes 26 et 27 : ouverture du fichier

Linges 29 à 33 : on vide la file (la pile) table.

Ligne 37 à 55 : Lecture du fichier ligne par ligne.

Ligne 39-40 : Lecture des champs présents sur la ligne.

Ligne 41-42 : Contrôle de la bonne lecture des champs. Abandon sinon.

Lignes 44 et 45 : interprétation du symbole BLK.

Lignes 47 à 54 : On empile la règle lue dans la file.

Lignes 59 à 99

La machine proprement dite.

Ligne 66 : La machine s'arrête soit lorsqu'elle se trouve dans l'état 0 soit lorsque le ruban déborde (Exemple historique ci-dessous).

Lignes 68 à 71 : Caractère lu. (blanc avant le début ou après la fin)

Ligne 73-74 : Recherche de la règle dans la table de transittion.

Lignes 76 à 79 : En cas d'échec, on abandonne.

Ligne 82 : Affichage de la règle qui sera appliquée.

Lignes 84 à 91 : Ecriture du caractère. Si la position est avant le début du contenu du ruban, le caractère est inséré avant ce début. Contrôle de la place disponible.

Puis viennent le mouvement de la tête de lecture et le changement d'état.

Le résultat est affiché par la ligne 97.

Exemples de tables de transition

Dans ces exemples les calculs se font en binaire. Les caractères disponibles sont 0 et 1. (le point dans l'exemple historique de Turing). Le caractère «blanc» est noté BLK.

La tête de lecture est placée sur le chiffre le plus à gauche du nombre.

Pour les explications voir les références données en introduction.

Addition de 1

Le ruban contient un nombre binaire. Le but est d'effectuer l'opération + 1.

Le fichier contenant la table de transition est ici : add_1.

1 0 0 + 2
1 1 1 + 2
2 0 0 + 2
2 1 1 + 2
2 BLK BLK - 3
3 0 1 * 0
3 1 0 - 3
3 BLK  1 * 0

Soustraction de 1

Cette fois il s'agit de soustraire 1.

Le fichier correspondant est sub_1.

1 0 0 + 2
1 1 1 + 2
2 0 0 + 2
2 1 1 + 2
2 BLK BLK - 3
3 0 1 - 3
3 1 0 - 0
3 BLK BLK - 0

Exemple historique

C'est l'exemple donné par Turing dans son article de 1936. Il s'agit d'ajouter à un nombre une suite illimitée où alternent 0 et 1 : 010101 ...

Numériquement ça correspond à additionner 1/3 en binaire.

En réalité Turing ne construisait que la suite alternée de 0 et 1.

Le fichier contenant la table de transition est : historic.

1 0 0 + 1
1 1 1 + 1
1 BLK . + 2
2 BLK 0 + 3
3 BLK 1 + 2

Réalisé avec Qlam - LGPL