Date: Thu, 19 Feb 2015 10:24:56 0500
Subject: [PATCH] more formatting

topics/_week4_fixed_point_combinator.mdwn  39 +++++++++++++++
1 file changed, 19 insertions(+), 20 deletions()
diff git a/topics/_week4_fixed_point_combinator.mdwn b/topics/_week4_fixed_point_combinator.mdwn
index 4f2691e7..14bba4c9 100644
 a/topics/_week4_fixed_point_combinator.mdwn
+++ b/topics/_week4_fixed_point_combinator.mdwn
@@ 457,23 +457,23 @@ more, nonequivalent fixedpoint combinators.)
Two of the simplest:
Θ′ ≡ (\u f. f (\n. u u f n)) (\u f. f (\n. u u f n))
Y′ ≡ \f. (\u. f (\n. u u n)) (\u. f (\n. u u n))
+ Îâ² â¡ (\u f. f (\n. u u f n)) (\u f. f (\n. u u f n))
+ Yâ² â¡ \f. (\u. f (\n. u u n)) (\u. f (\n. u u n))
Θ′
has the advantage that f (Θ′ f)
really *reduces to* Θ′ f
. Whereas f (Y′ f)
is only *convertible with* Y′ f
; that is, there's a common formula they both reduce to. For most purposes, though, either will do.
+`Îâ²` has the advantage that `f (Îâ² f)` really *reduces to* `Îâ² f`. Whereas `f (Yâ² f)` is only *convertible with* `Yâ² f`; that is, there's a common formula they both reduce to. For most purposes, though, either will do.
You may notice that both of these formulas have etaredexes inside them: why can't we simplify the two `\n. u u f n` inside Θ′
to just `u u f`? And similarly for Y′
?
+You may notice that both of these formulas have etaredexes inside them: why can't we simplify the two `\n. u u f n` inside `Îâ²` to just `u u f`? And similarly for `Yâ²`?
Indeed you can, getting the simpler:
Θ ≡ (\u f. f (u u f)) (\u f. f (u u f))
Y ≡ \f. (\u. f (u u)) (\u. f (u u))
+ Î â¡ (\u f. f (u u f)) (\u f. f (u u f))
+ Y â¡ \f. (\u. f (u u)) (\u. f (u u))
I stated the more complex formulas for the following reason: in a language whose evaluation order is *callbyvalue*, the evaluation of Θ (\self. BODY)
and `Y (\self. BODY)` will in general not terminate. But evaluation of the etaunreduced primed versions will.
+I stated the more complex formulas for the following reason: in a language whose evaluation order is *callbyvalue*, the evaluation of `Î (\self. BODY)` and `Y (\self. BODY)` will in general not terminate. But evaluation of the etaunreduced primed versions will.
Of course, if you define your `\self. BODY` stupidly, your formula will never terminate. For example, it doesn't matter what fixed point combinator you use for Ψ
in:
+Of course, if you define your `\self. BODY` stupidly, your formula will never terminate. For example, it doesn't matter what fixed point combinator you use for `Î¨` in:
Ψ (\self. \n. self n)
+ Î¨ (\self. \n. self n)
When you try to evaluate the application of that to some argument `M`, it's going to try to give you back:
@@ 491,7 +491,7 @@ You've written an infinite loop!
However, when we evaluate the application of our:
Ψ (\self (\xs. (empty? xs) 0 (succ (self (tail xs))) ))
+ Î¨ (\self (\xs. (empty? xs) 0 (succ (self (tail xs))) ))
to some list `L`, we're not going to go into an infinite evaluation loop of that sort. At each cycle, we're going to be evaluating the application of:
@@ 505,7 +505,7 @@ to *the tail* of the list we were evaluating its application to at the previous
There's a tendency for people to say "Ycombinator" to refer to fixedpoint combinators generally. We'll probably fall into that usage ourselves. Speaking correctly, though, the Ycombinator is only one of many fixedpoint combinators.
I used Ψ
above to stand in for an arbitrary fixedpoint combinator. I don't know of any broad conventions for this. But this seems a useful one.
+I used `Î¨` above to stand in for an arbitrary fixedpoint combinator. I don't know of any broad conventions for this. But this seems a useful one.
As we said, there are many other fixedpoint combinators as well. For example, Jan Willem Klop pointed out that if we define `L` to be:
@@ 635,17 +635,16 @@ sentence in which it occurs, the sentence denotes a fixed point for
the identity function. Here's a fixed point for the identity
function:
Y I
(\f. (\h. f (h h)) (\h. f (h h))) I
(\h. I (h h)) (\h. I (h h)))
(\h. (h h)) (\h. (h h)))
ω ω
&Omega

+ Y I
+ (\f. (\h. f (h h)) (\h. f (h h))) I
+ (\h. I (h h)) (\h. I (h h)))
+ (\h. (h h)) (\h. (h h)))
+ Ï Ï
+ Î©
Oh. Well! That feels right. The meaning of *This sentence is true*
in a context in which *this sentence* refers to the sentence in which
it occurs is Ω
, our prototypical infinite loop...
+it occurs is `Î©`, our prototypical infinite loop...
What about the liar paradox?
@@ 677,7 +676,7 @@ rather than recursive functions.
You should be cautious about feeling too comfortable with
these results. Thinking again of the truthteller paradox, yes,
Ω
is *a* fixed point for `I`, and perhaps it has
+`Î©` is *a* fixed point for `I`, and perhaps it has
some a privileged status among all the fixed points for `I`, being the
one delivered by Y and all (though it is not obvious why Y should have
any special status).

2.11.0