fork download 
  1. // Turing machine implemented at type-level in C++11
  2. // http://w...content-available-to-author-only...t.com/r/cpp/comments/xea4y/typelevel_turing_machine/
  3.  
  4. // Output:
  5. // .. 0 0 1 1 *1* 1 0 0 ..
  6.  
  7. #include <stdio.h>
  8. #include <vector>
  9.  
  10. using namespace std;
  11.  
  12. enum class Direction { L, R };
  13.  
  14. template<int Value>
  15. struct repeat {
  16.     static const int head = Value;
  17.     typedef repeat<Value> tail;
  18. };
  19.  
  20. template<int Head, typename Tail>
  21. struct cons {
  22.     static const int head = Head;
  23.     typedef Tail tail;
  24. };
  25.  
  26. template<Direction, typename Left, typename Right>
  27. struct step {};
  28.  
  29. template<typename Left, typename Right>
  30. struct step<Direction::L, Left, Right> {
  31.     typedef typename Left::tail left;
  32.     typedef cons<Left::head, Right> right;
  33. };
  34.  
  35. template<typename Left, typename Right>
  36. struct step<Direction::R, Left, Right> {
  37.     typedef cons<Right::head, Left> left;
  38.     typedef typename Right::tail right;
  39. };
  40.  
  41. template<typename TuringMachine, typename Left, typename Right,
  42.          typename State = typename TuringMachine::initial_state>
  43. struct turing_machine {
  44.     typedef typename TuringMachine::template transition_table<Right::head, State> transition;
  45.     typedef step<transition::direction, Left, cons<transition::symbol, typename Right::tail>> after;
  46.  
  47.     typedef turing_machine<TuringMachine, typename after::left,
  48.                            typename after::right, typename transition::state> next;
  49.  
  50.     typedef typename next::final_left final_left;
  51.     typedef typename next::final_right final_right;
  52. };
  53.  
  54. template<typename TuringMachine, typename Left, typename Right>
  55. struct turing_machine<TuringMachine, Left, Right, typename TuringMachine::final_state> {
  56.     typedef Left final_left;
  57.     typedef Right final_right;
  58. };
  59.  
  60. struct busy_beaver {
  61.     struct A {};
  62.     struct B {};
  63.     struct H {};
  64.  
  65.     template<int Sym, typename State>
  66.     struct transition_table {};
  67.  
  68.     typedef A initial_state;
  69.     typedef H final_state;
  70. };
  71.  
  72. template<>
  73. struct busy_beaver::transition_table<0, busy_beaver::A> {
  74.     static const int symbol = 1;
  75.     static const Direction direction = Direction::R;
  76.     typedef B state;
  77. };
  78.  
  79. template<>
  80. struct busy_beaver::transition_table<0, busy_beaver::B> {
  81.     static const int symbol = 1;
  82.     static const Direction direction = Direction::L;
  83.     typedef A state;
  84. };
  85.  
  86. template<>
  87. struct busy_beaver::transition_table<1, busy_beaver::A> {
  88.     static const int symbol = 1;
  89.     static const Direction direction = Direction::L;
  90.     typedef B state;
  91. };
  92.  
  93. template<>
  94. struct busy_beaver::transition_table<1, busy_beaver::B> {
  95.     static const int symbol = 1;
  96.     static const Direction direction = Direction::R;
  97.     typedef H state;
  98. };
  99.  
  100. template<typename T>
  101. struct type_list_to_vector {
  102.     void operator()(std::vector<int> &output);
  103. };
  104.  
  105. template<int Head, typename Tail>
  106. struct type_list_to_vector<cons<Head, Tail>> {
  107.     void operator()(std::vector<int> &output)
  108.     {
  109.         output.push_back(Head);
  110.         type_list_to_vector<Tail>()(output);
  111.     }
  112. };
  113.  
  114. template<int Value>
  115. struct type_list_to_vector<repeat<Value>> {
  116.     void operator()(std::vector<int> &output) {
  117.         output.push_back(Value);
  118.     }
  119. };
  120.  
  121. int main() {
  122.     typedef turing_machine<busy_beaver, repeat<0>, repeat<0>> tm;
  123.  
  124.     vector<int> tape;
  125.     type_list_to_vector<tm::final_left>()(tape);
  126.  
  127.     printf(".. %d ", tape.back());
  128.     for (auto it = tape.crbegin(); it != tape.crend(); ++it)
  129.         printf("%d ", *it);
  130.  
  131.     tape.clear();
  132.     type_list_to_vector<tm::final_right>()(tape);
  133.     printf("*%d* ", tape.front());
  134.     for (auto it = tape.cbegin() + 1; it != tape.cend(); ++it)
  135.         printf("%d ", *it);
  136.     printf("%d ..\n", tape.back());
  137. }
Success #stdin #stdout 0s 3016KB
comments (?)
stdin 
Standard input is empty
stdout 
.. 0 0 1 1 *1* 1 0 0 ..
https://ideone.com/Vzkt8
language:
C++14 (gcc 8.3)
created:
13 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!