In 1936, before a single electronic computer existed, Alan Turing had already pinned down what computable means: an endless tape of cells, a read-write head, and a rule table saying that in this state, on reading that symbol, write such a symbol, move left or right, and go to that other state. That much suffices to add, to test a palindrome, to run any program at all. The record-holding three-state machine writes exactly six 1s in 13 steps and then halts by itself, while the question of whether an arbitrary machine halts is one Turing proved no general algorithm can answer.
▸ Laying out the infinite tape · dividing cells (0 / 1 / ␣)…
▸ Placing the read/write head on the tape
▸ Loading the finite state set + rule table δ
▸ Convention: (state, read) → (write, move, new state)
Each step the machine does just 4 mechanical things: READ the cell under the head → look up the RULE by (state, symbol) → WRITE a new cell → MOVE left/right + change STATE. So simple yet enough to compute EVERYTHING computable (the Church–Turing thesis).
—
Pick a "Sample machine" to load a different rule table (bit flip · binary increment · unary add · palindrome · busy beaver · runs forever) · ⏭ step through · click a concept (tape/head/rule/HALT/Church–Turing/Halting Problem…) for details
Your browser has canvas disabled.
Head position on the tape per stephead cell
About Turing Machine
In 1936, before a single electronic computer existed, Alan Turing had already pinned down what computable means: an endless tape of cells, a read-write head, and a rule table saying that in this state, on reading that symbol, write such a symbol, move left or right, and go to that other state. That much suffices to add, to test a palindrome, to run any program at all. The record-holding three-state machine writes exactly six 1s in 13 steps and then halts by itself, while the question of whether an arbitrary machine halts is one Turing proved no general algorithm can answer.