Download code

Jump to: navigation, search

Back to Turing_machine_simulator_(C_Plus_Plus,_Template_metaprogramming)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

turing.cc

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Turing_machine_simulator_(C_Plus_Plus,_Template_metaprogramming)?oldid=11638
 14 */
 15 
 16 typedef int position;
 17 enum displacement { left = -1, none = 0, right = 1 };
 18 enum states { halt, A, B, C };
 19 typedef bool symbol;
 20 typedef unsigned int Time;
 21 Time const initial = 0;
 22 template<Time t, position pos> struct tape;
 23 template<Time t> struct head;
 24 template<Time t> struct state_machine;
 25 template<states t, symbol value> struct table;
 26 template<Time t, position pos> struct tape
 27 {
 28   static symbol const value =
 29         head<t-1>::pos == pos?
 30           table<state_machine<t-1>::state,
 31                 tape<t-1,pos>::value>::new_value
 32         : tape<t-1,pos>::value;
 33 };
 34 template<position pos> struct tape<initial, pos>
 35 {
 36   static symbol const value = 0;
 37 };
 38 template<Time t> struct head
 39 {
 40   // the position is the position of the last step plus
 41   // the displacement found in the state table for the
 42   // previous state/tape value
 43   static position const pos =
 44         head<t-1>::pos
 45         + table<state_machine<t-1>::state,
 46                 tape<t-1,head<t-1>::pos>::value>::move;
 47 };
 48 template<> struct head<initial>
 49 {
 50   static position const pos = 0;
 51 };
 52 template<Time t> struct state_machine
 53 {
 54   // the state is the new state for the previous
 55   // state/tape value in the state table
 56   static states const state =
 57     table<state_machine<t-1>::state,
 58           tape<t-1,head<t-1>::pos>::value>::new_state;
 59 };
 60 template<> struct state_machine<initial>
 61 {
 62   static states const state = A;
 63 };
 64 template<symbol value> struct table<halt, value>
 65 {
 66   static states const new_state = halt; // halt remains halt
 67   static symbol const new_value = value;   // the value doesn't change
 68   static displacement const move = none;   // we don't move any more
 69 };
 70 template<> struct table<A, 0>
 71 {
 72   static states const new_state = B;
 73   static symbol const new_value = 1;
 74   static displacement const move = right;
 75 };
 76 
 77 template<> struct table<A, 1>
 78 {
 79   static states const new_state = C;
 80   static symbol const new_value = 1;
 81   static displacement const move = left;
 82 };
 83 
 84 template<> struct table<B, 0>
 85 {
 86   static states const new_state = A;
 87   static symbol const new_value = 1;
 88   static displacement const move = left;
 89 };
 90 
 91 template<> struct table<B, 1>
 92 {
 93   static states const new_state = B;
 94   static symbol const new_value = 1;
 95   static displacement const move = right;
 96 };
 97 
 98 template<> struct table<C, 0>
 99 {
100   static states const new_state = B;
101   static symbol const new_value = 1;
102   static displacement const move = left;
103 };
104 
105 template<> struct table<C, 1>
106 {
107   static states const new_state = halt;
108   static symbol const new_value = 1;
109   static displacement const move = right;
110 };
111 #include <iostream>
112 #include <ostream>
113 #include <iomanip>
114 char const* statename[4] = { "(halt)", "A", "B", "C" };
115 template<symbol s, bool at_head> struct display_symbol;
116 template<> struct display_symbol<0, false> { static char const value = '*'; };
117 template<> struct display_symbol<1, false> { static char const value = '|'; };
118 template<> struct display_symbol<0, true> { static char const value = 'o'; };
119 template<> struct display_symbol<1, true> { static char const value = 'I'; };
120 template<Time t, position p> struct tape_symbol
121 {
122   static char const value = display_symbol<tape<t, p>::value,
123                                            head<t>::pos == p>::value;
124 };
125 template<Time t, position start, position end> struct print_tape
126 {
127   static void out(std::ostream& os)
128   {
129     os << tape_symbol<t, start>::value;
130     print_tape<t, start+1, end>::out(os);
131   }
132 };
133 
134 template<Time t, position end> struct print_tape<t, end, end>
135 {
136   static void out(std::ostream&)
137   {
138   }
139 };
140 template<Time tmin, Time tmax, position startpos, position endpos>
141  struct print_evolution
142 {
143   static void out(std::ostream& os)
144   {
145     os << std::setw(2) << tmin << ": ";
146     print_tape<tmin, startpos, endpos>::out(os);
147     os << " state: " << statename[state_machine<tmin>::state] << "\n";
148     print_evolution<tmin+1, tmax, startpos, endpos>::out(os);
149   }
150 };
151 
152 template<Time tmax, position startpos, position endpos>
153  struct print_evolution<tmax, tmax, startpos, endpos>
154 {
155   static void out(std::ostream&)
156   {
157   }
158 };
159 int main()
160 {
161   print_evolution<initial, 16, -5, 6>::out(std::cout);
162 }
163 


hijacker
hijacker
hijacker
hijacker