Download code

Jump to: navigation, search

Back to Turing_machine_simulator_(C_Plus_Plus,_Generic_Programming)

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,_Generic_Programming)?oldid=14525
 14 */
 15 
 16 
 17 #include <list>
 18 
 19 #include <cassert>
 20 
 21 #include <iostream>
 22 
 23 #include <iterator>
 24 
 25 #include <iomanip>
 26 
 27 
 28 template<typename Symbol> class tape
 29 {
 30 public:
 31   typedef Symbol symbol_type;
 32   class head_type;
 33   friend class head_type;
 34 
 35   tape(int start_size = 1, int start_pos = 0);
 36   head_type head();
 37   void print(head_type const& head) const;
 38 private:
 39   typedef std::list<Symbol> tape_impl;
 40   tape_impl the_tape;
 41   int the_start_pos;
 42 };
 43 
 44 
 45 template<typename Symbol> class tape<Symbol>::head_type
 46 {
 47   friend class tape;
 48 public:
 49   typedef Symbol symbol_type;
 50   void left();
 51   void right();
 52   Symbol read();
 53   void write(Symbol);
 54 private:
 55   tape_impl& tape;
 56   typename tape_impl::iterator position;
 57   head_type(tape_impl&, int start_pos);
 58 };
 59 
 60 template<typename Symbol>
 61  tape<Symbol>::tape(int start_size, int start_pos):
 62    the_tape(start_size),
 63    the_start_pos(start_pos)
 64 {
 65   assert(start_size >= 1);
 66   assert(start_pos >= 0);
 67   assert(start_pos < start_size);
 68 }
 69 
 70 template<typename Symbol>
 71  typename tape<Symbol>::head_type tape<Symbol>::head()
 72 {
 73   return head_type(the_tape, the_start_pos);
 74 }
 75 
 76 template<typename Symbol>
 77  void tape<Symbol>::print(head_type const& head) const
 78 {
 79   for (typename tape_impl::const_iterator i = the_tape.begin(),
 80                                           end = the_tape.end();
 81        i != end;
 82        ++i)
 83     std::cout << symbol_char(*i, i == head.position);
 84 }
 85 
 86 template<typename Symbol>
 87  tape<Symbol>::head_type::head_type(tape_impl& t, int start_pos):
 88    tape(t),
 89    position(t.begin())
 90 {
 91   std::advance(position, start_pos);
 92 }
 93 
 94 template<typename Symbol>
 95  void tape<Symbol>::head_type::left()
 96 {
 97   if (position == tape.begin())
 98   {
 99     tape.push_front(Symbol());
100     position = tape.begin();
101   }
102   else
103     --position;
104 }
105 
106 template<typename Symbol>
107  void tape<Symbol>::head_type::right()
108 {
109   ++position;
110   if (position == tape.end())
111   {
112     tape.push_back(Symbol());
113     position = tape.end();
114     --position;
115   }
116 }
117 
118 template<typename Symbol>
119  Symbol tape<Symbol>::head_type::read()
120 {
121   return *position;
122 }
123 
124 template<typename Symbol>
125  void tape<Symbol>::head_type::write(Symbol s)
126 {
127   *position = s;
128 }
129 
130 template<typename StateTable, typename State, typename Head>
131  State process(State curstate, Head& h, StateTable tab)
132 {
133   typename StateTable::symbol_type symb = h.read();
134   h.write(tab.newsymb(curstate, symb));
135   switch (tab.direction(curstate, symb))
136   {
137   case StateTable::left:
138     h.left();
139     break;
140   case StateTable::right:
141     h.right();
142     break;
143   default:
144     assert(!"Should not happen\n");
145   }
146   return tab.newstate(curstate, symb);
147 }
148 
149 template<typename State, typename Tape, typename Head>
150  void print(State state, Tape const& tape, Head const& head)
151 {
152   std::cout << "state: "<< std::setw(5) << state_name(state) << ", tape: ";
153   tape.print(head);
154   std::cout << "\n";
155 }
156 
157 template<typename StateTable>
158  void run_turing_machine(StateTable table, int tape_size, int tape_pos)
159 {
160   typedef typename StateTable::symbol_type symbol_type;
161   typedef typename StateTable::state_type state_type;
162   typedef tape<symbol_type> tape_type;
163 
164   tape_type tape(tape_size, tape_pos);
165   typename tape_type::head_type head = tape.head();
166   state_type state = table.initial_state();
167 
168   while (state != table.halt_state())
169   {
170     print(state, tape, head);
171     state = process(state, head, table);
172   }
173   print(state, tape, head);
174 }
175 
176 class busy_beaver
177 {
178 public:
179   enum state_type { A, B, C, Halt };
180   friend char const* state_name(state_type);
181 
182   typedef bool symbol_type;
183   friend char symbol_char(symbol_type, bool at_head);
184 
185   enum direction_type { left, right };
186 
187   static state_type initial_state();
188   static state_type halt_state();
189   static symbol_type newsymb(state_type oldstate, symbol_type oldsymb);
190   static direction_type direction(state_type oldstate, symbol_type oldsymb);
191   static state_type newstate(state_type oldstate, symbol_type oldsymb);
192 private:
193   struct table_entry
194   {
195     symbol_type symbol;
196     direction_type direction;
197     state_type state;
198   };
199   static table_entry table[3][2];
200 };
201 
202 busy_beaver::state_type busy_beaver::initial_state()
203 {
204   return A;
205 }
206 
207 busy_beaver::state_type busy_beaver::halt_state()
208 {
209   return Halt;
210 }
211 
212 busy_beaver::symbol_type busy_beaver::newsymb(state_type oldstate,
213                                               symbol_type oldsymb)
214 {
215   return table[oldstate][oldsymb].symbol;
216 }
217 
218 busy_beaver::direction_type busy_beaver::direction(state_type oldstate,
219                                                    symbol_type oldsymb)
220 {
221   return table[oldstate][oldsymb].direction;
222 }
223 
224 busy_beaver::state_type busy_beaver::newstate(state_type oldstate,
225                                               symbol_type oldsymb)
226 {
227   return table[oldstate][oldsymb].state;
228 }
229 
230 busy_beaver::table_entry busy_beaver::table[3][2] =
231   {{{ true, right, B }, { true, left,  C }},
232    {{ true, left,  A }, { true, right, B }},
233    {{ true, left,  B }, { true, left,  Halt }}};
234 
235 char const* state_name(busy_beaver::state_type state)
236 {
237   switch(state)
238   {
239   case busy_beaver::A:
240     return "A";
241   case busy_beaver::B:
242     return "B";
243   case busy_beaver::C:
244     return "B";
245   case busy_beaver::Halt:
246     return "Halt";
247   default:
248     assert(!"Invalid state");
249   }
250 }
251 
252 char symbol_char(busy_beaver::symbol_type symbol, bool at_head)
253 {
254   if (symbol)
255     return at_head? 'I' : '|';
256   else
257     return at_head? 'o' : '*';
258 }
259 
260 int main()
261 {
262   run_turing_machine(busy_beaver(), 12, 6);
263 }


hijacker
hijacker
hijacker
hijacker