TuringMachine.cpp

#include <fstream>
#include <fstream>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

#define LEFT false
#define RIGHT true
#define HALT -1

// Each instance of the class below is a state.
class State {
    public:
        // Attributes of a state, initialized to default values
        bool write_after_0 = false;
        bool write_after_1 = false;
        bool direction_after_0 = LEFT;
        bool direction_after_1 = LEFT;
        size_t next_state_after_0 = HALT;
        size_t next_state_after_1 = HALT;

        // Dummy constructor
        State() {}
    
        // Creates a new state.
        State(bool write_0, bool direction_0, size_t state_0,
              bool write_1, bool direction_1, size_t state_1) {
            write_after_0 = write_0;
            write_after_1 = write_1;
            direction_after_0 = direction_0;
            direction_after_1 = direction_1;
            next_state_after_0 = state_0;
            next_state_after_1 = state_1;
        }

        // Prints the state based on its attributes.
        void printState() {
            if (write_after_0)
                cout << "1";
            else
                cout << "0";
            if (direction_after_0)
                cout << "R";
            else
                cout << "L";
            cout << next_state_after_0 << " ";
            
            if (write_after_1)
                cout << "1";
            else
                cout << "0";
            if (direction_after_1)
                cout << "R";
            else
                cout << "L";
            cout << next_state_after_1 << endl;
        }
        
        // Performs operations on a piece of tape, according to
        // the bit read and the rules of the state.
        int run(bool* tape, size_t* index) {
            if (tape[*index]) {
                if (write_after_1)
                    tape[*index] = 1;
                else
                    tape[*index] = 0;
                if (direction_after_1)
                    *index += 1;
                else
                    *index -= 1;
                return next_state_after_1;
            }
            if (write_after_0)
                tape[*index] = 1;
            else
                tape[*index] = 0;
            if (direction_after_0)
                *index += 1;
            else
                *index -= 1;
            return next_state_after_0;
        }
};

// Runs the Turing machine program based on the states.
// Once the program halts or goes on for too long, the 60 bits
// around the center of the tape are output to the screen.
int process(State* state_set, bool* tape, size_t* index) {

    size_t next_state = 0;
    int number_of_ops = 0;
    while (next_state != -1 && number_of_ops < 100000000 &&
           *index >= 0 && *index < 1048576) {
        next_state = state_set[next_state].run(tape, index);
        number_of_ops++;
    }
    
    cout << "Tape (60 bits about center):\n";
    
    for (size_t i = 0; i < 60; i++) {
        if (tape[524288+i-9]) {
            cout << "1";
        } else {
            cout << "0";
        }
    }
    cout << '\n';
    
    return 0;
}

// Reads in values stored on the tape from tape.txt.
void read_tape(bool* tape, size_t* index) {
    string tape_string;
    ifstream file ("tape.txt");
    getline(file, tape_string);
    file.close();
    
    for (size_t i = 0; i < tape_string.length(); i++) {
        if (tape_string[i] == '1')
            tape[i + *index] = true;
    }
}

// Counts the number of states used.
int count_num_states(string state_string) {    
    size_t num_states = 1;
    for (size_t i = 0; i < state_string.length(); i++) {
        if (state_string[i] == ',')
            num_states++;
    }
    
    return num_states;
}

// Reads in array of states from states_string.
void read_states(State* state_set, string state_string) {
    size_t i = 0;
    size_t index = 0;

    while (i < state_string.length()) {
        if (state_string[i] == '1')
            state_set[index].write_after_0 = true;
        else
            state_set[index].write_after_0 = false;
        i += 2;
        if (state_string[i] == '1')
            state_set[index].direction_after_0 = true;
        else
            state_set[index].direction_after_0 = false;
        i += 2;
        
        size_t j = 0;
        while (i+j < state_string.length() && state_string[i+j] != ' ')
            j++;
        state_set[index].next_state_after_0 = (size_t) stoi(state_string.substr(i, j));
        i += j + 1;
        
        if (state_string[i] == '1')
            state_set[index].write_after_1 = true;
        else
            state_set[index].write_after_1 = false;
        i += 2;
        if (state_string[i] == '1')
            state_set[index].direction_after_1 = true;
        else
            state_set[index].direction_after_1 = false;
        i += 2;
        
        j = 0;
        while (i+j < state_string.length() && state_string[i+j] != ',')
            j++;
        state_set[index].next_state_after_1 = (size_t) stoi(state_string.substr(i, j));
        i += j + 1;
        
        index++;
    }
}

// Calls functions to set up and then run the Turing machine.
int main() {
    // Sets up cells along the tape.
    bool tape[1048576] = { false }; // 1 MB
    size_t* index;
    size_t start = 524288;
    index = &start;

    // Reads the text from states.txt into state_string.
    string state_string;
    ifstream file ("states.txt");
    getline(file, state_string);
    file.close();

    // Sets up state_set, in which all states are stored.
    State* state_set = new State[count_num_states(state_string)];

    // Calls functions to store states and the tape in arrays.
    read_states(state_set, state_string);
    read_tape(tape, index);

    // Runs the Turing machine.
    return process(state_set, tape, index);
}