### Chapter Six Lambda
Calculus,
or
an
Attempt
to
Reinstate
Computation
in
the
Realm
of
Mathematics

THE THEORY OF COMPUTABILITY, which provided a negative answer to
Hilbert’s decision problem, went hand in hand with an attempt to reinstate
computation in mathematics. Although this attempt failed, it is significant
and worthy of attention. In many ways, it foreshadowed future developments
in the history of mathematics. This attempt rests on a language that
is considered to be Church’s greatest achievement, namely lambda
calculus.

Lambda calculus started out as a simple functional notation system. A function can be represented by a table of values, or by a curve, but also, in some cases, by a functional expression. For example, the function that, ...