Badass_Turing_Machine_Simulator/turing_machine.cpp

#include <iostream>
#include <array>
#include <algorithm>
#include <initializer_list>

#include <cstdlib>
#include <string.h>

// #define NDEBUG
#include <cassert>

#ifdef ARDUINO
void __assert(const char *__func, const char *__file, int __lineno, const char *__sexp) {
	// abort program execution.
	abort();
}
#endif

constexpr short max_tape_len = 1024;

struct tape_t {
	short head = 0;
	char tape_stg[max_tape_len];

	tape_t(short init_pos, const char *init, char blank = '.') {
		reset_tape(init_pos, init, blank);
	}

	void reset_tape(short init_pos, const char *init, char blank = '.') {
		head = init_pos;
		int i = 0;
		while(*init != '\0')
			tape_stg[i++] = *init++;
		std::fill(std::begin(tape_stg) + i, std::end(tape_stg), blank);
	}

	void shift_head_right(short s = 1) {
		head += s;
		assert(head < max_tape_len);
	}

	void shift_head_left(short s = 1) {
		head -= s;
		assert(head >= 0);
	}

	bool in_bounds(short pos) {
		return pos >= 0 && pos < max_tape_len;
	}

	char read() {
		return tape_stg[head];
	}

	void write(char symbol) {
		tape_stg[head] = symbol;
	}

};

enum class action_t : char {
	fail,
	left,
	right,
	succeed,
	stay,
};

struct rule {
	short  state_in;
	char  symbol_in;
	short state_out;
	char symbol_out;
	action_t action;
};

template<size_t N_FINALS, size_t N_RULES>
struct turing_machine {
	short state = 0;
	const short final_states[N_FINALS];
	const rule rules[N_RULES];
	tape_t tape;
	char blank = '.';
	char wildcard = '*';
	short ticks = 0;

	// Disable copying the tm as well as moving it
	turing_machine(turing_machine&) = delete;
	turing_machine(turing_machine&&) = delete;

	void succeed() {
		std::cout << "Success\n";
		std::exit(0);
	}
	void fail() {
		std::cout << "Failed\n";
		std::exit(1);
	}

	bool is_final(short st) {
		return std::find(std::begin(final_states), std::end(final_states), st)
			!= std::end(final_states);
	}

	bool step_forward(int steps = 1) {
		for(int i = 0; i < steps; ++i){
			char symbol = tape.read();
			short state = this->state; char wildcard = this->wildcard;
			char next_symbol; short next_state; action_t action;

			// std::cout << i << ": [" << tape.head << "] = \'" << symbol <<  "\'; s = " << state << "\n";

			// Find a rule matching the current state and either the current symbol
			// or the wildcard
			if(std::find_if(std::begin(rules), std::end(rules),
			                // Capture these variables, so they can be accessed
			                // inside the lambda
			                [&next_state, &next_symbol, &action,
			                 symbol, state, wildcard](rule r) {
				                // std::cout << "(" << state << ", \'" << symbol << "\') <=> "
				                //           << "(" << r.state_in << ", \'" << r.symbol_in << "\') \n";
				                if(r.state_in == state &&
				                   (r.symbol_in == symbol || r.symbol_in == wildcard)) {
					                // std::cout << (int) r.symbol_out << "\n";
					                next_state = r.state_out;
					                next_symbol = r.symbol_out;
					                action = r.action;
					                return true;
				                }
				                return false;
			                }) != std::end(rules)) {

				if(next_symbol != wildcard)
					tape.write(next_symbol);

				++ticks;
				this->state = next_state;

				if(is_final(this->state)){
					succeed();
				}

				switch(action) {
				case action_t::fail:
					fail();
					break;
				case action_t::left:
					tape.shift_head_left();
					break;
				case action_t::right:
					tape.shift_head_right();
					break;
				case action_t::succeed:
					succeed();
					break;
				case action_t::stay:
					break; // Do nothing
				}
			} else {
				fail();
			}

			// Reading an empty cell on the tape means we have failed
			// Doing this after the rest, in case a transition wasn't found
			// This should happen before, but, for compatibility with the reference,
			// it must be done afterwards, as it includes rules matching `blank`
			// // Therefore, TODO, move up
			// if(symbol == blank)
			// 	fail();
		}


		return true;
	}

};

template<typename T, size_t N1, size_t N2>
turing_machine(short, const T (&)[N1], const rule (&)[N2], tape_t) -> turing_machine<N1, N2>;

int main() {

	turing_machine tm{0, {100},
	                  // st, char,  next_st, n_char, act
	                  {{0,	'.',	100,	'.',	action_t::right},
	                   {0,	'0',	1,	'#',	action_t::right},
	                   {1,	'0',	1,	'0',	action_t::right},
	                   {1,	'.',	2,	'0',	action_t::left},
	                   {2,	'0',	2,	'0',	action_t::left},
	                   {2,	'#',	3,	'#',	action_t::right},
	                   {3,	'0',	4,	'A',	action_t::right},
	                   {4,	'.',	100,	'.',	action_t::left},
	                   {4,	'0',	5,	'C',	action_t::right},
	                   {5,	'0',	6,	'C',	action_t::right},
	                   {6,	'0',	7,	'C',	action_t::right},
	                   {7,	'.',	100,	'.',	action_t::left},
	                   {7,	'a',	7,	'a',	action_t::right},
	                   {7,	'A',	7,	'A',	action_t::right},
	                   {7,	'C',	7,	'C',	action_t::right},
	                   {7,	'0',	9,	'0',	action_t::left},
	                   {9,	'C',	9,	'C',	action_t::left},
	                   {9,	'A',	9,	'A',	action_t::left},
	                   {9,	'a',	9,	'A',	action_t::left},
	                   {9,	'#',	10,	'#',	action_t::right},
	                   {10,	'A',	10,	'A',	action_t::right},
	                   {10,	'C',	11,	'a',	action_t::right},
	                   {11,	'a',	11,	'a',	action_t::right},
	                   {11,	'C',	11,	'C',	action_t::right},
	                   {11,	'0',	8,	'C',	action_t::right},
	                   {8,	'0',	12,	'C',	action_t::left},
	                   {12,	'C',	12,	'C',	action_t::left},
	                   {12,	'a',	12,	'a',	action_t::left},
	                   {12,	'A',	11,	'a',	action_t::right},
	                   {12,	'#',	13,	'#',	action_t::right},
	                   {13,	'a',	13,	'a',	action_t::right},
	                   {13,	'C',	13,	'C',	action_t::right},
	                   {13,	'0',	14,	'C',	action_t::right},
	                   {14,	'.',	100,	'.',	action_t::left},
	                   {14,	'0',	9,	'0',	action_t::left}
	                   // {100,'*',	100,	'*',	action_t::succeed}
	                  },
	                  {0, "0"}};

	tm.step_forward(1000);

}