Computability & Complexity
What a machine can compute in principle, and how much time and space it takes in practice — from the Turing machine to the million-dollar P versus NP question.
Computability & Complexity
Every other section of this field guide runs a rule forward: a Pendulum swings, a Wave propagates, a Markov Chain wanders. This section asks the prior question — what does it even mean to compute a rule, and what are the limits? It splits cleanly into two halves that grew up together.
- Computability — the study of what can be computed at all, given unlimited time and memory. Some problems have no algorithm, ever. This is where the Turing Machine, the Halting Problem, and Decidability live.
- Complexity — among the problems we can solve, how expensive are they? Measured in time and space as the input grows, this is the world of Big-O Notation, Complexity Classes, and the famous P versus NP divide.
The big arc
In 1936, before any electronic computer existed, Alan Turing imagined an absurdly simple machine — a tape, a head, a handful of rules — and proved two things at once: that this toy captures everything mechanically computable (the Church–Turing Thesis), and that even it cannot solve every problem (the Halting Problem). Computation has a hard ceiling, and it was found before the hardware.
Once you accept that machines are limited, the next question is cost. A problem may be solvable yet hopeless: a method that takes 2^n steps is useless at n = 100. Sorting these problems by their appetite for time and memory gives the Complexity Class hierarchy, whose central mystery — is checking an answer really easier than finding one? — is P versus NP, anchored by the NP-complete problems that stand or fall together.
The pages in this section
Computability
- Turing Machine — tape, head, rules: the definition of computable.
- Finite Automaton — a memoryless cousin that recognizes regular patterns.
- Church–Turing Thesis — why every reasonable model computes the same things.
- Halting Problem — the first proven-impossible problem.
- Decidability — the frontier between solvable and forever out of reach.
Complexity
- Big-O Notation — the language of how fast it grows.
- Complexity Class — P, NP, PSPACE, EXP — sorting problems by resources.
- P versus NP — is finding as easy as checking?
- NP-Completeness — the hardest problems in NP, joined at the hip.
Threads to the rest of the field
Computation is not sealed off. The shortest-path engine of Dijkstra's Algorithm is a complexity story about a Graph; the NP-complete problems are graph-coloring and clique puzzles. And the deepest link runs to Information Theory: Kolmogorov Complexity measures the size of the shortest program that prints a string — a computational definition of information that turns out to be undecidable. The endlessly intricate patterns of a Cellular Automaton like Conway's Game of Life are Turing-complete too: simple local rules, full computational power.
Start with the Turing Machine, or jump to the open problem that defines the field: P versus NP.