Part 2 · 1 chapters · ~8 min

Turing Machines

Turing's 1936 model, tape, head and transition table, a binary increment machine traced, multi-tape and nondeterministic variants, the universal machine and the stored-program computer, the Church-Turing thesis, lambda calculus as an equivalent model, and accidental Turing completeness.

4

A machine that adds one

code
// binary increment: move to the rightmost bit, then carry left
const rules = {
  'right,0': ['0', +1, 'right'], 'right,1': ['1', +1, 'right'], 'right,_': ['_', -1, 'carry'],
  'carry,1': ['0', -1, 'carry'], 'carry,0': ['1', 0, 'done'],   'carry,_': ['1', 0, 'done'],
};
function run(input: string) {
  const tape = new Map([...input].map((c, i) => [i, c])); let pos = 0, q = 'right';
  while (q !== 'done') { const [w, mv, nq] = rules[`${q},${tape.get(pos) ?? '_'}`]; tape.set(pos, w); pos += mv; q = nq; }
  return [...tape.entries()].sort((a, b) => a[0] - b[0]).map(e => e[1]).join('').replace(/_/g, '');
}
run('1011')   // '1100'   (11 + 1 = 12)
run('111')    // '1000'

Accidental Turing completeness matters in practice: if your configuration language, template system or rules engine is Turing complete, you cannot in general predict whether a configuration terminates (next part), so production systems put time and step limits on them.

A TURING MACHINE
a finite controller with an infinite tape
tape… _ 1 0 1 1 _ …headreads, writes, moves L or Rcontrollerfinite state tablehaltaccept or reject
swipe the figure sideways, or tap expand for full screen
1/4
the parts
A tape of cells, a head that reads and writes one cell and moves left or right, and a finite table of rules: in state q reading s, write s', move, go to state q'.
tape + head + rule tableTuring, 1936