-
Notifications
You must be signed in to change notification settings - Fork 0
Turing Machines : Implementation Choices
Since the sets of states and symbols are countable, we use integers to represent the elements of these sets. Let M be a machine of T_mn, i.e. with m symbols and n states.
The symbols of M are the m first natural integers, i.e {0, 1, ..., m-1}. By convention 0 is the blank symbol.
M is an element of T_mn so it may have n states. In fact, M has n + 1 states : n operational states, used for the computations, and one halt state, where the machine goes when it wants to halt (if this case occurs). Of course, no action can follow a transition to the halt state.
These n + 1 states are indexed from 0 to n. By convention, 0 is the start state and n is the halt state.
The tape of a Turing machine is supposed to be infinite. In our implementation, the tape is a double ended queue (STL deque) that we resize when the machine wants to overtake the actual tape size. We also need an integer to know where on the tape the head is.
The Turing machines we choose to implement have only two possible moves : moving right and moving left. Immobility is not allowed but the computational power remains the same. So counting shifts and counting steps are the same. We use a boolean variable to store the direction, with the following correspondence : false <-> left, true <-> right.