X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week4.mdwn;h=06581f01518648d75c077a4e18de89c1647d1a38;hp=10ab8b99c12977afda62d3573a2b6a950dd26d61;hb=276c8f5fcba4ed0b79225eece8fb3f269e98c385;hpb=76452415c955f62828e6c81370c9e39eb6d5b28f diff --git a/week4.mdwn b/week4.mdwn index 10ab8b99..06581f01 100644 --- a/week4.mdwn +++ b/week4.mdwn @@ -1,5 +1,7 @@ [[!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? @@ -7,9 +9,11 @@ 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 <~~> TX` (that's what it means to *have* a fixed point). - let W = \x.T(xx) in - let X = WW in - X = WW = (\x.T(xx))W = T(WW) = TX +
+let W = \x.T(xx) in
+let X = WW in
+X = WW = (\x.T(xx))W = T(WW) = TX
+
Q: How do you know that for any term T, YT is a fixed point of T?