Alan Turing's machine
In 1936, before electronic computers existed, Alan Turing asked what a person following rules with pencil and paper could compute. He boiled it down to a machine: an unbounded tape of cells, a head that reads and writes one cell and moves left or right, and a finite table of rules. That's a Turing machine, and despite its simplicity it can compute anything your laptop can — just slower.
The Church–Turing thesis says that every algorithm, in any reasonable sense, can be carried out by a Turing machine. It can't be proved — "algorithm" is an informal idea — but every model anyone has proposed (lambda calculus, RAM machines, real programming languages) turns out to be equivalent. Today you'll write the simulator.
The rule table
A rule says: in this state, reading this symbol, write a symbol, move L or R, and go to a next state. The machine stops when it enters its accept or reject state. Unlike a finite automaton it can overwrite its input, go back and re-read it, and use as much tape as it likes. Empty cells hold the blank symbol, written _.
const INVERT = {
start: "q",
accept: "done",
reject: "fail",
delta: {
q: {
0: ["1", "R", "q"],
1: ["0", "R", "q"],
_: ["_", "L", "done"],
},
},
};If no rule exists for the current state and symbol, the machine rejects. That keeps tables short: list only the moves that make sense.