Functional Programming and Scheme
CMPSC 461
Programming Language Concepts Penn State University
Fall 2020
Is the λ-Calculus Turing complete?
2
Encoding: Boolean
Booleans
Shorthand for
λ𝑥. (λ𝑦. 𝑥)
TRUE ≜ λ𝑥 𝑦.𝑥 FALSE ≜ λ𝑥 𝑦.𝑦
Encoding of “if”? 𝑡 when 𝑏 is TRUE Goal: IF 𝑏 𝑡 𝑓 = 3𝑓 when 𝑏 is FALSE
IF ≜ λ𝑏𝑡𝑓. (𝑏𝑡𝑓)
Definition
3
Encoding: Boolean Booleans
TRUE ≜ λ𝑥 𝑦.𝑥 FALSE ≜ λ𝑥 𝑦.𝑦
Encoding of “and”? TRUE when 𝑏!, 𝑏” are both TRUE
Goal: AND 𝑏! 𝑏” = 3 FALSE otherwise
AND ≜ λ𝑏! 𝑏”. (𝑏! (𝑏” TRUE FALSE) FALSE) Check that AND TRUE FALSE = FALSE (Note 2)
Definition
4