A JavaScript Turing Machine

A JavaScript turing machine.

Download turer.js or turer.min.js on the releases page.

`bower install turer`

`npm install turer`

A Turer turing machine consists of the following parts:

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.

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.

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.

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.

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.

Type: `string`

The start state is the initial state of the turing machine.

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).

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 = '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.