Comprehensive, but emphasizing material since 2nd hour exam (e.g., diagonalization,
reduction, Rice’s theorem, computation histories, PCP, recursion theorem,
lambda calculus, etc.)
Designed for 2 hours, you’ll have 2 1/2 +
Rules and format otherwise similar to hour exams
Donuts and cider
SOFIs
Helpful to me in planning future offerings of this course
Please fill out
2 filled out so far
Questions?
Logic in Lambda Calculus
Section 3 of Rojas
Need to see the various expressions (aka “combinators”) in action…
Combinator = lambda expression with no free variables, typically a function definition
Examples
T = λxy.x, F = λxy.y
Tab = (λxy.x) a b
→ a
(T (λx.Fx) (λy.Gy)) a
→ (λx.Fx) a
→ F a
(F (λx.Fx) (λy.Gy)) a
→ (λy.Gy) a
→ G a
Typical use of these ideas would be to apply some expression that eventually evaluates
to T or F to two functions — lambda calculus’s version of
“if-then-else”