What computers can do in principle: simple machines, the Turing machine, and problems no program can ever solve. Press play on any sketch to watch it happen.
1 Finite automata
A finite automaton is the simplest model of a computer. It reads input one symbol at a time and moves between a fixed set of states. Regular expressions and many protocols are built on this idea.
State: the only memory the machine has.
Transition: a rule: in this state, on this symbol, go there.
Accepting state: if input ends here, the string is accepted.
Limit: it has no counter or stack, so it cannot match balanced brackets.
State diagram
1/5 This machine accepts binary strings with an even number of 1s. It starts in Even.
Machine
Memory
Recognises
Finite automaton
None beyond state
Regular languages
Pushdown automaton
A stack
Context-free languages
Turing machine
An unlimited tape
Anything computable
Rule of thumb: If a problem needs unlimited memory of the past, a finite automaton cannot solve it.
2 The Turing machine
A Turing machine is a head reading and writing symbols on an unlimited tape, following a table of rules. It sounds trivial, yet it can compute anything your laptop can, given enough time and tape.
Tape: unlimited memory divided into cells.
Head: reads a cell, writes a cell, moves left or right.
Rule table: in this state, on this symbol: write, move, change state.
Church-Turing thesis: anything that can be computed at all can be computed by a Turing machine.
Machine diagram
1/5 The head starts on the first cell. Its rule: flip the bit, then move right.
Rule of thumb: Turing complete means a language or machine can compute anything a Turing machine can.
3 The limits: P, NP and halting
Some problems are easy, some are easy to check but seemingly hard to solve, and some cannot be solved by any program at all. Knowing which kind you face saves you from chasing the impossible.
P: problems a computer can solve quickly, like sorting.
NP: problems where a proposed answer can be checked quickly, like Sudoku.
P vs NP: nobody has proved whether these two classes are the same.
NP-complete: the hardest problems in NP. Use approximations for these.
Undecidable: no algorithm can solve these for every input, as with the halting problem.
Proof by contradiction
1/5 Suppose someone writes H, a perfect program that predicts whether any program halts.
Rule of thumb: If your problem is NP-complete, stop seeking a perfect fast solution and look for a good-enough one.
