turingsim

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

the code

#include 

#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

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
low-level
máquinas de turing
jarotsim
d-turing

meta
compudanzas
contact
colophon
this work is dedicated to the public domain. CC0 1.0