Turing Machine Simulator

Turing machines are among the simplest models of computation, and are frequently used in teaching. Our Turing Machine simulator is fast, easy to use, and it can handle non-deterministic Turing machines. 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. It is a slight generalization of the model in Sipser (Introduction to the Theory of Computation).

This is a Turing machine that recognizes words of form a^i.b^i.c^i: Explanation and the input file.

Next we give a Turing machine that recognizes words of form v#w, where v is a substring of w. It does this by non-deterministically throwing away a prefix of w, and then checking what w starts with v: Explanation and the input file.

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 never computes more than 10000 configurations for a single word, but this number can be easily changed in the code.

The simulator reads input from stdin, and prints output in stdout.

Sources are available under the Aladdin Free Public License and can be downloaded in a single zipfile. If you don't touch the file parsing/grammar.m, the simulator can be compiled without the parser generator, but you need the Maphoon lexer. Download the lexer seprately, and set Lexing to the directory containing lexing2023.

The Turing machine simulator was written with the help of Dinislam Madikhanov, Kenessary Myrzakul, and Dastan Sultanov.