Turing machine definitions, computation traces, universal machines, the halting problem, and undecidability results.
Turing machines provide a simple formal model of computation, where an algorithm is represented by a finite set of instructions acting on a tape, a head position, and an internal state.
The chapter begins with machine definitions, including the tape alphabet, states, transition function, starting configuration, accepting and rejecting states, and the precise meaning of one step of computation.
Computation traces are then introduced to describe the full sequence of configurations produced by a machine on a given input, making it possible to reason carefully about halting, output, and nontermination.
Universal machines are studied next, showing that a single Turing machine can simulate any other Turing machine when given a suitable description of that machine and its input.
The halting problem is then presented as the central undecidable problem, where one asks whether a given machine eventually halts on a given input.
Finally, the chapter develops further undecidability results by reducing the halting problem to other decision problems, showing that many natural questions about programs and formal systems cannot be solved by any algorithm.