Formal definition: the basic model
A Turing Machine (TM) is a 7-tuple where:
- is a finite non-empty set of states.
- is a finite non-empty set of symbols called the tape alphabet.
- is the input alphabet.
- is the transition or next-move function that maps pairs of state symbol to subsets of triples state, symbol, head direction (left, right or stay).
- is the start state.
- is the final accepting state.
- is the blank symbol.
In each step of the computation, a TM can be described by an instantaneous description (ID). An ID is a triple where is the actual state, is the string contained in the cells at the left of the cell being scanned by the machine, and is the string contained in the current cell and the other cells to the right of the tape head until the cell that begins the infinite sequence of blanks.
The binary relation relates two IDs and is defined as follows, for all and and :
- iff
- iff
- iff
- iff
- iff
- iff
Let be the transitive and reflexive closure of , i.e. the application of zero or more transitions between IDs. Then, the language recognized by is defined as: .
If for all states and tape symbols , has at most one element the TM is said to be deterministic. It there exist transitions with more than one choice, the TM is nondeterministic.
The sequence of IDs of deterministic TMs is linear. For nondeterministic TMs, it forms a computation tree. Nondeterminism can be thought as if the machine creates replicas of itself that proceed in parallel. This useful analogy will be used by our simulator.
At a first glance, we can think that nondeterministic TMs are more powerful than deterministic TMs because the ability to “guess” the correct path. But this is not true: a DTM is only a particular case of a NDTM, and any NDTM can be converted to a DTM. So, they have the same computational power.
In fact, several variants of TMs have been proposed: with two-way infinite tape, with several tracks, without stay option, etc. Interestingly, all of these variants are exhibit the same computational power than the basic model. They recognize the same class of languages.
In the next section we introduce a very useful variant: multitape nondeterministic TMs.
Multitape Nondeterministic Turing Machine simulator
This article tackles both theoretical and practical issues in Computer Science (CS). It reviews Turing Machines (TMs), a fundamental class of automata and presents a simulator for a broad variant of TMs: nondeterministic with multiple tapes. Nondeterminism is simulated by a breadth first search (BFS) of the computation tree.
The simulator is written in Python 3 and takes advantage of the power and expressiveness of this programming language, combining object oriented and functional programming techniques.
The organization is as follows. First, TMs are introduced in an informal manner, highlighting its many applications in Theoretical CS. Then, formal definitions of the basic model and the multitape variant are given. Finally, the design and implementation the simulator is presented, providing examples of its use and execution.