turingmachine.c

#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]);
    }
}