The simulator is written in Python 3 and uses all the power and expressiveness of this programming language, combining objectoriented and functional programming methods.
The organization is as follows. First, TM is introduced informally, highlighting its many applications in theoretical CS. Then the formal definitions of the base model and the multiline option are provided. Finally, the design and implementation of the simulator is presented, examples of its use and execution are given.
ТМ — these are abstract automata developed by Alan Turing in 1936 to explore the frontiers of computation. TM can calculate functions according to simple rules.
TM — it is a primitive computational model with 3 components:
The TM operation consists of three stages:
TM have many applications in theoretical computer science and are closely related to the theory of formal language. TM — these are language recognizers that adopt the highest class of the Chomsky language hierarchy: type 0 languages generated by unrestricted grammars. They are also language converters: given an input string from one language, TM can evaluate an output string from the same or a different language. This capability allows TMs to compute functions whose inputs and outputs are encoded as strings of a formal language, for example, binary numbers viewed as a set of strings in the alphabet {0, 1}.
ChurchTuring claims that TMs are capable of computing any a function that can be expressed by the algorithm. This means that TM are actually universal computers, which, being abstract mathematical devices, do not suffer from the limitations of physical time and space. If this thesis is correct, as many computer scientists believe, the fact that Turing discovered that there are functions that cannot be computed by TM implies that there are functions that cannot be algorithmically computed by any computer in the past, present, or the future.
TM have also been very important in the study of computational complexity and one of the central unsolved problems in CS and mathematics: the P vs NP problem. TM are a convenient hardwareindependent model for analyzing the computational complexity of algorithms in terms of the number of steps performed (time complexity) or the number of scanned cells (spatial complexity) during computation.
Turing Machine (TM) is a 7tuple where:
At each stage of the calculation, a TM can be described by an instant description (ID). The id is ternary where is the actual state, the string contained in the cells to the left of the cell scanned by the machine and the string contained in the current cell and other cells to the right of the ribbon head until the cell starting an infinite sequence of spaces.
Binary relation links two identifiers and is defined as follows, for all and and :
Allow to be transitive and reflective closure , i.e. applying zero or more transitions between identifiers. Then the language recognized by is defined as: ,
If for all states and ribbon symbols , has a maximum of one element, which is called TM deterministic. If there are transitions with more than one choice, TM is nondeterministic.
The sequence of identifiers of deterministic TMs is linear. For nondeterministic TM, it forms a computation tree . Nondeterminism can be thought of as if the machine created its own replicas that run in parallel. This useful analogy will be used by our simulator.
At first glance, we might think that nondeterministic TMs are more powerful than deterministic TMs because they are able to “guess” the correct path. But this is not the case: the DTM is only a special case of the NDTM, and any NDTM can be converted to a DTM. Thus, they have the same processing power.
In fact, several variants of TM have been proposed: with a doublesided endless tape, with several tracks, without a stop option, etc. the same processing power as the base model. They recognize the same class of languages.
In the next section, we present a very useful option: multiline nondeterministic TM.
TM Multitape have multiple I / O tapes with independent heads. This option does not increase the computational power of the original, but, as we will see, it can simplify the construction of TM using auxiliary tapes.
A Ktape TM is a 7tuple where all the elements are the same as in the base TM, except for the transition function, which is a mapping , It maps the readstate character pairs to subsets of the new writestate pairs + directions.
For example, the following twopart TM computes the sum of the numbers stored in unary notation in the first tape. The first tape contains factors: sequences of 1 separated by 0, which are natural numbers. The machine writes all 1s to tape 2, calculating the sum of all factors.
Formally let where is defined as follows:
TM may not stop for some inputs ... For example, consider the TM with ,
The halting problem means that it is unresolvable to check if an arbitrary TM will halt on a given input line. This problem has profound implications because it shows that there are problems that cannot be calculated by TM, and if the ChurchTuring thesis is correct, it means that no algorithm can solve these problems.
This is very bad news for the TM simulator, because it means that the simulator can go into an infinite loop.
We cannot completely avoid this problem, but we can solve its limited form. Consider the case of nondeterministic TM, where there are branches of the computation tree that enter an infinite loop and grow forever where others reach their final state. In this case, the simulator should stop accepting the input string. But if we traverse the tree using depthfirst search (DFS), the simulator gets stuck when it enters one of the infinite branches. To avoid this, the simulator will traverse the computation tree using Breadth First Search (BFS). BFS — it is a graph traversal strategy that examines all children of a branch before proceeding to their descendants.
In this section, we present a simulator for nondeterministic TMs with multiple feeds written in Python.
The simulator consists of two classes: a ribbon class and an NDTM class.
Ribbon instances contain a list of currently scanned cells and a pointer to the ribbon head and provide the following operations:
NDTM instances have the following attributes:
The navigation function is implemented using a dictionary whose keys are — tuples (state, read_symbols), and values — lists of tuples (new_state, move). For example, a TM that adds numbers in the unary notation introduced earlier would be represented as:
{('q0', (' 1', '#')): [('q0', (( '1',' R'), ('1',' R')))], ('q0', (' 0', '#')): [('q0', ((' 0', 'R'), (' # ',' S')))], ('q0', (' # ',' # ')): [(' q1', (('#', 'S') , ('#', 'S')))]}
Note that Python's representation is very similar to the mathematical definition of a transition function, thanks to Python's generic data structures such as dictionaries, tuples, and lists. A subclass of dict, defaultdict, from the standard collections module, is used to ease the burden of initialization.
NDTM objects contain methods for reading the current character set on tapes, for adding, getting and navigating, and for making copies of the current TM.
The main NDTM method is accept (). Its argument is an input string and returns an NDTM object if any branch of the computation tree reaches an accepting state, or None if none of the branches reaches. It traverses the computation tree using Breadth First Search (BFS) to allow computation to stop if any branch reaches an accepting state. BFS uses a queue to keep track of pending branches. Deque Python from Collections module is used to get O (1) performance on queue operations. The algorithm looks like this:
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 for printing a TM representation as a collection of instant descriptions and analyzing a TM specification from a file. As usual, this I / O is the most cumbersome part of the simulator.
The spec 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 ...
Lines starting with '%' are considered comments. For example, a TM that adds numbers in unary notation has the following spec 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 characters can be any string that does not contain spaces or commas.
The simulator can be run from a Python session to examining the output configuration. For example, if the previous file was saved with the name "2sum.tm":

The output shows that the simulator has generated the sum of units on 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 (the second list of each tape), and the final state of the TM.
Excluding I / O code and comments, the simulator is less than 100 lines of code. This is a testament to the power and economy of Python. It's object oriented, but also uses functional constructs like lists.
