fixed broken markdown?

[lambda.git] / week3.mdwn

diff --git a/week3.mdwn b/week3.mdwn
index 27bdc53..2252387 100644 (file)
--- 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:
 
 
 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.
 
 
 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,
 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! ...
 
 
     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)))
 
 
     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.
 
 
 (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
 
 Without pretending to give a serious analysis of the paradox, let's
 assume that sentences can have for their meaning boolean functions


@@ -529,27 +530,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
 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
 
 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
 
 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
     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...
 
 in a context in which *this sentence* refers to the sentence in which
 it occurs is &Omega;, our prototypical infinite loop...