Turing Machine Interpreter in JavaScript

turing-machine-interpreter.js

/**
 * Turing Machine Interpreter
 *
 * Features:
 *  - Infinite tape, both ways
 *  - Uses JS values, anything that matches ==, is a valid symbol
 *
 * Definition:
 *  - States (Q): { integer, halt }
 *  - Input symbols read/write (Σ): any integer or string
 *  - Tape alphabet symbols (Γ): Σ + b
 *  - Blank symbol (b): null
 *  - Final state (F): halt
 *
 * @typedef {Array<Array<{read, write, move, next }>>} Tape
 *
 * @param {Tape} delta
 * @param {Array} tape
 * @returns {Tape}
 */
module.exports = function turingMachine(delta, tape) {
  if (delta.length < 1 || tape.length < 1) return trim(tape)

  let head = 0
  let state = 0
  let shift = 0

  while (true) {
    if (head < 0) tape.unshift(null), shift++

    const rule = delta[state].find(rule => rule.read == tape[head + shift])
    if (!rule) return trim(tape)

    const { write, move, next } = rule

    tape[head + shift] = write
    head += move
    state = next

    if (state === 'halt') return trim(tape)
  }
}

/**
 * Trim leading and trailing blanks
 * @param {Tape} tape
 * @return {Tape}
 */
function trim(tape) {
  const start = tape.findIndex(v => v != null)
  const end =
    tape.length -
    tape
      .slice()
      .reverse()
      .findIndex(v => v != null)

  return tape.slice(start, end)
}

usage-example-0.js

// Bitwise NOT function

const turingMachine = require('./turing-machine-interpreter')

const _ = null
const tape = [1, 0, 1]
const delta = [
  [
    { read: _, write: _, move: 0, next: 'halt' },
    { read: 0, write: 1, move: 1, next: 0 },
    { read: 1, write: 0, move: 1, next: 0 }
  ]
]

turingMachine(delta, tape) // => [0, 1, 0]

usage-example-1.js

// Subtraction, unary
//  decimal (base-10): 5     - 2  = 3
//  unary   (base-1):  11111 - 11 = 111

const turingMachine = require('./turing-machine-interpreter')

const _ = null
const tape = [1, 1, 1, 1, 1, _, 1, 1]
const delta = [
  [
    { read: _, write: _, move: 1, next: 1 },
    { read: 0, write: 0, move: 1, next: 0 },
    { read: 1, write: 1, move: 1, next: 0 }
  ],
  [
    { read: _, write: _, move: -1, next: 2 },
    { read: 0, write: 0, move: 1, next: 1 },
    { read: 1, write: 1, move: 1, next: 1 }
  ],
  [
    { read: _, write: _, move: 1, next: 4 },
    { read: 0, write: 0, move: -1, next: 2 },
    { read: 1, write: 0, move: -1, next: 3 }
  ],
  [
    { read: _, write: _, move: -1, next: 7 },
    { read: 0, write: 0, move: -1, next: 3 },
    { read: 1, write: 1, move: -1, next: 3 }
  ],
  [
    { read: _, write: _, move: -1, next: 5 },
    { read: 0, write: 0, move: 1, next: 4 },
    { read: 1, write: 1, move: 1, next: 4 }
  ],
  [
    { read: _, write: _, move: -1, next: 6 },
    { read: 0, write: _, move: -1, next: 5 },
    { read: 1, write: 1, move: -1, next: 5 }
  ],
  [
    { read: _, write: _, move: 1, next: 'halt' },
    { read: 0, write: _, move: -1, next: 6 },
    { read: 1, write: 1, move: -1, next: 6 }
  ],
  [
    { read: _, write: _, move: 1, next: 'halt' },
    { read: 0, write: 0, move: -1, next: 7 },
    { read: 1, write: 0, move: 1, next: 0 }
  ]
]

turingMachine(delta, tape) // => [1, 1, 1]

usage-example-2.js

// Proof of an Infinite tape both ways
//  prepends two zeros

const turingMachine = require('./turing-machine-interpreter')

const _ = null
const tape = [1, 0, 1]
const delta = [
  [
    { read: _, write: _, move: -1, next: 1 },
    { read: 0, write: 0, move: -1, next: 1 },
    { read: 1, write: 1, move: -1, next: 1 }
  ],
  [
    { read: _, write: 0, move: -1, next: 2 }
  ],
  [
    { read: _, write: 0, move: -1, next: 'halt' }
  ]
]

turingMachine(delta, tape) // => [0, 0, 1, 0, 1]