A Turing machine (1936) has a finite control with states, a two-way infinite tape divided into cells, and a head that reads/writes one cell and moves left/right per step. A function is computable iff some TM, given the input on its tape, halts with the output. Church–Turing thesis: this captures the intuitive notion of "effectively computable."

Halting problem: given $(M, w)$, does $M$ halt on input $w$? Turing proved this is undecidable — no algorithm decides it for all inputs. Diagonal argument: suppose $H$ decides it; build $D(M) := $ "run $H(M, M)$ and do the opposite"; consider $D(D)$ — contradiction.

Gödel's incompleteness theorems (1931):

1. Any consistent, effectively axiomatized theory containing enough arithmetic (Peano +) is incomplete: there's a true statement it cannot prove.
2. Such a theory cannot prove its own consistency.

Proof idea: arithmetize syntax (Gödel numbering) and build a self-referential sentence "this sentence is not provable in $T$."

Interactive: a Turing machine incrementing a binary number