We present a graphical simulator of 1-Tape, k-Tapes, deterministic and non deterministic Turing machines. The simulator is written in Java and as such it runs on most platforms. During and after the computation it returns interesting features such as the amount of space visited/used and the number of steps. When simulating non-deterministic Turing machines it allows to browse the \tree" of non deterministic computations. It is developed purely for didactic purposes: it can be used in courses of Foundations of Computer Science, in courses of Computational Complexity, as well as in didactic projects with high schools.
When computer science students meet computation models, and in particular Turing machines, they nd useful (and even funny) testing their rst programs using a simulator. Although encoding a simulator can be proposed as a useful exercise using a high level programming language, the availability of a graphical working simulator is in general very appreciated.
Several existing simulators are available, some of them running on Android and iOS. However, the availability of multi-platform simulators is rather limited, and, as far as the authors know, there is only one simulator for multi tape deterministic Turing machines, and no simulators at all for non-deterministic Turing machines. With this communication we would like to present a graphical simulator of 1-Tape, k-Tapes, deterministic and non deterministic Turing machines that, being written in Java, runs on most operating systems, and in particular it is tested on Windows, Linux, and macOS. The simulator (.jar) is available for free download and use from http://clp.dimi.uniud.it/sw/.
We rely on the syntax based on 5-tuples (q; s; q0; s0; L=R) as originally
presented by Alan Turing in his seminal paper On Computable Numbers, with an
Application to the Entscheidungsproblem [
As anticipated above, Turing Machine simulators are available. A complete
analysis is out of the scope of this paper. We just survey some of them focusing
on those based on a 5-tuple syntax. Some of them are obsolete, such as [
The tool we present (split in two components, A-machine and NA-machine,
N standing for Non deterministic) is devised as a support for students of
Computer Science or Mathematics, but it can be used for didactic projects with high
schools (e.g., PLS project). However, the authors hope that it can be of
interest of passionate scienti c readers of introductory books such as The Universal
Computer [
A Turing Machine is a 4-tuple hQ; ; P; q0i where Q is a nite set of (mental) states, q0 2 Q is the initial state, is the alphabet of the machine, that should contain at least two symbols: one symbol for the \empty" cell (blank) \ " and another symbol (tally). P is a set of 5-tuples of the form (q; s; q0; s0; m) where q; q0 2 Q, s; s0 2 and m 2 fL; Rg where L stands for left and R for right such that for each pair (q; s) there is at most one tuple beginning with q; s in P to guarantee determinism.
An instantaneous description (ID) is a 4-tuple hq; `; s; ri where q is the current state, `sr denotes the \interesting" portion of the tape: ` the string at the left of the head, s the symbol currently read, and r the string at the right of the head. P allows us to determine the deterministic relation successor (`) among IDs, and hence, the notion of computation. A machine halts if (and only if) the current ID is hq; `; s; ri and no tuples starting with q; s is in the program P .
Some common variations are allowed in Turing Machines. For instance, the
possibility of staying in the same position (that can be simulated by the
execution of two consecutive instructions L and R) We refer to this feature as
S (for \Stay"). In [
It is well-known that a Turing machine with tape limited on one side (e.g.,
on the left) is su cient to prove the equivalence between the set of Turing
computable function and the set of (partial) recursive function (see, e.g., [
Following [
Last, non determinism must be kept into account (leading to the famous open problem P vs NP). Non deterministic Turing machines are simply one-tape machines1 with the unique (but crucial) di erence that P is no longer a function: more than one tuple starting with a pair q; s are allowed. This leads to a de nition of ` which is no longer deterministic. Starting from an initial ID0 = hq0; "; B; xi,2 the machine can run a set of non-deterministic computations. This set can be visualized as paths in a tree rooted by ID0 and we refer to it as the tree of non deterministic computations (brie y, ND tree). 3
The rst tool we present in this paper is the A-Machine; its name is inspired
from [
If at each stage the motion of a machine [...] is completely determined by the con guration, we shall call the machine an \automatic machine" (or a-machine).
The simulator is written in Java, using the graphical library JavaFX. It is multiplatform and tested under Linux, Windows, and macOS systems.
The alphabet contains two symbols by default: # and blank ( ). # is used as an ASCII version of B (it is not a technical problem, but we experimentally realized that its absence in the keyboards decreases the usability) and starts every tape. New symbols can be added by selecting the option in the upper right square (see Fig. 1). Each state has its unique name and an optional description. 1 Multi tape non-deterministic Turing machines are easy to be de ned. 2 " denotes, as usual, the empty string. States can be added by selecting the option in the lower right square. A new machine is endowed with the initial state q0 and the \pseudo" states yes, no, and halt (see Section 2).
Program instructions are added by clicking \+" below the left table. There is a text eld where a description of the instruction can be added. Instructions can be later easily modi ed or cancelled. Some facilities to sort instructions, symbols, and states are available. Programs can be saved and retrieved.
The machine has one tape as default. New tapes can be can be added or erased. All tapes start with #. The input in the tape can be written/erased by clicking on the pencil in the right low corner.
Execution can be launched/interrupted by pressing on the common animation buttons. In Fig. 2 we report one example of execution. From the menu Computation (see Fig. 1), the user can select the Computation log and get all details (step by step) of the computation, the number of computation steps (info related to the time complexity), and the numbers of total cells and of new cells used (info related to space complexity).
The simulator have also other features that can be read in the manual available at the download site. We just give a quick overview here. I/O Turing machines can be generated and used by the tool. The programmer can choose if generate a new \standard" Turing machine or a I/O one. In the latter case the machine starts with 3 tapes. Veri cation of the constraints of I/O Turing machines are checked during programming. The interpreter is capable of using other machines as sub-routines (Turing referred to them as skeleton tables ). They can be selected by specifying the path of the corresponding le. With this trick it is possible to de ne (mutually) recursive machines. The interpreter is capable of de ning and running more machines at the same time.
Although there is no proof of the fact that the main deterministic and non deterministic time computational classes are di erent (or equal) every computer scientist has experienced the exponential blow up that emerges in the simulation of a non deterministic Turing Machine with a deterministic one, when building and/or visiting the tree of non-deterministic computations. This intrinsic di culty often leads students to avoiding the activity of programming non deterministic Turing Machine even for simple examples. The simulator we are presenting here could represent a support in the early stages of the study of non deterministic classes by automatically executing the code in a breadth rst fashion and allowing the user to zoom on the interesting part of the ND tree. Handling of graphics is in this case demanded to the graphical Java environment Swing.
We refer as NA-machine (non deterministic A-machine) to this version of the simulator. The overall appearance of the program and user interface is the same as of A-machine for adding symbols, states, instructions. The constraint that for each pair q; s there is at most one instruction beginning with q; s is of course relaxed to allow non-determinism.
Three windows reporting computation data can be analyzed. Statistics keeps track of some general info on the ND tree and of the number of \yes" node that has been reached; ND Tree shows the main structure of the ND tree: the picture of the tree can be enlarged and, clicking on a node, the corresponding ID is shown; Instantaneous description reports the list of the all IDs associated with the nodes of the ND tree. See Fig. 3 for an example. We have presented a Java simulator for one tape, multi tape, deterministic and non deterministic Turing machines. The language of the interpreter (Italian vs English) can be selected modifying a settings le. The authors are ready to modify the simulators and/or add di erent features according to user requests.
Research partially supported by the University of Udine PRID ENCASE project.