What is the result of one step of β-reduction applied to (λx. λy. x) z?
Aλy. z
Bλx. z
Cz
Dλz. z
β-reduction substitutes the argument z for every free occurrence of x in the body λy. x, yielding λy. z. The outer lambda abstraction is consumed by the application, but the inner abstraction λy remains because only one argument is being applied. The variable y is bound in the result and x no longer appears.
Question 2 True / False
In lambda calculus, the number 3 is a built-in constant, just as it is in most programming languages.
TTrue
FFalse
Answer: False
Lambda calculus has no built-in data types — no numbers, booleans, pairs, or lists. Natural numbers must be encoded as functions. The Church numeral for 3 is λf. λx. f (f (f x)), representing 'apply f three times to x.' This encoding shows that all of computation can emerge from pure function abstraction and application, with no primitive constants required.
Question 3 Short Answer
What is β-reduction, and in what sense does it model computation?
Think about your answer, then reveal below.
Model answer: β-reduction is the rule (λx.M) N → M[x := N]: applying a lambda abstraction to an argument substitutes that argument for every free occurrence of the bound variable in the body. It models computation because each reduction step corresponds to one unit of work — evaluating a function call. A sequence of β-reductions transforms a lambda term until no further reductions are possible (normal form), representing the final computed value.
This single rewrite rule is the entire computational engine of lambda calculus. All of arithmetic, logic, and recursion are encoded so that evaluating them reduces to repeated application of β-reduction. Turing-completeness means every computable function can be expressed as a lambda term that β-reduces to the correct output — demonstrating that function application alone is sufficient for all of computation.