turer
A JavaScript Turing Machine
npm install turer
Want to see pretty graphs? Log in now!
32 | downloads in the last month |
Last Published By | |
---|---|
Version | 0.2.0 last updated 4 months ago |
Repository | git://github.com/niclashoyer/turer.git (git) |
Bugs | https://github.com/niclashoyer/turer/issues |
Dependencies | None |
Turer
A JavaScript turing machine.
Installation
Download turer.js or turer.min.js on the releases page.
Using Bower
bower install turer
Using NPM
npm install turer
Usage
A Turer turing machine consists of the following parts:
Input Alphabet
Type: array
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.
Output Alphabet
Type: array
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.
Start Symbol
Type: 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.
Empty Symbol
Type: 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.
States
Type: array
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.
Start State
Type: string
The start state is the initial state of the turing machine.
Transition Function
Type: object
The transition function defines the transitions of the turing machine. The transition function is read in as a JavaScript object that has the current state as properties and an object of characters with the next state, symbol to write and direction 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).
Example
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
: ['0']
. The start symbol is >
, the empty symbol is ˽
.
We'll need two states which we name q0
and q1
which leads to the state
list as ['q0', 'q1']
. The start state will be q0
.
The instantiation with a transition function delta
will be:
var t = new Turer(['0'], ['0'], '>', '˽', ['q0','q1'], 'q0', delta);
Now all we need is the actual program delta
.
First we need to read the start symbol >
, write it back to the tape and
move to the right (we stay in state q0
):
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
. q1
is not defined in the program, which just
means that the turing machine can't transition to a next state. It'll now
emit the output
event returning the output.
The full example is located in the examples folder.