X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week3.mdwn;h=a55659cb97b6e0f12616770115fc8680eb2ed821;hp=27bdc53e3c718c3c3db7230d0fd4aadc98470e79;hb=cd20a0a226f35177c21ef48bcabfc59316e3e489;hpb=3046bff4d37b7a7424f414633706ac6f7cfc3d59

diff --git a/week3.mdwn b/week3.mdwn
index 27bdc53e..a55659cb 100644
--- a/week3.mdwn
+++ b/week3.mdwn
@@ -211,7 +211,8 @@ Instead of writing out a long formula twice, we could write:
 
 and the initial `(\x. x x)` is just what we earlier called the <code>&omega;</code> combinator (lower-case omega, not the non-terminating <code>&Omega;</code>). So the self-application of `H` can be written:
 
-<pre><code>&omega; (\h \lst. (isempty lst) zero (add one ((h h) (extract-tail lst))))</code></pre>
+<pre><code>&omega; (\h \lst. (isempty lst) zero (add one ((h h) (extract-tail lst))))
+</code></pre>
 
 and this will indeed implement the recursive function we couldn't earlier figure out how to define.
 
@@ -493,16 +494,16 @@ As any functional programmer quickly learns, writing a recursive
 function divides into two tasks: figuring out how to handle the
 recursive case, and remembering to insert a base case.  The
 interesting and enjoyable part is figuring out the recursive pattern,
-but leaving out the base case creates a program that runs forever.
-For instance, consider computing a factorial: `n!` is `n * (n-1) *
-(n-2) * ... * 1`.  The recursive case says that the factorial of a
-number `n` is `n` times the factorial of `n-1`.  But if we leave out
-the base case, we get
+but the base case cannot be ignored, since leaving out the base case
+creates a program that runs forever.  For instance, consider computing
+a factorial: `n!` is `n * (n-1) * (n-2) * ... * 1`.  The recursive
+case says that the factorial of a number `n` is `n` times the
+factorial of `n-1`.  But if we leave out the base case, we get
 
     3! = 3 * 2! = 3 * 2 * 1! = 3 * 2 * 1 * 0! = 3 * 2 * 1 * 0 * -1! ...
 
-That's why it's crucial to declare that 0! = 1, and the recursive rule
-does not apply.  In our terms,
+That's why it's crucial to declare that 0! = 1, in which case the
+recursive rule does not apply.  In our terms,
 
     fac = Y (\fac n. iszero n 1 (fac (predecessor n)))
 
@@ -514,12 +515,12 @@ case: the truth-teller paradox (and related paradoxes).
 
 (1)    This sentence is true.
 
-If we assume that "this sentence" can refer to (1), then the
-proposition expressed by (1) will be true just in case the thing
-referred to by "this sentence is true".  Thus (1) will be true just in
-case (1) is true, and (1) is true just in case (1) is true, and so on.
-If (1) is true, then (1) is true; but if (1) is not true, then (1) is
-not true.
+If we assume that the complex demonstrative "this sentence" can refer
+to (1), then the proposition expressed by (1) will be true just in
+case the thing referred to by *this sentence* is true.  Thus (1) will
+be true just in case (1) is true, and (1) is true just in case (1) is
+true, and so on.  If (1) is true, then (1) is true; but if (1) is not
+true, then (1) is not true.
 
 Without pretending to give a serious analysis of the paradox, let's
 assume that sentences can have for their meaning boolean functions
@@ -529,29 +530,32 @@ is John* might denote the function `\x y. x`, our `true`.
 Then (1) denotes a function from whatever the referent of *this
 sentence* is to a boolean.  So (1) denotes `\f. f true false`, where
 the argument `f` is the referent of *this sentence*.  Of course, if
-`f` is a boolean, `f true false <~~> f`, (1) denotes the identity
-function `I`.
+`f` is a boolean, `f true false <~~> f`, so for our purposes, we can
+assume that (1) denotes the identity function `I`.
 
 If we use (1) in a context in which *this sentence* refers to the
 sentence in which the demonstrative occurs, then we must find a
 meaning `m` such that `I m = I`.  But since in this context `m` is the
-same as the meaning `I`, we have `m = I m`, so `m` is a fixed point
-for the denotation of the sentence (when used in the appropriate context).
+same as the meaning `I`, so we have `m = I m`.  In other words, `m` is
+a fixed point for the denotation of the sentence (when used in the
+appropriate context).
 
 That means that in a context in which *this sentence* refers to the
 sentence in which it occurs, the sentence denotes a fixed point for
-the identity function, `Y I`.
-
-    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; &omega;
-    &Omega
-
-Oh.  Well.  That feels right!  The meaning of *This sentence is true*
+the identity function.  Here's a fixed point for the identity
+function:
+
+<pre><code>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; &omega;
+&Omega
+</code></pre>
+
+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 &Omega;, our prototypical infinite loop...
+it occurs is <code>&Omega;</code>, our prototypical infinite loop...
 
 What about the liar paradox?
 
@@ -578,3 +582,40 @@ See Barwise and Etchemendy's 1987 OUP book, [The Liar: an essay on
 truth and circularity](http://tinyurl.com/2db62bk) for an approach
 that is similar, but expressed in terms of non-well-founded sets
 rather than recursive functions.
+
+HOWEVER, you should be cautious about feeling too comfortable with
+these results.  Thinking again of the truth-teller paradox, yes,
+<code>&omega;</code> 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.
+
+But one could ask: look, literally every formula is a fixed point for
+`I`, since
+
+    X <~~> I X
+
+for any choice of X whatsoever.
+
+So the Y combinator is only guaranteed to give us one fixed point out
+of infinitely many---and not always the intuitively most useful
+one. (For instance, the squaring function has zero as a fixed point,
+since 0 * 0 = 0, and 1 as a fixed point, since 1 * 1 = 1, but `Y
+(\x. mul x x)` doesn't give us 0 or 1.) So why in the reasoning we've
+just gone through should we be reaching for just this fixed point at
+just this juncture?
+
+One obstacle to thinking this through is the fact that a sentence
+normally has only two truth values.  We might consider instead a noun
+phrase such as 
+
+(3)  the entity that this noun phrase refers to
+
+The reference of (3) depends on the reference of the embedded noun
+phrase *this noun phrase*.  It's easy to see that any object is a
+fixed point for this referential function: if this pen cap is the
+referent of *this noun phrase*, then it is the referent of (3), and so
+for any object.
+
+Ultimately, in the context of this course, these paradoxes are more
+useful as a way of gaining leverage on the concepts of fixed points
+and recursion, rather than the other way around.