Turing Machine

A simplistic simulation of turing machines written in TypeScript. Tested on NodeJS v8, although eralier versions should word as well.

Installation

The module is available through npm as:

npm install --save turing-machine

Usage

We can use pre-built machines.

import { EraseMachine } from 'turing-machine/pre-built';
 
// In this case, the erase machine requires the domain of our language
const eraseMachine = new EraseMachine( [ 'a', 'b' ] );
 
const eraseTape = Tape.fromString( 'aaabb', 2 );
 
eraseMachine.diagnose( eraseTape );

Or we can create our own custom machines.

import { TuringMachine, Tape, TapeMovement } from 'turing-machine';
 
// Let's create a machine that accepts a's and b's and removes all the a's.
const machine = new TuringMachine();
 
const stateInitial = machine.addState( '0' );
 
const stateConsume = machine.addState( '1' );
 
// We can even compose machines!
const stateErase = machine.addState( '2', new EraseMachine( [ 'a', 'b' ] ) );
 
const stateRollback = machine.addState( '3' );
 
const stateFinal = machine.addState( '4' );
 
// After we have defined the states, we can add transitions between them
stateInitial.addTransition( stateConsume, [ null, null, TapeMovement.Right ] );
stateConsume.addTransition( stateErase, [ 'a', 'a', TapeMovement.Center ] );
stateConsume.addTransition( stateConsume, [ 'b', 'b', TapeMovement.Right ] );
stateConsume.addTransition( stateRollback, [ null, null, TapeMovement.Left ] );
stateErase.addTransition( stateConsume );
stateRollback.addTransition( stateRollback, [ 'b', 'b', TapeMovement.Left ] );
stateRollback.addTransition( stateFinal, [ null, null, TapeMovement.Center ] );
 
machine.setInitialState( stateInitial );
 
machine.setFinalState( stateFinal );
 
// Automatically enables debug mode and prints the productions used and the result
machine.diagnose( 'bbaabab' );
// Otherwise, just call the method run and get the final Tape state
machine.run( 'bbaabab' );
 
// Additionaly, it's also possible to generate the Dot representation of our graph
machine.toDot();
// Or save it directly to a file
machine.toDotFile( 'graph.dot' );