turing/turing.cpp

#include <vector>

#pragma once

namespace Turing {

// Available movements on the turing machine
enum Movement {
    left = false,
    right = true,
};

// Turing instruction
template <typename S, typename V>
struct Instruction {
    S currentState;
    V currentValue;
    S nextState;
    V nextValue;
    Movement tapeMovement;

    constexpr Instruction(const S cS, const V cV, const S nS, const V nV, Movement tM) {
        this->currentState = cS;
        this->currentValue = cV;
        this->nextState = nS;
        this->nextValue = nV;
        this->tapeMovement = tM;
    }

    Instruction() = default;
};

// Configuration of the Turing machine
template <typename S, typename V>
struct Definition {
    S defaultState;
    V defaultValue;
    std::vector<Instruction<S, V>> instructions;
};

// The Turing Machine
template <typename S, typename V>
class Machine
{

const Definition<S, V>* definition;

int position = 0; // current position
S state; // current state
std::vector<V> memory; // aka tape
int memoryStart = 0; // the position of the beginning of the saved memory

V& value() {
    this->ensure(position);
    return this->memory[position - memoryStart];
}

public:

unsigned int runCount = 0;

S getState() { return this->state; }

int getPosition() {return this->position; }

auto getMemory() { return std::vector<V>(this->memory); }

// returns position of the behind last saved element in the saved memory
int getMemoryEnd() { return this->memoryStart + this->memory.size(); }

int getMemoryStart() { return this->memoryStart; }

Machine(const Definition<S, V>* definition) {
    this->definition = definition;
    this->state = definition->defaultState;
}

/**
 * @brief Ensures that provided position is saved in memory and avaliable.
 * 
 * @param pos the position
 * @return true if changes were made, false otherwise
 */
bool ensure(const int pos) {
    if (pos >= this->memoryStart && pos < this->getMemoryEnd()) return false;

    // if ensuring pos is after memory ending
    if (pos >= this->getMemoryEnd()) {
        this->memory.insert(
            this->memory.end(),
            this->getMemoryEnd() - pos + 1,
            this->definition->defaultValue
        );
    }

    // if ensuring pos is before memory ending
    if (pos < this->memoryStart) {
        this->memory.insert(
            this->memory.begin(),
            this->memoryStart - pos,
            this->definition->defaultValue
        );
        this->memoryStart = pos;
    }

    return true;
}

/**
 * @brief Ensures that current position is saved in memory and available
 * 
 * @return true if changes were made, false otherwise
 */
bool ensure() { return this->ensure(this->position); }

/**
 * @brief sets the value at given position
 */
void set(const V& value, int pos) {
    this->ensure(pos);
    this->memory[pos - this->memoryStart] = value;
}

/**
 * @brief Gets state from the memory
 * 
 * @param pos from which position get the value from
 */
V& at(int pos) {
    this->ensure(pos);
    return this->memory[pos - this->memoryStart];
}

/**
 * @brief Set the saved memory by copying values from the provided vector
 * 
 * @param newTape vector of new memory values
 * @param position the position of the head after loading the memory, default 0 (the beginning)
 */
void setTape(const std::vector<V>& newTape, int position = 0) {
    this->memoryStart = 0;
    this->memory = newTape;
    this->position = position;
}

/**
 * @brief do tick() for n times
 * 
 * @return the ammount of remaining ticks after halting
 */
unsigned int tickFor(const unsigned int times) {
    unsigned int i = times;
    while (i > 0 && this->tick()) i--;
    return i;
}

/**
 * @brief evaluate what happens in the machine after one tick and check if the machine is halted
 * 
 * @return false if halted, true if work has been done
 */
bool tick() {
    V& value = this->value();
    Turing::Instruction<S, V>* thatInstruction = nullptr;
    for(auto i : this->definition->instructions) {
        if (value == i.currentValue & this->state == i.currentState) {
            thatInstruction = &i;
            break;
        }
    }

    if (thatInstruction == nullptr) return false;

    this->set(thatInstruction->nextValue, this->position);
    this->state = thatInstruction->nextState;

    thatInstruction->tapeMovement == Movement::right ? this->position++ : this->position--;
    this->runCount++;

    return true;
}

}; // class Machine

} // namespace Turing