Turing machine simulator (C Plus Plus, Template metaprogramming)
From LiteratePrograms
- Other implementations: C | C++ | C++ | Haskell | Java | LaTeX | OCaml | Ruby | Scheme | Sed | Unlambda
C++ has a quite powerful template feature. Indeed, the templates provide a turing-complete sublanguage in C++. The most direct way of showing that turing-completeness is, of course, to write a turing machine simulator in it.
Now templates are a compile-time feature, and turing machines are defined by a process. However that problem is simple to solve: By making the time an input variable, the time-dependent problem of emulating is essentially reduced to the time-independent problem of determining the state of the machine at a given time t.
The following code implements a turing machine with two symbols. The turing machine is running a three-state busy beaver, as described in [1]. The turing machine itself is completely implemented in compile-time template metaprogramming; in addition there's some run-time code to output the interesting part. The program was successfully tested with g++ 4.0.2 on Linux, but should work on any platform with any sufficiently standard conforming C++ compiler.
The general program structure thus is as follows:
<<turing.cc>>= turing machine output code
The turing machine
The turing machine consists of four parts: The tape, the read/write head, the state machine, and the table the state machine is driven by. The tape stores the data. Since we have a two-symbol turing machine, the stored data are just bits. Thus the tape can be modelled as function which maps the time and the position to a bit value. The head has at any time a certain position. Thus the head can be implemented as function which maps time to position. Similarly the state machine can be implemented as function mapping time to states. Finally the table, which contains the actual program run by the turing machine, is a mapping from current state and read bit value to the three values of new state, new bit value to write, and displacement of the head (-1 for left, +1 for right).
First, the basic types, as used in the description above, are defined.
Since the tape is infinite to both sides, the position is modeled by an int.
<<turing machine>>= typedef int position;
The only movements allowed are a single step to the left and a single step to the right. To enforce this at compile time, an enum type is used (relying on the implicit enum->int conversion). However, since after reaching the halt state, the head doesn't move any more, the displacement none is also included for the halt state.
<<turing machine>>= enum displacement { left = -1, none = 0, right = 1 };
Similar considerations hold for the states. In our case, we have three states which are simply called A, B and C, and an additional halt state.
<<turing machine>>= enum states { halt, A, B, C };
We also need a type for the symbols. Since we only have two symbols, a bool will do.
<<turing machine>>= typedef bool symbol;
Finally, we need a variable describing time. We describe the time by the number of steps since the initial value. Since this by definition cannot be negative, an unsigned int is used. Also, the constant initial is defined for time 0.
<<turing machine>>= typedef unsigned int Time; Time const initial = 0;
Now we are ready to define the actual parts of the turing machine. Since they heavily refer to each other, all of them get forward-declared.
<<turing machine>>= template<Time t, position pos> struct tape; template<Time t> struct head; template<Time t> struct state_machine; template<states t, symbol value> struct table;
As described above, the tape maps time and position to symbols. To calculate the symbol, we have to look at the machine one step earlier. If at that time, the head was at the requested position, the symbol has changed according to the table depending on the previous symbol at the same position and the state the machine was in. Otherwise, the symbol didn't change.
<<turing machine>>= template<Time t, position pos> struct tape { static symbol const value = head<t-1>::pos == pos? table<state_machine<t-1>::state, tape<t-1,pos>::value>::new_value : tape<t-1,pos>::value; };
Of course, the initial state of the tape has to be provided explicitly. Since the machine is running a busy beaver, the tape is initially empty.
<<turing machine>>= template<position pos> struct tape<initial, pos> { static symbol const value = 0; };
The head can calculate the position at time t from the position at time t-1 by adding the displacement read from the table depending on the previous state/symbol.
<<turing machine>>= template<Time t> struct head { // the position is the position of the last step plus // the displacement found in the state table for the // previous state/tape value static position const pos = head<t-1>::pos + table<state_machine<t-1>::state, tape<t-1,head<t-1>::pos>::value>::move; };
At the beginning, the head starts at position 0.
<<turing machine>>= template<> struct head<initial> { static position const pos = 0; };
The state machine simply reads the current state from the table at the previous state/symbol.
<<turing machine>>= template<Time t> struct state_machine { // the state is the new state for the previous // state/tape value in the state table static states const state = table<state_machine<t-1>::state, tape<t-1,head<t-1>::pos>::value>::new_state; };
The turing machine starts being in state A.
<<turing machine>>= template<> struct state_machine<initial> { static states const state = A; };
Finally, we need the table driving the turing machine. The data is completely in the specializations of the already declared template.
First, the halting state is defined. The halting state is characterized by the fact that nothing changes any more.
<<turing machine>>= template<symbol value> struct table<halt, value> { static states const new_state = halt; // halt remains halt static symbol const new_value = value; // the value doesn't change static displacement const move = none; // we don't move any more };
The table for the other states defines the program the machine runs, i.e. here the busy beaver.
<<turing machine>>= template<> struct table<A, 0> { static states const new_state = B; static symbol const new_value = 1; static displacement const move = right; }; template<> struct table<A, 1> { static states const new_state = C; static symbol const new_value = 1; static displacement const move = left; }; template<> struct table<B, 0> { static states const new_state = A; static symbol const new_value = 1; static displacement const move = left; }; template<> struct table<B, 1> { static states const new_state = B; static symbol const new_value = 1; static displacement const move = right; }; template<> struct table<C, 0> { static states const new_state = B; static symbol const new_value = 1; static displacement const move = left; }; template<> struct table<C, 1> { static states const new_state = halt; static symbol const new_value = 1; static displacement const move = right; };
The output code
While the above is a complete description of the turing machine, it does not actually do anything. What is wanted, is a program which actually outputs the actions of the turing machine when run. Thus we need to create some run-time code which is able to display it. This has to be in template metaprogramming style, too, since there's no way to instantiate a template based on runtime values.
Basically, the following is a compile-time program running the above turing machine and constructing a set of (runtime) functions which display the results. The output format is as follows:
For each step, there's a separate line starting with the current time, followed by the interesting section of the tape, and then finally the current state. The head's position is indicated by using different symbols for the tape states.
For the output at runtime, we now need some headers.
<<output code>>= #include <iostream> #include <ostream> #include <iomanip>
We also need strings with names for the states, which can be done with a simple array.
<<output code>>= char const* statename[4] = { "(halt)", "A", "B", "C" };
We also need to define the characters representing 0 and 1, both at the head position and elsewhere. For the non-head positions, the characters '*' and '|' are used, corresponding to the usage on the above mentioned web site. At the head position, the characters 'o' and 'I' are used instead. This mapping is done through a template metafunction.
<<output code>>= template<symbol s, bool at_head> struct display_symbol; template<> struct display_symbol<0, false> { static char const value = '*'; }; template<> struct display_symbol<1, false> { static char const value = '|'; }; template<> struct display_symbol<0, true> { static char const value = 'o'; }; template<> struct display_symbol<1, true> { static char const value = 'I'; };
What actually is needed is a map from time and position to the corresponding character. This is done by the following metafunction, which uses the above.
<<output code>>= template<Time t, position p> struct tape_symbol { static char const value = display_symbol<tape<t, p>::value, head<t>::pos == p>::value; };
This can be used to output a section of the tape. This is done through a metaprogramming loop, which for a given time t loops through a given range of positions. It follows the usual C convention that the given end value is outside the specified range.
<<output code>>= template<Time t, position start, position end> struct print_tape { static void out(std::ostream& os) { os << tape_symbol<t, start>::value; print_tape<t, start+1, end>::out(os); } }; template<Time t, position end> struct print_tape<t, end, end> { static void out(std::ostream&) { } };
We also have to loop through time, to see the turing machine in action. This is done by the following template.
<<output code>>= template<Time tmin, Time tmax, position startpos, position endpos> struct print_evolution { static void out(std::ostream& os) { os << std::setw(2) << tmin << ": "; print_tape<tmin, startpos, endpos>::out(os); os << " state: " << statename[state_machine<tmin>::state] << "\n"; print_evolution<tmin+1, tmax, startpos, endpos>::out(os); } }; template<Time tmax, position startpos, position endpos> struct print_evolution<tmax, tmax, startpos, endpos> { static void out(std::ostream&) { } };
Ok, finally we have to call that. The busy beaver needs 13 steps, but 15 steps are run to see that the halt state works (remember that the 16 is one-past-end). The tape range displayed is chosen so that the interesting stuff is displayed without too much unneeded empty tape left and right.
<<output code>>= int main() { print_evolution<initial, 16, -5, 6>::out(std::cout); }
Running the program gives the following output:
0: *****o***** state: A 1: *****|o**** state: B 2: *****I|**** state: A 3: ****o||**** state: C 4: ***o|||**** state: B 5: **o||||**** state: A 6: **|I|||**** state: B 7: **||I||**** state: B 8: **|||I|**** state: B 9: **||||I**** state: B 10: **|||||o*** state: B 11: **||||I|*** state: A 12: **|||I||*** state: C 13: **||||I|*** state: (halt) 14: **||||I|*** state: (halt) 15: **||||I|*** state: (halt)
At time 0 (initial state), the tape is empty (symbolized by '*', or 'o' at head position), and the state machine is in state A. After 13 steps, the machine reached halt status. Now the tape contains 6 ones (symbolized by '|', or 'I' at head position). From then on, there's no change any more.
| Download code |