Turing machine (Alan Turing, 1936) — a mathematical model of computation consisting of an infinite tape divided into cells, a read/write head, a current state, and a transition function δ(state, symbol) → (new symbol, direction, new state). Despite its simplicity, any algorithm that can be computed at all can be computed on a Turing machine (Church–Turing thesis). The halting problem — whether a TM halts on a given input — is undecidable.