1 1. Find a fixed point `X` for the succ function:
8 So `succ(HH) <~~> succ(succ(HH))`.
10 2. Prove that `add 1 X <~~> X`:
12 add 1 X == (\mn.m succ n) 1 X
19 add 2 X == (\mn.m succ n) 2 X
24 So `add n X <~~> X` for all (finite) natural numbers `n`.
27 Solutions to the factorial problem and the mutual recursion problem:
30 let false = \y n. n in
31 let pair = \a b. \v. v a b in
32 let fst = \a b. a in ; aka true
33 let snd = \a b. b in ; aka false
35 let succ = \n s z. s (n s z) in
36 let zero? = \n. n (\p. false) true in
37 let pred = \n. n (\p. p (\a b. pair (succ a) a)) (pair zero zero) snd in
38 let add = \l r. r succ l in
39 let mult = \l r. r (add l) 0 in
40 let Y = \h. (\u. h (u u)) (\u. h (u u)) in
42 let fact = Y (\f n . zero? n 1 (mult n (f (pred n)))) in
44 let Y1 = \f g . (\u v . f(u u v)(v v u))
45 (\u v . f(u u v)(v v u))
46 (\v u . g(v v u)(u u v)) in
48 let Y2 = \f g . Y1 g f in
50 let proto_even = \e o n. zero? n true (o (pred n)) in
51 let proto_odd = \o e n. zero? n false (e (pred n)) in
53 let even = Y1 proto_even proto_odd in
54 let odd = Y2 proto_even proto_odd in