compudanzas

turingsim

a quick and dirty turing machine simulator, written in C89.

the code

turingsim git repository

#include <stdio.h>

#define TAPE_SIZE 80
#define RULES_SIZE 256

typedef struct {
	char state; /* current state */
	char symbol; /* current symbol */
	int head; /* index of head */
	char tape[TAPE_SIZE]; /* tape of characters */
	int nrules; /* number of rules */
	/* state, symbol, new state, new symbol, direction (even right, odd left ) */
	char rules[RULES_SIZE][5];
} Machine;

Machine m;
int nsteps;

int main(int argc, char *argv[]){
	int i,n=0;
	FILE *f;

	if(!(f = fopen(argv[1], "r"))){
		fprintf(stderr, "failed to load file\n");
		return 1;
	}
	printf("%s\n\n", argv[1]);

	/* read machine description */
	printf("initial state: ");
	fscanf(f,"%c",&m.state);
	printf("%c\n",m.state);

	printf("initial tape: ");
	fscanf(f,"%s",m.tape);
	printf("%s\n",m.tape);

	printf("initial position of head: ");
	fscanf(f,"%d",&m.head);
	m.head = (m.head+TAPE_SIZE)%TAPE_SIZE;
	printf("%d\n",m.head);

	printf("number of rules: ");
	fscanf(f,"%d",&m.nrules);
	printf("%d\n",m.nrules);

	for(i=0; i<m.nrules; i++){
		printf("rule number %d: ",i);
		fscanf(f,"%s",m.rules[i]);
		printf("%s\n",m.rules[i]);

	}
	printf("max number of simulation steps: ");
	fscanf(f,"%d",&nsteps);
	printf("%d\n\n",nsteps);

	/* simulate */
	int irules; /* rules index */
	do{
		printf("step %d\n",n);
		/* print head and state */
		for(i=0; i<m.head; i++)
			printf(" ");
		printf("%c\n",m.state);
		/* print tape: */
		printf("%s\n",m.tape);

		/* get symbol at head position */
		m.symbol = m.tape[ m.head ];

		/* search for corresponding rule */
		irules = -1;
		for(i=0; i<m.nrules && irules<0; i++)
			if(m.rules[i][0] == m.state && m.rules[i][1] == m.symbol)
				irules = i;
		
		if( irules == -1) /* halt if not found */
			printf("halted\n");
		else{ /* update machine otherwise */
			m.state = m.rules[irules][2]; /* new state */
			m.tape[ m.head ] = m.rules[irules][3]; /* new symbol */
			/* move head */
			if( m.rules[irules][4]%2 ) /* if odd, move to left */
				m.head = (m.head-1+TAPE_SIZE)%TAPE_SIZE;
			else /* if even, move to right */
				m.head = (m.head+1)%TAPE_SIZE;
		}

		printf("\n");
	}while( ++n<nsteps && irules != -1);

	return 0;
}

build and run

to build: 

cc -std=c89 -Wall turingsim.c -o turingsim

to run with an input file: 

./turingsim parentesis.txt | less

input file fields

the line-based fields are:

example input file

this input file corresponds to the "comprobador de paréntesis" machine described in máquinas de turing 

a
A(()())A
1
11
a)bX1
a(a(0
aAcA1
aXaX0
b)b)1
b(aX0
bAH00
bXbX1
c(H00
cAH10
cXcX1
80

example output

the output for this example file looks as follows: 

parentesis.txt
initial state: a
initial tape: A(()())A
initial position of head: 1
number of rules: 11
rule number 0: a)bX1
rule number 1: a(a(0
rule number 2: aAcA1
rule number 3: aXaX0
rule number 4: b)b)1
rule number 5: b(aX0
rule number 6: bAH00
rule number 7: bXbX1
rule number 8: c(H00
rule number 9: cAH10
rule number 10: cXcX1
max number of simulation steps: 80

step 0
 a
A(()())A

step 1
  a
A(()())A

step 2
   a
A(()())A

step 3
  b
A((X())A

step 4
   a
A(XX())A

step 5
    a
A(XX())A

step 6
     a
A(XX())A

step 7
    b
A(XX(X)A

step 8
     a
A(XXXX)A

step 9
      a
A(XXXX)A

step 10
     b
A(XXXXXA

step 11
    b
A(XXXXXA

step 12
   b
A(XXXXXA

step 13
  b
A(XXXXXA

step 14
 b
A(XXXXXA

step 15
  a
AXXXXXXA

step 16
   a
AXXXXXXA

step 17
    a
AXXXXXXA

step 18
     a
AXXXXXXA

step 19
      a
AXXXXXXA

step 20
       a
AXXXXXXA

step 21
      c
AXXXXXXA

step 22
     c
AXXXXXXA

step 23
    c
AXXXXXXA

step 24
   c
AXXXXXXA

step 25
  c
AXXXXXXA

step 26
 c
AXXXXXXA

step 27
c
AXXXXXXA

step 28
 H
1XXXXXXA
halted

the 1 written at the end indicates that the parenthesis sequence was well-formed. if there was a parenthesis without its pair, the machine would have written 0 instead.

incoming links