# Activity Goals

The goals of this activity are:
1. To relate the Lambda calculus to the Turing Machine abstraction, and to describe their equivalence
2. To derive boolean expressions using the Lambda Calculus and beta-reductions

Feel free to visit these resources for supplemental background reading material.

# The Activity

## Model 1: Lambda Calculus

λx.x

### Questions

1. The first statement defines a parameter called x and returns x. What does (λx.x)y do?

## Model 2: Fundamental Constructs with the Lambda Calculus

true = λxy.x
false = λxy.y
Here, x and y are bound variables. Variables that appear in the lambda expression that are not defined are referred to as free variables.

### Questions

1. In your own words, what does it mean for something to be true in the lambda calculus, when choosing between two alternative parameters?

## Model 3: Boolean Constructions with the Lambda Calculus

not x = λx.x false true
not x = (λx.x false true) true
These expansions are called currying. Now, substitute true for x:
not x = (true false true)
Substitute λxy.x for true:
not x = (λxy.x false true)
Given two parameters, select the first one, where the parameters are x = true, y = false: not true = false

equals(x, y) = λxy.???
Apply one of the parameters to see if it expands to true or false:
equals(x, y) = λxy.x ???
If x is true, then they are equal if y is true, and false otherwise. In other words, the value of y is the result.
equals(x, y) = λxy.xy ???
Otherwise, x is false, and so the result is true if y is also false; in other words, the result is not y.
equals(x, y) = λxy.xy not y
Which we can expand from our prior definition: equals(x, y) = λxy.xy y false true
Which we expand again to substitute our definitions for true and false: equals(x, y) = λxy.xy y λxy.y λxy.x
These substitutions are called beta-reductions.

and(x, y) = y when x = true, and false if x = false.
λxy.xy false
Note that when x = true, this corresponds to choosing the first of the two following parameters (y and false) to resolve the boolean expression to y. When x = false, we choose the second of the two following parameters, and obtain false.
Finally, substitute λab.b for false. λxy.xy λab.b

### Questions

1. Verify the behavior of not false using the lambda expression above.
2. All boolean expressions can be constructed using the NAND operator. What is the lambda expression for NAND, which is (NOT AND x y)?
3. Derive the boolean expression for A OR B, given that A OR B is true when A is true, and B otherwise.
4. Draw a truth table for the XOR operator. What is the result when A is true? How about when A is false? Derive the lambda expression for XOR.
5. Draw a truth table for the equals operator. What is its boolean expression? Derive its lambda expression.

## Submission

I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.