turing_machine.cpp 6.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227
  1. #include <iostream>
  2. #include <array>
  3. #include <algorithm>
  4. #include <initializer_list>
  5. #include <cstdlib>
  6. #include <string.h>
  7. // #define NDEBUG
  8. #include <cassert>
  9. #ifdef ARDUINO
  10. void __assert(const char *__func, const char *__file, int __lineno, const char *__sexp) {
  11. // abort program execution.
  12. abort();
  13. }
  14. #endif
  15. constexpr short max_tape_len = 1024;
  16. struct tape_t {
  17. short head = 0;
  18. char tape_stg[max_tape_len];
  19. tape_t(short init_pos, const char *init, char blank = '.') {
  20. reset_tape(init_pos, init, blank);
  21. }
  22. void reset_tape(short init_pos, const char *init, char blank = '.') {
  23. head = init_pos;
  24. int i = 0;
  25. while(*init != '\0')
  26. tape_stg[i++] = *init++;
  27. std::fill(std::begin(tape_stg) + i, std::end(tape_stg), blank);
  28. }
  29. void shift_head_right(short s = 1) {
  30. head += s;
  31. assert(head < max_tape_len);
  32. }
  33. void shift_head_left(short s = 1) {
  34. head -= s;
  35. assert(head >= 0);
  36. }
  37. bool in_bounds(short pos) {
  38. return pos >= 0 && pos < max_tape_len;
  39. }
  40. char read() {
  41. return tape_stg[head];
  42. }
  43. void write(char symbol) {
  44. tape_stg[head] = symbol;
  45. }
  46. };
  47. enum class action_t : char {
  48. fail,
  49. left,
  50. right,
  51. succeed,
  52. stay,
  53. };
  54. struct rule {
  55. short state_in;
  56. char symbol_in;
  57. short state_out;
  58. char symbol_out;
  59. action_t action;
  60. };
  61. template<size_t N_FINALS, size_t N_RULES>
  62. struct turing_machine {
  63. short state = 0;
  64. const short final_states[N_FINALS];
  65. const rule rules[N_RULES];
  66. tape_t tape;
  67. char blank = '.';
  68. char wildcard = '*';
  69. short ticks = 0;
  70. // Disable copying the tm as well as moving it
  71. turing_machine(turing_machine&) = delete;
  72. turing_machine(turing_machine&&) = delete;
  73. void succeed() {
  74. std::cout << "Success\n";
  75. std::exit(0);
  76. }
  77. void fail() {
  78. std::cout << "Failed\n";
  79. std::exit(1);
  80. }
  81. bool is_final(short st) {
  82. return std::find(std::begin(final_states), std::end(final_states), st)
  83. != std::end(final_states);
  84. }
  85. bool step_forward(int steps = 1) {
  86. for(int i = 0; i < steps; ++i){
  87. char symbol = tape.read();
  88. short state = this->state; char wildcard = this->wildcard;
  89. char next_symbol; short next_state; action_t action;
  90. // std::cout << i << ": [" << tape.head << "] = \'" << symbol << "\'; s = " << state << "\n";
  91. // Find a rule matching the current state and either the current symbol
  92. // or the wildcard
  93. if(std::find_if(std::begin(rules), std::end(rules),
  94. // Capture these variables, so they can be accessed
  95. // inside the lambda
  96. [&next_state, &next_symbol, &action,
  97. symbol, state, wildcard](rule r) {
  98. // std::cout << "(" << state << ", \'" << symbol << "\') <=> "
  99. // << "(" << r.state_in << ", \'" << r.symbol_in << "\') \n";
  100. if(r.state_in == state &&
  101. (r.symbol_in == symbol || r.symbol_in == wildcard)) {
  102. // std::cout << (int) r.symbol_out << "\n";
  103. next_state = r.state_out;
  104. next_symbol = r.symbol_out;
  105. action = r.action;
  106. return true;
  107. }
  108. return false;
  109. }) != std::end(rules)) {
  110. if(next_symbol != wildcard)
  111. tape.write(next_symbol);
  112. ++ticks;
  113. this->state = next_state;
  114. if(is_final(this->state)){
  115. succeed();
  116. }
  117. switch(action) {
  118. case action_t::fail:
  119. fail();
  120. break;
  121. case action_t::left:
  122. tape.shift_head_left();
  123. break;
  124. case action_t::right:
  125. tape.shift_head_right();
  126. break;
  127. case action_t::succeed:
  128. succeed();
  129. break;
  130. case action_t::stay:
  131. break; // Do nothing
  132. }
  133. } else {
  134. fail();
  135. }
  136. // Reading an empty cell on the tape means we have failed
  137. // Doing this after the rest, in case a transition wasn't found
  138. // This should happen before, but, for compatibility with the reference,
  139. // it must be done afterwards, as it includes rules matching `blank`
  140. // // Therefore, TODO, move up
  141. // if(symbol == blank)
  142. // fail();
  143. }
  144. return true;
  145. }
  146. };
  147. template<typename T, size_t N1, size_t N2>
  148. turing_machine(short, const T (&)[N1], const rule (&)[N2], tape_t) -> turing_machine<N1, N2>;
  149. int main() {
  150. turing_machine tm{0, {100},
  151. // st, char, next_st, n_char, act
  152. {{0, '.', 100, '.', action_t::right},
  153. {0, '0', 1, '#', action_t::right},
  154. {1, '0', 1, '0', action_t::right},
  155. {1, '.', 2, '0', action_t::left},
  156. {2, '0', 2, '0', action_t::left},
  157. {2, '#', 3, '#', action_t::right},
  158. {3, '0', 4, 'A', action_t::right},
  159. {4, '.', 100, '.', action_t::left},
  160. {4, '0', 5, 'C', action_t::right},
  161. {5, '0', 6, 'C', action_t::right},
  162. {6, '0', 7, 'C', action_t::right},
  163. {7, '.', 100, '.', action_t::left},
  164. {7, 'a', 7, 'a', action_t::right},
  165. {7, 'A', 7, 'A', action_t::right},
  166. {7, 'C', 7, 'C', action_t::right},
  167. {7, '0', 9, '0', action_t::left},
  168. {9, 'C', 9, 'C', action_t::left},
  169. {9, 'A', 9, 'A', action_t::left},
  170. {9, 'a', 9, 'A', action_t::left},
  171. {9, '#', 10, '#', action_t::right},
  172. {10, 'A', 10, 'A', action_t::right},
  173. {10, 'C', 11, 'a', action_t::right},
  174. {11, 'a', 11, 'a', action_t::right},
  175. {11, 'C', 11, 'C', action_t::right},
  176. {11, '0', 8, 'C', action_t::right},
  177. {8, '0', 12, 'C', action_t::left},
  178. {12, 'C', 12, 'C', action_t::left},
  179. {12, 'a', 12, 'a', action_t::left},
  180. {12, 'A', 11, 'a', action_t::right},
  181. {12, '#', 13, '#', action_t::right},
  182. {13, 'a', 13, 'a', action_t::right},
  183. {13, 'C', 13, 'C', action_t::right},
  184. {13, '0', 14, 'C', action_t::right},
  185. {14, '.', 100, '.', action_t::left},
  186. {14, '0', 9, '0', action_t::left}
  187. // {100,'*', 100, '*', action_t::succeed}
  188. },
  189. {0, "0"}};
  190. tm.step_forward(1000);
  191. }