Skip to content

Instantly share code, notes, and snippets.

@darkf darkf/turingmachine.c
Last active Apr 5, 2017

Embed
What would you like to do?
#include <stdio.h>
#include <assert.h>
#include <string.h>
// unfortunately there does not exist a magical computer with unbounded memory for an infinite tape
#define TAPE_SIZE 64
typedef struct {
char symbol; // input symbol
char write; // output symbol
char shift; // which way to move the head
char next; // output state
} state_t;
int main(void) {
static char tape[TAPE_SIZE];
static size_t head = TAPE_SIZE/2; // start in the middle of the tape so we can go in both directions
static unsigned int state = 0;
// 3-symbol (blank = -1, 0, 1) test binary incrementer
// from < https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/four.html >
static state_t states[][3] = { // each state has three possible input symbols defined
{
{-1, -1, 1, 1},
{0, 0, -1, 0},
{1, 1, -1, 0}
},
{
{-1, 1, -1, 2},
{0, 1, 1, 2},
{1, 0, 1, 1}
},
{
{-1, -1, 1, -1},
{0, 0, -1, 2},
{1, 1, -1, 2}
}
};
// set tape to blank symbol (-1)
memset(tape, -1, TAPE_SIZE);
// initialize for our test program
// note: binary is in reverse order
// in this case 0b101 (5)
tape[head+2] = 1;
tape[head+1] = 0;
tape[head+0] = 1;
// should write 0b110 (6) as output to the tape
for(;;) {
state_t *s = states[state];
// if we made the assumption that the set of symbols is unsigned and consecutive we could skip the
// linear lookup and just index into the state array for that symbol directly.
for(size_t i = 0; i < 3; i++) {
if(tape[head] == s[i].symbol) {
printf("(%d, '%d') -> (%d, '%d', %d)\n", state, tape[head], s[i].next, s[i].write, s[i].shift);
tape[head] = s[i].write;
head += s[i].shift;
state = s[i].next;
if(state == -1) // halting state
goto halt;
break;
}
assert(i != 2); // haven't found a new state, so error. just a safeguard for the impossible
}
}
halt:
printf("Tape:\n");
for(int i = 0; i < TAPE_SIZE; i++) {
printf("%02d: %d\n", i, tape[i]);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.