Turing machine simulator (C Plus Plus, Generic Programming)

From LiteratePrograms

Other implementations: C | C++ | C++ | Haskell | Java | LaTeX | OCaml | Ruby | Scheme | Sed | Unlambda

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 is implemented using generic programming techniques. The program was successfully tested with gcc version 4.1.2 20061115 (prerelease) (Debian 4.1.1-21) on Linux, but should work on any platform with any sufficiently standard conforming C++ compiler.

Contents 1 Definition of the turing machine 2 Definition of the busy beaver 3 The concepts 3.1 Symbol 3.2 State 3.3 Tape 3.4 Head 3.5 StateTable 4 The code 4.1 The tape 4.1.1 The tape constructor 4.1.2 Getting the head 4.1.3 Printing the tape 4.2 The head 4.2.1 The constructor 4.2.2 Head movement 4.2.3 Reading and writing the tape 4.3 The state machine 4.3.1 The state machine function 4.3.2 Doing a single step 4.3.3 Printing the machine state 4.4 The state table 4.4.1 Initial and halt state 4.4.2 Table lookup functions 4.4.3 The table data 4.4.4 Text representation of states and symbols 4.5 The main function 4.6 Putting things together

Definition of the turing machine

A turing machine consists of several parts:

• A tape which is infinite on one or both sides, and at each position contains one of a finite set of symbols.
• A read/write head which can move along the tape one position at a time, read the symbol at the current position, and replace that symbol with another symbol.
• A state machine, which controls the read-write head according to a table defining the actual program.

The state machine's table contains for each combination of current state and current symbol at the head's position

• what symbol to write at that position (replacing the current symbol)
• in which direction (left or right) to move the head afterwards
• the next state of the state machine

There's a special "halt" state, which causes the turing machine to stop operation. Usually that halt state is not counted, i.e. an n-state turing machine has actually n+1 states: n "working" states and the halt state.

Definition of the busy beaver

A busy beaver is turing machine with the following properties:

• It has exactly two symbols. One of them may be called "blank" or "zero", the other symbol may be called "one".
• It runs on a tape which is infinite on both sides.
• If started on an empty tape (i.e. one which is filled with the "blank" symbol), it stops after a finite number of steps. After that, the tape contains as many ones as possible.

The concepts

One of the corner building blocks of generic programs are the concepts used in the program. Unfortunately C++ doesn't yet support the direct expression of the concepts in the code (C++0x will allow that, though). The following sections describe the concepts used in the program.

Note that the state machine doesn't have its own concept, because it is implemented as function (after all, it does something).

Symbol

The concept Symbol models a single symbol on the tape.

• Refinement of:
  • DefaultConstructible
  • CopyConstructible
  • CopyAssignable
• Associated types: none
• Required functions:
  • char symbol_char(Symbol, bool at_head)

    Returns a character representing the passed symbol on output. The parameter at_head tells whether the character for use at the head position shall be returned.

State

The concept State models a state of the state machine.

• Refinement of:
  • DefaultConstructible
  • CopyConstructible
  • CopyAssignable
• Associated types: none
• Required functions:
  • char const* state_name(State)

    Returns a C string giving the name of the state.

Tape

The concept Tape models the infinite tape of the turing machine. Note that all manipulation of the tape is done through its head.

• Refinement of: none
• Associated types:
  • Tape::symbol_type

    This is the type used for the symbol. It must be a model of Symbol.

  • Tape::head_type

    This is the type used to descripe the read/write head for this tape. It must be a model of Head.

• Required functions:
  • head_type Tape::head()

    Returns a head pointing to the starting position.

  • void Tape::print(head_type const& head) const

    Writes the tape to std::cout

    Note: This function actually isn't very generic and will probably be reworked later

Head

The concept Head models the read/write head of the turing machine. From the semantics, it could have been modeled as a bidirectional iterator. Since the full functionality of a bidirectional iterator isn't needed, and the existing bidirectional iterators don't model an infinite sequence anyway, a separate concept is used. This desicion might be reconsidered in the future.

• Refinement of:
  • CopyConstructible
  • CopyAssignable
• Associated types:
  • Head::symbol_type

    The type of the symbols read from and written to the tape

• Required functions:
  • void left()

    Moves the head one position to the left.

  • void right()

    Moves the head one position to the right.

  • symbol_type read()

    Reads the symbol from the tape at the current head position.

  • void write(symbol_type)

    Writes a symbol to the tape at the current head position.

StateTable

The state table describes the states and associated actions of the turing machine.

• Refinement of:
  • Copy constructible
• Associated types:
  • StateTable::state_type

    Describes the states of the turing machine. It must be a model of State.

  • StateTable::direction_type

    Describes the direction. There must be constants StateTable::left and StateTable::right of this type. It must be of a type suitable for switch.

  • StateTable::symbol_type

    Describes the symbols of the turing machine. It must be a model of Symbol.

