Recursive functions, partial and total functions, the Church-Turing thesis, formal models of computation, and equivalence of models.
Computability theory studies which functions can be calculated by a precise mechanical procedure, and it gives a mathematical meaning to the informal idea of an effective algorithm.
The chapter begins with recursive functions, where computation is described by basic initial functions together with operations that generate more complex functions, such as composition, primitive recursion, and minimization.
Partial and total functions are then distinguished, since some computations produce an output for every input while others may fail to halt or remain undefined for some inputs.
The Church-Turing thesis is introduced as the claim that all reasonable formal models of effective computation capture the same intuitive class of computable functions.
The chapter then studies formal models of computation, including recursive definitions, lambda calculus, register machines, and Turing machines, each of which gives a different but equivalent way to describe computation.
Finally, the equivalence of these models is examined, showing that the notion of computability is robust and does not depend on the particular formalism chosen.