generator and source files for the compudanzas.net site
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Warning: Missing License
We looked everywhere, but we couldn't find an OSI- or FSF-approved Free Software or Content License, which is a requirement for hosting content on Codeberg.
Learn about why no license or custom ones are a bad idea and get started on the docs.
Please consider carefully if you want to use (parts of) this project, as doing so might put you in legal trouble.
 
 
 
 
 

294 lines
4.2 KiB

# turingsim
a quick and dirty turing machine simulator, written in C89.
# the code
=> https://tildegit.org/sejo/turingsim 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}
```
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.