• Required functions:
  • state_type StateTable::initial_state()

    Gives the initial state of the state machine

  • state_type StateTable::halt_state()

    Gives the halt state of the state machine

  • symbol_type StateTable::newsymb(state_type oldstate, symbol_type oldsymb)

    Gives the new symbol written when the current state is oldstate and the read symbol is oldsymb.

  • direction_type direction(state_type oldstate, symbol_type oldsymb)

    Gives the direction in which the head will be moved when the current state is oldstate and the read symbol is oldsymb.

  • state_type newstate(state_type oldstate, symbol_type oldsymb)

    Gives the state the state machine switches to when the current state is oldstate and the read symbol is oldsymb.

The code

The tape

The tape class is a model of the concept Tape. It is parametrized on the type of symbol the tape stores.

The public interface is mostly a straightforward implementation of the Tape concept. The only addition is a constructor, which allows to specify how many of the tape positions are generated on construction, and at which position the head will start. If the head ever moves outside that initial region, the storage will automatically be extended.

Note tape<Symbol>::head_type is implemented as member class. This implementation detail makes sense because the head is quite dependent from the tape (it has to access the internal representation; indeed, it is the only way to modify the tape after construction).

The tape itself is represented by a std::list<Symbol>.

<<includes>>=
#include <list>
<<tape>>=
template<typename Symbol> class tape
{
public:
  typedef Symbol symbol_type;
  class head_type;
  friend class head_type;
  tape(int start_size = 1, int start_pos = 0);
  head_type head();
  void print(head_type const& head) const;
private:
  typedef std::list<Symbol> tape_impl;
  tape_impl the_tape;
  int the_start_pos;
};

The tape constructor

The constructor creates an empty tape, of which start_size positions (minimum: 1) are already stored. An empty tape in this concept means a tape filled with the value one gets from Symbol's default constructor.

<<includes>>=
#include <cassert>
<<tape constructor>>=
template<typename Symbol>
 tape<Symbol>::tape(int start_size, int start_pos):
   the_tape(start_size),
   the_start_pos(start_pos)
{
  assert(start_size >= 1);
  assert(start_pos >= 0);
  assert(start_pos < start_size);
}

Getting the head

This function just creates a head which is the_start_pos positions right of the leftmost stored one.

<<tape head>>=
template<typename Symbol>
 typename tape<Symbol>::head_type tape<Symbol>::head()
{
  return head_type(the_tape, the_start_pos);
}

Printing the tape

This prints the tape to std::cout. Note that symbol_char is found through argument-dependent lookup.

<<includes>>=
#include <iostream>
<<tape print>>=
template<typename Symbol>
 void tape<Symbol>::print(head_type const& head) const
{
  for (typename tape_impl::const_iterator i = the_tape.begin(),
                                          end = the_tape.end();
       i != end;
       ++i)
    std::cout << symbol_char(*i, i == head.position);
}

The head

This nested class head_type of tape<Symbol> implements the read/write head. The public interface is just a straightforward implementation of the Head concept. Internally, it holds a reference to and an iterator into the tape representation. Note that the iterator always points to a valid object of type Symbol (no one-past-end iterator).

The constructor is private, so that only the tape class can construct a new head. However, the head can be freely copied using the compiler-generated copy constructor.

<<head>>=
template<typename Symbol> class tape<Symbol>::head_type
{
  friend class tape;
public:
  typedef Symbol symbol_type;
  void left();
  void right();
  Symbol read();
  void write(Symbol);
private:
  tape_impl& tape;
  typename tape_impl::iterator position;
  head_type(tape_impl&, int start_pos);
};

The constructor

The head constructor creates an iterator to the internal representation and advances that to the requested position.

<<includes>>=
#include <iterator>
<<head constructor>>=
template<typename Symbol>
 tape<Symbol>::head_type::head_type(tape_impl& t, int start_pos):
   tape(t),
   position(t.begin())
{
  std::advance(position, start_pos);
}

Head movement

Generally, the head movement functions just move the internal iterator. However, when the iterator reaches the end of the stored sequence, the sequence must be extended by the corresponding value.

<<head movement>>=
template<typename Symbol>
 void tape<Symbol>::head_type::left()
{
  if (position == tape.begin())
  {
    tape.push_front(Symbol());
    position = tape.begin();
  }
  else
    --position;
}
template<typename Symbol>
 void tape<Symbol>::head_type::right()
{
  ++position;
  if (position == tape.end())
  {
    tape.push_back(Symbol());
    position = tape.end();
    --position;
  }
}

Reading and writing the tape

The read and write functions just dereference the iterator and return resp. assign to the result.

<<head read/write>>=
template<typename Symbol>
 Symbol tape<Symbol>::head_type::read()
{
  return *position;
}
template<typename Symbol>
 void tape<Symbol>::head_type::write(Symbol s)
{
  *position = s;
}

The state machine

The state machine is implemented as function template run_turing_machine, with two helper function templates. The first helper function template, process, does one single step of the turing machine. The second helper function, print, shows the current state.

The state machine function

The function run_turing_machine takes a state table as argument, constructs all parts needed for the turing machine, and then runs the turing machine until it reaches the halt state, printing the current state at each step.

