A simple way to simulate a turing machine.
tm-interpreter <path-to-tm> [OPTIONS]
In a file. For example:
A Turing machine that accepts if the input is divisible by 3
alphabet: 0123456789
tape: 14526
tape_offset: 0
start_state: S0
accepted_states: S0
rule: S0 0369 none r S0
rule: S0 147 none r S1
rule: S0 258 none r S2
rule: S1 0369 none r S1
rule: S1 147 none r S2
rule: S1 258 none r S0
rule: S2 0369 none r S2
rule: S2 147 none r S0
rule: S2 258 none r S1
Let's break that down:
The basic structure is: keyword: <values>. Any line that does not match this will be ignored.
Sets the alphabet to be used, here all possible characters are digits.
alphabet: 0123456789
Sets the input word.
tape: 14526
Defines where the tape starts. An offset of 3 would shift the tape 3 characters to the LEFT(for example if you want to write an oracle to the left of the head, the offset yould be the length of that oracle)
tape_offset: 0
To control a turing machine a state pattern is used.
Here we do not need a complete definition of all possible states, as a starting state and all state transitions (I will refer to them as rules) are sufficient.
A state is unambiguously defined by its name.
In which state the TM starts.
starting_state: S0
Defines which states are accepting end states. If there are multiple ones they are separated by a space like so S0 S1.
accepted_states: S0
A rule consists of 5 things.
* The state the rule is 'active' in
* On what it reads
* What does it write
* Where it moves after
* The next State
The first 2 are conditions to be met, the last 3 are actions that are taken if those conditions are met.
Generally speaking it is: rule: <in-state> <read-condition> <write-action> <head_movement> <next-state>, where:
states are just a String
<read-condition> is one of the following:
* any -> if any character is written on the tape at the heads position
* empty -> if there is character at the head
* 12345 -> if this contains the character at the head (this would rule would apply for [1-5])
<write-action> is one of:
* none -> leave it as is
* delete -> erase the current char
* a (a single char) -> write a
<movement> is any singular char, l moves to left, r to right, the rest stays in place.
rule: S1 258 none r S0
^^^^^^ if in state S1 and read 2, 5 or 8
^^^^^^^^^^ then leave the tape as is, move to the right and switch to state S0