The Halting Problem
It is possible that a TM does not halt for some inputs. For example, consider the TM with .
The halting problem states that it is undecidable to check if an arbitrary TM will halt on a given input string. This problem has profound implications, because it shows that there are problems that cannot be computed by TMs and, if the Church-Turing thesis is true, it means that no algorithm can solve this problems.
For a TM simulator this is very bad news, because it implies that the simulator could enter in an infinite loop.
We can not completely avoid this problem, but we can solve a restricted form of it. Consider the case of a nondeterministic TM were there are branches of the computation tree that enter an infinite loop and grow forever where others reach a final state. In this case the simulator should halt accepting the input string. But if we traverse the tree in a depth first search (DFS) fashion, the simulator will get stuck when it enters one of the infinite branches. To avoid this the simulator will traverse the computation tree via breadth first search (BFS). BFS is a graph traversal strategy that explores all the children of a branch prior to proceeding to their successors.
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.
Contact Us