This book provides an introduction to computability using a series of abstract
models of computation.
After giving the historical context and the original challenges that motivated
the development of computability theory in the 1930s, we start reviewing the
traditional models of computation: Turing machines, Church’s Lambda calculus
(or λ-calculus), and the theory of recursive functions of G¨odel and Kleene.
These three models of computation are equivalent in the sense that any computation
procedure that can be expressed in one of them can also be expressed in
the others. Indeed, Church’s Thesis states that the set of computable functions
is exactly the set of functions that can be defined in these models.