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 :

une bande qui contient les données et le résultat. La longueur est fixée dans tape_size pour arrêter la machine en cas de boucle infinie. (exemple historique donné par Turing)
La position de lecture de la bande est initialisée au premier caractère.
La position de la tête de lecture est indiquée en vidéo inverse.
Le caractère blanc est le caractère '\0'.
La table de transition est lue sur le disque.
Le programme affiche successivement l'état de la bande et la règle qui sera appliquée.

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.

/* turing.h
(C) 2020 by marnout à free pt fr  Released under the GPL
*/
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//#include <assert.h>
#include <stdarg.h>
 
#define REVERSE "\x1b[7m"
#define NORMAL "\x1b[0m"
#define BLK '\0' 
 
int tape_size = 72;
 
typedef struct tape {
   char *cells;        // array of symbols
   int pos;            // position for read and write symbol
} tapes;
 
void tape_init();
 
/** 
tape_print(tape) prints the tape
*/
void tape_print(tapes);
 
/**
tape_input(&tape) input from stdin a tape
returns number of characters read
*/
int tape_input(tapes *);
 
typedef struct rules {
   int state;          // machine state
   char read;          // char read
   char write;         // char write
   char mv;
   int new_state;
} rules;
 
/**
Table of rules queue
*/
typedef struct table { 
   rules rule;
   struct table *next;
} *tableptr;
 
/**
rule_print(rule) to print a rule
*/
void rule_print(rules);
 
/**
table_get(filename, &table) gets rules from file
filename: file to read
table to store
*/
void table_get(char*, tableptr *);
 
/**
The Turing machine
*/
void Turing_machine(tableptr, tapes);
/*
Utilitie to abort program
Source: site www.suckless.org, program surf, file common.c
*/
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 :

Alloue la mémoire nécessaire
Remplit le tableau de caractères '\0'.
Position la lecture à 0.

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.

state état de la machine
read caractère lu
write caractère à écrire
mv déplacement de la tête de lecture : + à droite, - à gauche, autre reste sur place
new_state état de la machine à la fin de l'application de la 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.

/*
:w | !gcc % -o .%<
:w | !gcc % -o .%< && ./.%<
*/
 
#include "turing.h"
 
int main(int argc, char *argv[]) 
{
	char *fn = argc == 2 ? argv[1] : "add_1";
	tapes tape;
	tape_init(&tape);
	printf("Turing machine, table: %s\n", fn);
	tableptr table;
	table_get(fn, &table);
 
	while(tape_input(&tape)) 
		Turing_machine(table, tape);
	free(tape.cells);
}
 
void table_get(char *fn, tableptr * table)
{
	FILE *fp = fopen(fn, "r");
	if(fp == NULL) die("Failed to open %s\n", fn);
	int n, s, ns;
	char r[4], w[4], mv, line[81];
	// emty stack if any
	while(*table != NULL) {
		tableptr top = (*table)->next;;
		free(*table);
		*table = top;
	}
	// last 
	tableptr last = *table;
	// read file line by line
	while(fgets(line, 80, fp)) {
		rules rule;
		n = sscanf(line, "%d%s%s %c%d", 
				&(rule.state), &r, &w, &(rule.mv), &(rule.new_state));
		if(n != 5)
			die("%s not match a rule\n", line);
 
		rule.read = strcmp(r, "BLK") ? *r : '\0';
		rule.write = strcmp(w, "BLK") ? *w : '\0';
		//Queue
		tableptr node = (tableptr)malloc(sizeof(struct table));
		node->rule = rule;
		node->next = NULL;
		if(*table == NULL)
			*table = node;
		else
			last->next = node;
		last = node;
	}
	fclose(fp);
}
 
void Turing_machine(tableptr table, tapes tape)
{
	int state = 1;
	char c, read[4] = "";
	rules rule;
	tape_print(tape);
	tableptr p;
	while(state != 0 && tape.pos < tape_size) {
		// char read
		if(tape.pos < 0 || tape.pos >= strlen(tape.cells)) 
			c = BLK;
		else 
			c = tape.cells[tape.pos];
		// find rule matching state and c
		for(p = table; p != NULL; p = p->next)
			if(p->rule.state == state && p->rule.read == c) break;
 
		if(p == NULL) { // rule not found
			if(c == BLK) strcpy(read, "BLK"); else *read = c;
			die("rule state = %d and read = %s not found\n", state, read);
		}
 
		rule = p->rule;
		rule_print(rule);
		// write rule.write
		if(tape.pos >= 0) 
			tape.cells[tape.pos] = rule.write;
		else {
			if(strlen(tape.cells) >= tape_size)
				die("tape overflow\n");
			memmove(tape.cells + 1, tape.cells, strlen(tape.cells));
			tape.cells[0] = rule.write;
		}
		// move
		if(rule.mv == '-') (tape.pos)--; 
		else if(rule.mv == '+') (tape.pos)++;
		// new state
		state = rule.new_state;
		tape_print(tape);
	}
}
 
void tape_init(tapes *tape)
{
	tape->cells = (char *)malloc(tape_size + 1);
	memset(tape->cells, BLK, tape_size + 1);
	tape->pos = 0;
}
 
void tape_print(tapes tape)
{
	if(tape.pos < 0) {
		printf("%s %s%s\n", REVERSE, NORMAL, tape.cells);
	} else if (tape.pos >= strlen(tape.cells)) {
		printf("%s%s %s\n", tape.cells, REVERSE, NORMAL);
	} else {
		char c = tape.cells[tape.pos];
		char *dup;
		printf(dup = strndup(tape.cells, tape.pos));
		printf("%s%c%s", REVERSE, c, NORMAL);
		puts(tape.cells + tape.pos + 1);
		free(dup);
	}
}
 
int tape_input(tapes *tape)
{
	ssize_t nread;
	char *line = NULL;
	size_t len = 0;
 
	printf("\ninitial tape: ");
	memset(tape->cells, BLK, tape_size + 1);
	nread = getline(&line, &len, stdin);
	if(nread <= 1) return 0;
	--nread;
	line[nread] = 0; // take rid of new line character
	strcpy(tape->cells, line);
	return nread;
 
}
 
void rule_print(rules rule)
{
	printf("{%2d, ", rule.state);
	if(rule.read) printf("%3c, ", rule.read); else printf("BLK, ");
	if(rule.write) printf("%3c, ", rule.write); else printf("BLK, ");
	printf("%c, ", rule.mv);
	printf("%d}\n", rule.new_state);
}
 
/*
Source : 
program: surf, file: common.c site: http://www.suckless.org
 */
void die(const char *errstr, ...)
{
	va_list ap;
 
	va_start(ap, errstr);
	vfprintf(stderr, errstr, ap);
	va_end(ap);
	exit(1);
}

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