X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week4.mdwn;h=58d6bc38204bd3bcbf4afabe6d9c4306b82735de;hp=bd3d8e5c6e0deac02d0954379f67b4d393ab2bc8;hb=HEAD;hpb=ee659ed0921805be0db5de5658290b6dc1222eee diff --git a/week4.mdwn b/week4.mdwn deleted file mode 100644 index bd3d8e5c..00000000 --- a/week4.mdwn +++ /dev/null @@ -1,61 +0,0 @@ -[[!toc]] - -#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 <~~> -TX` (that's what it means to *have* a fixed point). - -
let L = \x. T (x x) in
-let X = L L in
-X ≡ L L ≡ (\x. T (x x)) L ~~> T (L L) ≡ T X
-
-
-Please slow down and make sure that you understand what justified each
-of the equalities in the last line.
-
-#Q: How do you know that for any term `T`, `Y T` is a fixed point of `T`?#
-
-A: Note that in the proof given in the previous answer, we chose `T`
-and then set `X = L L = (\x. T (x x)) (\x. T (x x))`. If we abstract over
-`T`, we get the Y combinator, `\T. (\x. T (x x)) (\x. T (x x))`. No matter
-what argument `T` we feed `Y`, it returns some `X` that is a fixed point
-of `T`, by the reasoning in the previous answer.
-
-#Q: So if every term has a fixed point, even `Y` has fixed point.#
-
-A: Right:
-
-let Y = \T. (\x. T (x x)) (\x. T (x x)) in
-Y Y ≡ \T. (\x. T (x x)) (\x. T (x x)) Y
-~~> (\x. Y (x x)) (\x. Y (x x))
-~~> Y ((\x. Y (x x)) (\x. Y (x x)))
-~~> Y (Y ((\x. Y (x x)) (\x. Y (x x))))
-~~> Y (Y (Y (...(Y (Y Y))...)))
-
-
-#Q: Ouch! Stop hurting my brain.#
-
-A: Is that a question?
-
-Let's come at it from the direction of arithmetic. Recall that we
-claimed that even `succ`---the function that added one to any
-number---had a fixed point. How could there be an X such that X = X+1?
-That would imply that
-
- X <~~> succ X <~~> succ (succ X) <~~> succ (succ (succ (X))) <~~> succ (... (succ X)...)
-
-In other words, the fixed point of `succ` is a term that is its own
-successor. Let's just check that `X = succ X`:
-
-let succ = \n s z. s (n s z) in
-let X = (\x. succ (x x)) (\x. succ (x x)) in
-succ X
-≡ succ ( (\x. succ (x x)) (\x. succ (x x)) )
-~~> succ (succ ( (\x. succ (x x)) (\x. succ (x x))))
-≡ succ (succ X)
-
-
-You should see the close similarity with `Y Y` here.
-
-