bower install turer
npm install turer
A Turer turing machine consists of the following parts:
The input alphabet specifies the characters that are allowed as input to the turing machine. It is currently undefined what happens if the turing machine reads a character that is not in input alphabet.
The output alphabet specifies the characters that are allowed as output. The output of the turing machine is everything on the left side of the head that is in the output alphabet.
string (length 1)
The start symbol is a special symbol that marks the beginning of the tape. It is the first symbol that will be read at the beginning of every program.
string (length 1)
The empty symbol is a special symbol that marks an empty space on the tape. The tape has infinite empty symbols on the left and on the right side.
The states list defines which are the possible states that the turing machine is able to transition to. It is currently undefined what happens if the turing machine transitions into a state that is not in the state list.
The start state is the initial state of the turing machine.
var delta ='s1':'c':state: 's2'symbol: 'd'direction 'R'
which means that if the turing machine is in state
s1 and reads the character
c it will write
d to the tape, move to the right and transition to state
s2. The possible directions are
R (move right),
L (move left) and
N (don't move).
A simple turing machine, that reads zeros and adds one zero to the end of the input can be constructed as follows:
The turing machine has the same input and output alphabet which consists
just of the
['0']. The start symbol is
>, the empty symbol is
We'll need two states which we name
q1 which leads to the state
['q0', 'q1']. The start state will be
The instantiation with a transition function
delta will be:
var t = '0' '0' '>' '˽' 'q0''q1' 'q0' delta;
Now all we need is the actual program
First we need to read the start symbol
>, write it back to the tape and
move to the right (we stay in state
var delta ='q0':'>':state: 'q0'symbol: '>'direction: 'R'
After that we need to read in zeros and move to the right:
var delta ='q0':'>': ...'0':state: 'q0'symbol: '0'direction: 'R'
If we read an empty symbol, we need to write a zero and stop:
var delta ='q0':'>': ...'0': ...'˽':state: 'q1'symbol: '0'direction: 'R'
The turing machine will read in an empty symbol (which means we are at the
end of the input) and write a zero. After that it moves to the right and
transitions into state
q1 is not defined in the program, which just
means that the turing machine can't transition to a next state. It'll now
output event returning the output.
The full example is located in the examples folder.