The essential usefullness of the lambda calculus is that it is
wonderfully suited to representing functions. In fact, the untyped
-lambda calculus is Turing Complete [[!wikipedia Turing Completeness]]:
+lambda calculus is Turing Complete (see [[!wikipedia Turing Completeness]]):
all (recursively computable) functions can be represented by lambda
terms. (As we'll see, much of the fun will be in unpacking the word
"represented".)
we've become acquainted with. We'll start with the `if ... then
... else...` construction.
- if x then y else z
+ if M then N else L
-For a boolean expression `x`, this complex expression evaluates to `y`
-if `x` evaluates to `'true`, and to `z` if `x` evaluations to `'false.
+For a boolean expression `M`, this complex expression evaluates to `N`
+if `M` evaluates to `'true`, and to `L` if `M` evaluations to `'false.
So in order to simulate and `if` clause in the lambda calculus, we
need to settle on a way to represent `'true` and `'false`.