Formal definition: the multitape TM
Multitape TMs have multiple input-output tapes with independent heads. This variant does not increases the computational power of the original, but as we will see it can simplify the construction of TMs using auxiliary tapes.
A k-tape TM is a 7-tuple where all the elements are as in the basic TM, except the transition function that is a mapping . It maps pairs of state-read symbols to subsets of pairs new states-write symbols+directions.
For example, the following 2-tape TM computes the sum of the numbers stored in unary notation in the first tape. The first tape contains factors: sequences of 1’s separated by 0’s that represent natural numbers. The machine writes all the 1’s in tape 2, computing the sum of all factors.
Formally, let where is defined as follows:
- Skip all 0’s:
- Copy 1’s to tape 2:
- Halt when the blank is reached:
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.