Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Turing Machine Interpreter in JavaScript
/**
* 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)
}
// 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]
// 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]
// 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]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.