💾 Archived View for compudanzas.net › turingsim.gmi captured on 2022-06-11 at 20:44:53. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

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:

initial state
inital tape
initial position of head on tape (starting at 0)
number of rules
list of rules, in the form: state, symbol, new state, new symbol, direction (even is right, odd is left)
maximum number of simulation steps

example input file

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

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

jarotsim