fork download
  1. // Turing machine implemented at type-level in C++11
  2. // http://www.reddit.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
stdin
Standard input is empty
stdout
.. 0 0 1 1 *1* 1 0 0 ..