<<state machine function>>=
template<typename StateTable>
 void run_turing_machine(StateTable table, int tape_size, int tape_pos)
{
  typedef typename StateTable::symbol_type symbol_type;
  typedef typename StateTable::state_type state_type;
  typedef tape<symbol_type> tape_type;
  tape_type tape(tape_size, tape_pos);
  typename tape_type::head_type head = tape.head();
  state_type state = table.initial_state();
  while (state != table.halt_state())
  {
    print(state, tape, head);
    state = process(state, head, table);
  }
  print(state, tape, head);
}

Doing a single step

This function does a single step of the state machine. Note that the head argument is passed by reference, since the head is modified (moved). The function returns the new state the machine is in.

<<process>>=
template<typename StateTable, typename State, typename Head>
 State process(State curstate, Head& h, StateTable tab)
{
  typename StateTable::symbol_type symb = h.read();
  h.write(tab.newsymb(curstate, symb));
  switch (tab.direction(curstate, symb))
  {
  case StateTable::left:
    h.left();
    break;
  case StateTable::right:
    h.right();
    break;
  default:
    assert(!"Should not happen\n");
  }
  return tab.newstate(curstate, symb);
}

Printing the machine state

This function prints the current state of the turing machine, followed by the stored part of the tape. Note that state_name is found through argument_dependent lookup.

<<includes>>=
#include <iomanip>
<<print>>=
template<typename State, typename Tape, typename Head>
 void print(State state, Tape const& tape, Head const& head)
{
  std::cout << "state: "<< std::setw(5) << state_name(state) << ", tape: ";
  tape.print(head);
  std::cout << "\n";
}

The state table

The state table is what defines the particular turing machine. In this case, it's a busy beaver, therefore the class is named busy_beaver. It implements the concept StateTable.

Note that this class is not a template, but a concrete class, because it describes a concrete, specific turing machine. There's nothing generic about this class.

Since this class describes just a single state table (all copies iof the class are equivalent), both the data and all the member functions are static.

The use of friend functions for state_name and symbol_char is to allow argument-dependent lookup to find them. The functions don't actually access any private members of the class.

<<beaver>>=
class busy_beaver
{
public:
  enum state_type { A, B, C, Halt };
  friend char const* state_name(state_type);
  typedef bool symbol_type;
  friend char symbol_char(symbol_type, bool at_head);
  enum direction_type { left, right };
  static state_type initial_state();
  static state_type halt_state();
  static symbol_type newsymb(state_type oldstate, symbol_type oldsymb);
  static direction_type direction(state_type oldstate, symbol_type oldsymb);
  static state_type newstate(state_type oldstate, symbol_type oldsymb);
private:
  struct table_entry
  {
    symbol_type symbol;
    direction_type direction;
    state_type state;
  };
  static table_entry table[3][2];
};

Initial and halt state

These functions are straightforward.

<<beaver initial/halt state>>=
busy_beaver::state_type busy_beaver::initial_state()
{
  return A;
}
busy_beaver::state_type busy_beaver::halt_state()
{
  return Halt;
}

Table lookup functions

These functions just look up the corresponding values in the private array. For this, they make use of the implicit conversion from bool to int and from enum to int.

<<beaver lookup>>=
busy_beaver::symbol_type busy_beaver::newsymb(state_type oldstate,
                                              symbol_type oldsymb)
{
  return table[oldstate][oldsymb].symbol;
}
busy_beaver::direction_type busy_beaver::direction(state_type oldstate,
                                                   symbol_type oldsymb)
{
  return table[oldstate][oldsymb].direction;
}
busy_beaver::state_type busy_beaver::newstate(state_type oldstate,
                                              symbol_type oldsymb)
{
  return table[oldstate][oldsymb].state;
}

The table data

Note that there are no table entries for the halt state, because the lookup functions are never called with that state.

<<beaver data>>=
busy_beaver::table_entry busy_beaver::table[3][2] =
  {{{ true, right, B }, { true, left,  C }},
   {{ true, left,  A }, { true, right, B }},
   {{ true, left,  B }, { true, left,  Halt }}};

Text representation of states and symbols

These functions are also straightforward.

<<state/symbol text>>=
char const* state_name(busy_beaver::state_type state)
{
  switch(state)
  {
  case busy_beaver::A:
    return "A";
  case busy_beaver::B:
    return "B";
  case busy_beaver::C:
    return "B";
  case busy_beaver::Halt:
    return "Halt";
  default:
    assert(!"Invalid state");
  }
}
char symbol_char(busy_beaver::symbol_type symbol, bool at_head)
{
  if (symbol)
    return at_head? 'I' : '|';
  else
    return at_head? 'o' : '*';
}

The main function

The main function just calls run_turing_machine with an instance of busy_beaver.

<<main>>=
int main()
{
  run_turing_machine(busy_beaver(), 12, 6);
}

Putting things together

<<turing.cc>>=
includes
tape
head
tape constructor
tape head
tape print
head constructor
head movement
head read/write
process
print
state machine function
beaver
beaver initial/halt state
beaver lookup
beaver data
state/symbol text
main

Download code