Simulate Turing machine

Question

I have written this code to simulate a Turing machine and wonder what could be improved. In particular, the --tape.end() seems a bit dodgy.

#include <array>
#include <iostream>
#include <list>


typedef enum {right, left} Direction;

template<int n>         // n is the number of symbols
struct State {
    std::array<int, n> write;       // Value to write, 0 <= write < n
    std::array<Direction, n> move;  // Direction to move tape
    std::array<State*, n> next;     // Next state, nullptr represents HALT
};

// Some test machines
std::array<State<2>, 5> A = {{
    {{1, 1}, {left, left},   {&A[1],   &A[0]}},
    {{1, 1}, {right, right}, {&A[2],   &A[1]}},
    {{1, 1}, {left, right},  {&A[0],   &A[3]}},
    {{1, 1}, {left, right},  {&A[0],   &A[4]}},
    {{1, 0}, {left, right},  {nullptr, &A[2]}},
}};

std::array<State<2>, 6> B = {{
    {{1, 1}, {left, left},   {&B[1], &B[0]}},
    {{1, 1}, {right, right}, {&B[2], &B[1]}},
    {{0, 1}, {right, right}, {&B[5], &B[3]}},
    {{1, 0}, {left, right},  {&B[0], &B[4]}},
    {{0, 1}, {left, right},  {&B[0], &B[2]}},
    {{1, 1}, {left, left},   {&B[4], nullptr}},
}};

std::array<State<3>, 3> C = {{
    {{1, 1, 2}, {right, left, left},  {&C[1], &C[1], &C[0]}},
    {{1, 1, 2}, {left, right, right}, {&C[0], &C[2], nullptr}},
    {{0, 2, 1}, {left, right, left},  {&C[0], &C[2], &C[2]}},
}};


int main() {
    std::list<int> tape = {0};
    std::list<int>::iterator head = tape.begin();
    State<2>* current_state = &A[0];
    int read;

    unsigned long long int step_count = 0;
    while (true) {
        step_count += 1;
        // Read tape
        read = *head;
        // Write to tape
        *head = current_state->write[read];
        // Move tape head
        if (current_state->move[read] == right) {
            if (head == --tape.end()) {
                tape.push_back(0);
            }
            head++;
        } else if (current_state->move[read] == left) {
            if (head == tape.begin()) {
                tape.push_front(0);
            }
            head--;
        }
        // Change state
        if (current_state->next[read] == nullptr) {
            break;
        } else {
            current_state = current_state->next[read];
        }
    }
    std::cout << "Halted after " << step_count << " steps." << std::endl;
    unsigned int sum = 0;
    for (int it : tape) {
        sum += (it != 0);
    }
    std::cout << "Total non-zeroes: " << sum << std::endl;
    return 0;
}

Answer 1

I believe you're looking for std::prev:

std::prev(tape.end());

The linked page even states the exact comparison of the two:

Although the expression --c.end() often compiles, it is not guaranteed to do so: c.end() is an rvalue expression, and there is no iterator requirement that specifies that decrement of an rvalue is guaranteed to work. In particular, when iterators are implemented as pointers, --c.end() does not compile, while std::prev(c.end()) does.

I do have some additional points as well:

1. typedef isn't needed for enums in C++.

2. Since tape is a storage container of a primitive type (ints), the default constructor will zero-initialize it automatically. As such, you don't need to assign to {0}.

   std::list<int> tape;
   

   In case you want to verify it right away, take a look at this test.

3. It may be more useful to use auto with head:

   auto head = tape.begin();
   

   This allows for less typing and for any iterator type (if it ever changes).

4. You could put these "test machines" in a separate file or somewhere separate from the main implementation. Proper unit testing may be preferred, but I don't have much to say about that. I'd also rename them as such as it's best not to use single-variable names outside of loop counters.

   Another note: you can omit the = for each std::array for C++11 list initialization.

5. main() seems to be handling too much of the logic. Have other functions handle it and only have main() initialize variables, call these functions, then output the results.

6. return 0 or similar isn't needed at the very end of main(); it'll always do the same return at this point.