11. Turing Machines
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...