turing-machine.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MOVE_NONE 0
#define MOVE_LEFT 1
#define MOVE_RIGHT 2

typedef struct Rule {
    int state;
    char read_val;
    int new_state;
    char write_val;
    int move_dir;
} Rule;

char tape[32] = {'0', '0', '0', '1', '0', '1', '1'};
char *head;

int current_state;

Rule rules[32];
int rules_count = 0;

int accept_states[32];
int accept_states_count = 0;

bool is_accept_state(int state) {
    for (int i = 0; i < accept_states_count; i++) {
        if (state == accept_states[i]) {
            return true;
        }
    }

    return false;
}

int main(int argc, char **argv) {
    Rule rule0 = {1, '0', 2, '1', MOVE_RIGHT};
    rules[rules_count++] = rule0;
    Rule rule1 = {1, 0, 2, '1', MOVE_RIGHT};
    rules[rules_count++] = rule1;
    Rule rule2 = {1, '1', 1, '0', MOVE_LEFT};
    rules[rules_count++] = rule2;
    Rule rule3 = {2, '0', 2, '0', MOVE_RIGHT};
    rules[rules_count++] = rule3;
    Rule rule4 = {2, '1', 2, '1', MOVE_RIGHT};
    rules[rules_count++] = rule4;
    Rule rule5 = {2, 0, 3, 0, MOVE_LEFT};
    rules[rules_count++] = rule5;

    accept_states[accept_states_count++] = 3;

    head = &tape[6];
    current_state = 1;

    while (!is_accept_state(current_state)) {
        Rule *current_rule = NULL;
        for (int i = 0; i < rules_count; i++) {
            if (current_state == rules[i].state && *head == rules[i].read_val) {
                current_rule = &rules[i];
                break;
            }
        }

        if (!current_rule) {
            fprintf(stderr, "Did not match rule\n");
            exit(1);
        }

        printf("writing %c\n", current_rule->write_val);
        *head = current_rule->write_val;

        switch (current_rule->move_dir) {
            case MOVE_LEFT:
                printf("moving left\n");
                head--;
                break;
            case MOVE_RIGHT:
                printf("moving right\n");
                head++;
                break;
            case MOVE_NONE:
                // noop
                break;
        }

        printf("new state %i\n", current_rule->new_state);
        current_state = current_rule->new_state;
    }

    printf("done\n");
    printf("state: %i\n", current_state);

    printf("tape: ");
    for (int i = 0; i < 32; i++) {
        printf("%c", tape[i]);
    }
    printf("\n");

    return 0;
}