Question

15. Give an exa.mple of a. λ calculus term that contains one free varia.ble and one bound varia.ble.

16. Give an example of a λ calculus term that never reduces to a value, but instead grows without bound. Show at least two steps of evaluation to illustrate how this example works.

Answer 1

A λ calculus term with a bound and a free variable is λx.xy, with 'x' being bound and 'y' being free. The Omega combinator (λx.xx)(λx.xx) exemplifies a term that endlessly grows without reducing to a value.

Step-by-step explanation:

Examples of λ Calculus Terms

An example of a λ calculus term containing one free variable and one bound variable is λx.xy. Here, 'x' is the bound variable because it is declared within the scope of the λ operator, and 'y' is the free variable because it is not bound within the term.

An example of a λ calculus term that grows without bound is the λ term known as the Omega combinator, represented as (λx.xx)(λx.xx). To illustrate its behavior:

1. Take the λ term (λx.xx)(λx.xx) and apply the left side to the right side.
2. The term reduces to (λx.xx)(λx.xx) again, essentially replicating itself ad infinitum without ever producing a value.

The example clearly demonstrates a term that, upon evaluation, enters an infinite loop of self-application without simplifying to a value.