Turing machine for PSE #110567

turing.cpp

#include <deque>
#include <cstdio>
#include <numeric>

using namespace std;

const int L = -1;
const int R = 1;

int rules[6][2][3] = {{{1,L,1},{1,L,0}},
                      {{1,R,2},{1,R,1}},
                      {{0,R,5},{1,R,3}},
                      {{1,L,0},{0,R,4}},
                      {{0,L,0},{1,R,2}},
                      {{1,L,4},{-1,-1,-1}}};

void print_tape(deque<int> tape, int i, int state) {
    for (int j = 0; j < tape.size(); j++) {
        if (i == j) {
            printf("%d", state);
        } else {
            printf(" ");
        }
    }
    printf("\n");
    for (int n: tape) {
        printf("%d", n);
    }
    printf("\n");
}

int main() {
    deque<int> tape = {0};
    int i = 0; // head position
    int state = 0;
    unsigned long long steps = 0;
    while (1) {
        // print_tape(tape, i, state);
        int* result = rules[state][tape[i]];
        if ((tape[i] = *result) < 0) {
            break;
        }
        state = *(result + 2);
        i += *(result + 1);
        if (i < 0) {
            tape.push_front(0);
            i = 0;
            printf("< %ld\n", tape.size());
        } else if (i == tape.size()) {
            tape.push_back(0);
            // printf("> %ld\n", tape.size());
        }
        ++steps;
    }
    printf("%lld steps\n", steps);
    printf("%ld bits memory\n", tape.size());
    printf("%d ones\n", accumulate(tape.begin(), tape.end(), 0));
}