turer

A JavaScript Turing Machine

Turer

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