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.