Turing Machine

Introduction

The Turing Machine is a computational model first presented by Alan Turing in his 1936 paper on Computability. It is an incredibly simple model. The machine consists of an infinitely long tape and a tape head. The tape consists of boxes known as squares. Each square contains a symbol which is either B (representing a BLANK square) or 1 (representing a square with content and that content being the natural number "1"). The tape head can move along the tape. That is, it can move left or right. The square currently being scanned by the tape head is known as the scanned square, and the symbol of the scanned square is referred to as the scanned symbol. The machine can also print a new symbol into a scanned square.

With that being said, it is important to note that there are only three operations in a Turing Machine: Move Left, Move Right, and Print.

Once the input is loaded into the Turing Machine, its tape is configured to represent such. For instance, given a function f of two inputs x1 and x2, f(3,2) would yield the following initial tape configuration: B 1 1 1 B 1 1 B. To the left of the leftmost B, there are infinitely many Bs. The same applies to the right of the rightmost B. The inputs are represented in a sequence of 1s. For instance, 3 = 1 1 1 and 2 = 1 1. All inputs are separated by a blank square.

The behavior of the machine is dependent on the quadruples provided. A quadruple is a collection of four items in the format: Q1 S A Q2 where Q1 is the machine's current state, S is the scanned symbol, A is the action to perform, and Q2 is the machine's next state once the quadruple is executed. For example, 1 B R 2 is a valid quadruple. It is read as, "Whilst in state one reading a blank, move right and switch to state two." A finite sequence of quadruples concoct a program in a Turing Machine. Furthermore, two or more quadruples cannot have the same first two values. For instance, 4 B R 5 and 4 B L 6 are two invalid quadruples because the machine would not know which quadruple to execute when in state four reading a blank. However, 3 1 R 3 and 3 B L 4 are valid quadruples for the simple reason being that one executes when in state three reading a one and the other when reading a blank.

Note: A square cannot be blank and one, simultaneously.

Lastly, the machine runs as long as it can find a quadruple to execute. For example, if the machine is in state three reading a blank and it finds a quadruple that begins with 3 B, it will execute that quadruple. However, if it cannot find such a quadruple, the machine will halt. A correctly constructed Turing Machine will always halt with the tape head scanning the leftmost B in the tape. To the right of the tape head will be the sequence of ones representing the output. For instance, given a function g(x1, x2) = x1 + x2, g(3,2) = 5 and the final tape configuration will be B 1 1 1 1 1 B. As previously stated, there are infinitely many Bs to the left and right of the leftmost and rightmost Bs, respectively.

Disclaimer: This is just a brief summary of Turing Machines with respect to functions. There is a lot more one could learn about this model, and I highly recommend doing so, independently.

Usage

Install via NPM

npm install grumle-turing --save

import { TuringMachine, Quadruple, Result } from 'grumle-turing';

// Create the quadruples
const quadruples: Quadruple[] = [];
quadruples.push(new Quadruple(1, 'B', 'R', 2));
quadruples.push(new Quadruple(2, '1', 'R', 2));
// etc...

// Expects an array of inputs
const inputs: number[] = [3, 2];

// Instantiate the Turing Machine
const turing: TuringMachine = new TuringMachine(quadruples, inputs);

// Use step() to walk through the execution
const result: Result = turing.step();

/* OR */

// Use start() to execute the entire program
const result: Result = turing.start();

// Access the machine's output in decimal format
// (Only accessible once the entire machine has halted)
console.log(result.output);

// Access the tape's configuration after every step()
// or once the machine halts
console.log(result.tape);

// Access the machine's current state after every step()
// or once the machine halts
console.log(result.state);

Contribute

Once you've forked and cloned the repository, and have created your own development branch, install the dependencies.

npm install

Compile the code using the build script.

npm run build

Testing

It is highly encouraged to write unit tests to ensure the functionality of your changes. Jest is the testing framework used in this project. Store all of your test suites in the tests folder. Run your tests using the test script.

npm run test

Also, it is imperative that any changes made do not break the existing code. Consequently, all pull requests must pass Travis CI/CD tests.

Developer:
Treasure Muchenagumbo

License:
MIT

Version:
1.0.3