A Turing machine is an abstract model of computation: an infinite tape of symbols, a read/write head, and a finite set of states with transition rules. Each step: read symbol → write symbol, move left/right, change state.
Turing's 1936 proof shows no algorithm can decide, for an arbitrary program P and input I, whether P(I) halts. The proof is by contradiction using diagonalization: assume HALT(P,I) exists; build PARADOX that halts iff HALT(PARADOX, PARADOX) says it doesn't — contradiction. This is the same diagonal argument Cantor used to show |ℝ| > |ℕ|.
The Busy Beaver function Σ(n) = maximum 1s written by any halting n-state machine on blank tape. Σ grows faster than any computable function. Σ(5) = 4098 (proven 2024), Σ(6) is unknown and likely unknowable.