- Final
- Tuesday, May 10, 8:00 AM
- In our classroom
- 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
- 2 filled out so far
- Please fill out more
- What does a 1-item list look like for problem set?
- An ordered pair with 0 in its second element
- An ordered pair with 0 in its second element
- Rojas section 4
- Y and fixed points
- Y = λf.(λx.f(xx))(λx.f(xx))
- Y R = (λf.(λx.f(xx))(λx.f(xx))) R
- → (λx.R(xx))(λx.R(xx))
- → R( (λx.R(xx)) (λx.R(xx)) )
- = R( (λf.(λx.f(xx)) (λx.f(xx))) R ) {abstraction}
- = R (YR)
- “Unreduction” aka abstraction
- fx = (λa.fa)x
- Evidently YR is a fixed point for R
- Another example: Null = return 0 by counting down to it
- Null(x) = x if x = 0; = Null( P(x) ) otherwise
- e.g., Null(2) = Null( P(2) ) = Null( 1 ) = Null( P(1) ) = Null( 0 ) = 0
- As a lambda expression: N = λnx.(Zx)x(n(Px))
- Y N 2
- = N (YN) 2
- = (YN) (P2) = (YN) 1
- = N (YN) 1
- = (YN) 0
- = N (YN) 0
- = 0