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
None filled out so far
Questions?
Arithmetic in Lambda Calculus
Section 2 of Rojas
Currying
You can think of λxy as either introducing a function that takes 2
arguments, or as introducing a function of one argument that returns a
function that picks up the second argument
i.e., λxy.Fxy = λx.(λy.Fxy)
Church numerals
0 = λfy.y
1 = λfy.fy
2 = λfy.f(fy)
etc.
n applies f n times to y
Successor function: S = λn.(λfy.f(nfy))
Example:
2 = λfy.f(fy)
S2 = (λn.(λfy.f(nfy))) (λfy.f(fy))
= λfy.f( (λfy.f(fy)) f y )
= λfy.f( (λgx.g(gx)) f y ) = λfy.f( (λg.(λx.g(gx))) f y )