Turing machines are among the simplest models of computation. They are frequently used in teaching computability theory. Our Turing machine simulator is fast, easy to use, and it can handle non-deterministic Turing machines using exhaustive search. There exist online Turing machine simulators, but they are too slow for my patience, and cannot handle non-deterministic Turing machines.
Our simulator uses a modified model, which is a small generalization of the model in Sipser (Introduction to the Theory of Computation).
The simulator reads an input file, which must contain a description of the TM together with a set of input words. For each input word, the simulator either prints an accepting computation, or the set of reached configurations. The simulator does not compute more than 10000 configurations for a single input word, but this number can be easily changed in the code. The simulator always reads input from stdin, and prints output into stdout.
On these slides we describe a Turing machine that recognizes words of form a^i b^i c^i, and this is an input file containing the Turing machine with a few input words.
Next we give a Turing machine that recognizes words of form v#w, where v is a substring of w, and # is just a letter. The Turing machine is non-deterministic. It first non-deterministically throws away a prefix of w, and after that checks that w starts with v: Explanation and the input file.
Sources are available under the Aladdin Free Public License and can be downloaded in a single zipfile.
As long as you don't touch the file
parsing/grammar.m, the simulator can be compiled without
the parser generator,
but you will need the Maphoon lexer. Download the lexer separately, and
set variable Lexing in the Makefile
to the directory containing lexing2023.
The Turing machine simulator was written with help of Dinislam Madikhanov, Kenessary Myrzakul, and Dastan Sultanov.