X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week4.mdwn;h=2fa501c6bf204324cf38fbe5f9d5fd0c2ad3f69f;hp=c002a4713d83200ced68f2bd7914d3a1520767ab;hb=8eb66bfd3d6eec21e1a4d31a244200e80e73e888;hpb=99d1d57f9a1cf2447938744849531a5c68aee7b1 diff --git a/week4.mdwn b/week4.mdwn index c002a471..2fa501c6 100644 --- a/week4.mdwn +++ b/week4.mdwn @@ -1,9 +1,6 @@ [[!toc]] -#These notes return to the topic of fixed point combiantors for one more return to the topic of fixed point combinators# - -#Q: How do you know that every term in the untyped lambda calculus has -a fixed point?# +#Q: How do you know that every term in the untyped lambda calculus has a fixed point?# A: That's easy: let `T` be an arbitrary term in the lambda calculus. If `T` has a fixed point, then there exists some `X` such that `X <~~> @@ -161,3 +158,16 @@ A 2 x is to A 1 x as multiplication is to addition; A 3 x is to A 2 x as exponentiation is to multiplication--- so A 4 x is to A 3 x as hyper-exponentiation is to exponentiation... +#Q. What other questions should I be asking?# + +* What is it about the variant fixed-point combinators that makes + them compatible with a call-by-value evaluation strategy? + +* How do you know that the Ackerman function can't be computed + using primitive recursion techniques? + +* What *exactly* is primitive recursion? + +* I hear that `Y` delivers the *least* fixed point. Least + according to what ordering? How do you know it's least? + Is leastness important?