author Chris Barker Mon, 27 Sep 2010 00:17:10 +0000 (20:17 -0400) committer Chris Barker Mon, 27 Sep 2010 00:17:10 +0000 (20:17 -0400)
 week3.mdwn patch | blob | history

index 27bdc53..653b307 100644 (file)
@@ -493,16 +493,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)))

(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,27 +529,31 @@ 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`.
+the identity function.  Here's a fixed point for the identity
+function:

+<pre>
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
+</pre>

-Oh.  Well.  That feels right!  The meaning of *This sentence is true*
+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...