Usage

1. Create a file that will contain the turing machine description. Sample turing descriptions are provided by the repository. For the syntax, [see below](Syntax of a turing description file)
2. run ./turing <turing machine file path> <tapelength> <input tape contents>
3. the program will run and show you how the tape changes over time and how the tape head moves over the tape.

Example usage

This is an example run of one of the included example turing machines

$ ./src/turing ./examples/simple.t 50 0000__                  # command, runs the simple turing machine
                                                              # with a tape of length 50 (arbitrary)
                                                              # and initial contents 0000_
                                                              # this machine checks if the input string contains
                                                              # a power of 2 zeros
examples/simple.t> Parsing file examples/simple.t ... 

> Starting simulation... 

 q1 0000__                                                    # initial tape state (in state q1; head at start of tape)
_ q2 000__                                                    # read one character and wrote a space, now in q2
_x q3 00__                                                    # read another character and wrote an x, in q3
_x0 q4 0__                                                    # etc
_x0x q3 __
_x0 q5 x__
_x q5 0x__
_ q5 x0x__
 q5 _x0x__
_ q2 x0x__
_x q2 0x__
_xx q3 x__
_xxx q3 __
_xx q5 x__
_x q5 xx__
_ q5 xxx__
 q5 _xxx__
_ q2 xxx__
_x q2 xx__
_xx q2 x__
_xxx q2 __

> Done!

> Input accepted in state: q_accept                            # Simulation ended in q_accept state

Syntax of a turing description file

The syntax is as follow:

<int:amount of states that follows>
<state>
...
<state>
<transition>
...
<transition>

State syntax

The syntax for a state description is:

<name> <special>

name

unique identifier of the state

special

Can be one of:

• A for accept state
• R for reject state
• empty

Transition syntax

The syntax for a transition description is:

<from state> <input> -> <to state> <write char> <move>

from state

One of the state identifiers

input

Input token on which the transition occurs

to state

One of the state identifiers

write char

Token to write to the tape before the tape head moves.

• _ is used as a <space> character
• \ is used as a character that denotes do not write anything

move

Either L or R for left/right movement of the tape head