💾 Archived View for compudanzas.net › turingsim.gmi captured on 2022-03-01 at 16:05:58. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2022-01-08)
-=-=-=-=-=-=-
a quick and dirty turing machine simulator, written in C89.
#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;
}
to build:
cc -std=c89 -Wall turingsim.c -o turingsim
to run with an input file:
./turingsim parentesis.txt | less
the line-based fields are:
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
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.
updated on 12022-02-10
text, images, and code are shared with the peer production license