a Turing machine
/ Turing: TYOOR-ing /
Picture an endless paper notebook ruled into a single long row of square cells, and a clerk who can read one cell at a time, scribble a new symbol over it, step one cell left or right, and change their mind about what to do next. That is the whole idea of a Turing machine. A finite automaton is a turnstile that only remembers which state it is in; a pushdown automaton adds a stack of plates you can only touch from the top. A Turing machine throws away those restrictions: its memory is an unbounded tape that it can both read AND write, anywhere, as many times as it likes. This single change makes it powerful enough to capture everything we mean by the word algorithm.
Concretely, a Turing machine has two parts. The finite control is just like a DFA's brain: a fixed, finite set of states, with one current state at a time. Attached to it is an infinite tape divided into cells, each holding one symbol, plus a tape head parked over one cell. At each step the machine looks at its current state and the symbol the head is reading, and a transition function tells it three things to do at once: which symbol to write into the current cell (overwriting what was there), whether to move the head one cell left or one cell right, and which state to go to next. It keeps doing this, step after step. The input string starts written on the tape; everywhere else holds a special blank symbol.
The Turing machine is deliberately the simplest, dumbest gadget that can still compute anything computable. It is slow, it shuffles a head back and forth over a tape, and nobody would build a real computer this way. Its value is not speed but precision: it gives a single, fully formal answer to the question 'what does it mean for a problem to be solvable by some algorithm?' Decades of attempts to define computation in other ways (lambda calculus, recursive functions, register machines) all turned out to capture exactly the same set of computable things, which is why the Turing machine became the standard definition of computability.
A tiny Turing machine that flips every bit of a binary input: starting at the left end, in state q it reads a 0, writes 1, moves right, stays in q; reads a 1, writes 0, moves right, stays in q; reads a blank, it halts. On the tape 1011 it leaves 0100. Reading and writing the same cells is exactly what a DFA could never do.
Read-write memory in action: the same cells are both inspected and overwritten.
A Turing machine is a mathematical model, not a real device. Calling something 'a Turing machine' says it captures computability, not that it is fast or practical; real computers are vastly faster but compute exactly the same things.