I wrote a simulator for Turing machines, including a domain-specific language to write machine definitions and an evaluation system that catches errors and assists in debugging. The code is available [here](https://github.com/sidmani/turing). You might also be interested in my [[Designing a universal Turing machine|universal Turing machine]].
Here's a simple example of a machine that squares a unary number.
```
alphabet [A, B, 1, 0, X, Y, Z]
blank 0
halt H
init Q0
state Q0 {
A: Q0 A R
X: Q0 X R
Z: Q0 Z R
1: Q1 X -
Y: Q1 Z -
B: Q3 B L
}
state Q1 {
X: Q1 X L
A: Q1 A L
1: Q1 1 L
Z: Q1 Z L
0: Q2 1 R
}
state Q2 {
1: Q2 1 R
A: Q0 A -
}
state Q3 {
Z: Q3 Y L
X: Q5 Y L
}
state Q4 {
X: Q4 1 L
A: Q0 A -
}
state Q5 {
X: Q4 X -
A: H A -
}
```
The first few lines are directives.
- `alphabet` specifies the legal alphabet for the machine
- `blank` specifies the default symbol written on blank parts of the tape
- `halt` defines a halting state
- `init` defines the initial state
The `state` block has the following syntax.
```
state <name> {
<symbol>: <new state> <new symbol> <direction>
}
```
Each line in a state block defines a transition rule. Which rule to execute is determined by the symbol at the current head position on the tape, written on the left-hand side of the colon. On the right is the new state of the machine, the symbol to write on the current cell of the tape, and the direction to move (either `R`, `L`, or `-` for no movement).
You can run the machine like so:
```bash
python -m tm examples/square.tm examples/square.tape 0
```
The first argument is the machine definition, the second is the file containing the initial tape data (symbols from the alphabet, separated by spaces), and the third is the initial location of the machine head.
It's surprisingly easy to write programs in this language. For example, here's one that tests if a unary number is prime using trial division, using only 18 states and about 100 lines of code.
```
alphabet [A, B, 1, X, 0, NOT_PRIME, PRIME]
blank 0
halt H
init Q0
# write "2" in unary on the right side of B and move back to B
state Q0 {
A: Q0 A R
1: Q0 1 R
B: Q1 B R
}
state Q1 {
0: Q2 1 R
}
state Q2 {
0: Q3 1 -
}
state Q3 {
1: Q3 1 L
B: Q14 B L
}
# move right until we get to the first 1 right of B
# when 0 is reached, the test number has been exhausted
state Q5 {
B: Q5 B R
X: Q5 X R
1: Q6 X L
0: Q7 0 L
}
# mark off the first 1 from the target number and repeat
# if A is reached, then the target number is exhausted
# and we need to reset and increment the test number
state Q6 {
B: Q6 B L
X: Q6 X L
1: Q5 X R
A: Q11 A R
}
# check if there are any 1s remaining; if not, the number divides perfectly
state Q7 {
X: Q7 X L
B: Q7 B L
A: H NOT_PRIME -
1: Q8 1 R
}
# go right to B
state Q8 {
X: Q8 X R
B: Q9 B R
}
# reset the test number
state Q9 {
X: Q9 1 R
0: Q10 0 L
}
# loop back to marking off the test number
state Q10 {
1: Q10 1 L
B: Q5 B R
}
# reset everything and increment the test number
state Q11 {
X: Q11 1 R
B: Q11 B R
1: Q11 1 R
0: Q12 1 -
}
# return to B and check if the numbers are equal
# move left to B
state Q12 {
1: Q12 1 L
B: Q14 B L
}
# if we reach 0, reset everything and go back to Q5
state Q13 {
1: Q14 X L
X: Q13 X R
B: Q13 B R
0: Q15 0 L
}
state Q14 {
X: Q14 X L
B: Q14 B L
1: Q13 X R
A: H PRIME -
}
# starting from all the way on the right, reset all Xs to 1s
state Q15 {
X: Q15 1 L
B: Q15 B L
1: Q16 1 R
A: Q16 A R
}
state Q16 {
1: Q16 1 R
B: Q5 B R
}
```