A simulator of multitape NDTMs in Python

In this section we will present a simulator for nondeterministic TMs with multiple tapes written in Python. 
The simulator consists of two classes: a Tape class and a NDTM class.
Tape instances contain the list of current scanned cells and an index to the tape head, and provide the following operations: 
 

• readSymbol(): returns the symbol scanned by the head, or a blank if the head is in the last scanned cell
• writeSymbol(): replaces the symbol scanned by the head by another one. If the head is in the last scanned cells, appends the symbol to the end of the list of symbols.
• moveHead(): moves the head one position to the left (-1), to the right (1) or no positions (0).
• clone(): creates a replica or copy of the tape. This will be very useful for simulating nondeterminism

NDTM instances have the following attributes: 
 

• the start and final states.
• the current state.
• the list of tapes (Tape objects).
• a dictionary of transitions.

The transition function is implemented with a dictionary whose keys are tuples (state, read_symbols) and whose values are lists of tuples (new_state, moves). For example, the TM that adds numbers in unary notation presented before will be represented as:
 

{('q0', ('1', '#')): [('q0', (('1', 'R'), ('1', 'R')))],
 ('q0', ('0', '#')): [('q0', (('0', 'R'), ('#', 'S')))],
 ('q0', ('#', '#')): [('q1', (('#', 'S'), ('#', 'S')))]}

Note how the Python representation closely resembles the mathematical definition of the transition function, thanks to Python versatile data structures like dictionaries, tuples and lists. A subclass of dict, defaultdict from the standard collections module, is used to ease the burden of initialization.
NDTM objects contains methods for reading the current tuple of symbols in the tapes, for adding, getting and executing transitions and for making replicas of the current TM.
The main method of NDTM is accepts(). Its argument is an input string and it returns an NDTM object if any branch of the computation tree reaches the accepting state or None if neither branch does. It traverses the computation tree via breadth first search (BFS) to allow the computation to stop if any branch reaches the accepting state. BFS uses a queue to keep track of the pending branches. A Python deque from the collections module is used to get O(1) performance in the queue operations. The algorithm is as follows:
 

Add the TM instance to the queue
While queue is not empty:
   Fetch the first TM from the queue
   If there is no transition for the current state and read symbols:
      If the TM is in a final state: return TM
   Else:
      If the transition is nondeterministic:
         Create replicas of the TM and add them to the queue
      Execute the transition in the current TM and add it to the queue

Finally, the NDTM class has methods to print the TM representation as a collection of instantaneous descriptions and to parse the TM specification from a file. As usual, this input/output facilities are the most cumbersome part of the simulator.
The specification files have the following syntax
 

% HEADER: mandatory
start_state final_state blank number_of_tapes
% TRANSITIONS
state read_symbols new_state write_symbol, move write_symbol, move ...

The lines starting with ‘%’ are considered comments. For example, the TM that adds numbers in unary notation has the following specification file:
 

% HEADER
q0 q1 # 2
% TRANSITIONS
q0 1, # q0 1, R 1, R
q0 0, # q0 0, R #, S
q0 #, # q1 #, S #, S

States and symbols can be any string not containing whitespaces or commas.
The simulator can be run from a Python session to explore the output configuration. For example if the preceding file is saved with name “2sum.tm”:
 

The output shows that the simulator has produced the sum of the 1’s in tape #1:
 

Output :
q1: ['1', '1', '0', '1', '1', '1', '0', '1']['#']
q1: ['1', '1', '1', '1', '1', '1']['#']

The output shows the contents of the two tapes, the positions of the heads (second list of each tape) and the final state of the TM.
 

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.