// Turing machine implemented at type-level in C++11
// http://w...content-available-to-author-only...t.com/r/cpp/comments/xea4y/typelevel_turing_machine/
// Output:
// .. 0 0 1 1 *1* 1 0 0 ..
#include <stdio.h>
#include <vector>
using namespace std;
enum class Direction { L, R };
template<int Value>
struct repeat {
static const int head = Value;
typedef repeat<Value> tail;
};
template<int Head, typename Tail>
struct cons {
static const int head = Head;
typedef Tail tail;
};
template<Direction, typename Left, typename Right>
struct step {};
template<typename Left, typename Right>
struct step<Direction::L, Left, Right> {
typedef typename Left::tail left;
typedef cons<Left::head, Right> right;
};
template<typename Left, typename Right>
struct step<Direction::R, Left, Right> {
typedef cons<Right::head, Left> left;
typedef typename Right::tail right;
};
template<typename TuringMachine, typename Left, typename Right,
typename State = typename TuringMachine::initial_state>
struct turing_machine {
typedef typename TuringMachine::template transition_table<Right::head, State> transition;
typedef step<transition::direction, Left, cons<transition::symbol, typename Right::tail>> after;
typedef turing_machine<TuringMachine, typename after::left,
typename after::right, typename transition::state> next;
typedef typename next::final_left final_left;
typedef typename next::final_right final_right;
};
template<typename TuringMachine, typename Left, typename Right>
struct turing_machine<TuringMachine, Left, Right, typename TuringMachine::final_state> {
typedef Left final_left;
typedef Right final_right;
};
struct busy_beaver {
struct A {};
struct B {};
struct H {};
template<int Sym, typename State>
struct transition_table {};
typedef A initial_state;
typedef H final_state;
};
template<>
struct busy_beaver::transition_table<0, busy_beaver::A> {
static const int symbol = 1;
static const Direction direction = Direction::R;
typedef B state;
};
template<>
struct busy_beaver::transition_table<0, busy_beaver::B> {
static const int symbol = 1;
static const Direction direction = Direction::L;
typedef A state;
};
template<>
struct busy_beaver::transition_table<1, busy_beaver::A> {
static const int symbol = 1;
static const Direction direction = Direction::L;
typedef B state;
};
template<>
struct busy_beaver::transition_table<1, busy_beaver::B> {
static const int symbol = 1;
static const Direction direction = Direction::R;
typedef H state;
};
template<typename T>
struct type_list_to_vector {
void operator()(std::vector<int> &output);
};
template<int Head, typename Tail>
struct type_list_to_vector<cons<Head, Tail>> {
void operator()(std::vector<int> &output)
{
output.push_back(Head);
type_list_to_vector<Tail>()(output);
}
};
template<int Value>
struct type_list_to_vector<repeat<Value>> {
void operator()(std::vector<int> &output) {
output.push_back(Value);
}
};
int main() {
typedef turing_machine<busy_beaver, repeat<0>, repeat<0>> tm;
vector<int> tape;
type_list_to_vector<tm::final_left>()(tape);
printf(".. %d ", tape.back());
for (auto it = tape.crbegin(); it != tape.crend(); ++it)
printf("%d ", *it);
tape.clear();
type_list_to_vector<tm::final_right>()(tape);
printf("*%d* ", tape.front());
for (auto it = tape.cbegin() + 1; it != tape.cend(); ++it)
printf("%d ", *it);
printf("%d ..\n", tape.back());
}