author Chris Thu, 12 Feb 2015 16:01:24 +0000 (11:01 -0500) committer Chris Thu, 12 Feb 2015 16:01:24 +0000 (11:01 -0500)

index 32a4572..79fd399 100644 (file)
@@ -6,15 +6,6 @@ expression and replacing it with an equivalent simpler expression.
3 + 4 == 7

This equation can be interpreted as expressing the thought that the
-complex expression `3 + 4` evaluates to `7`.  The evaluation of the
-expression computing a sum.  There is a clear sense in which the
-expression `7` is simpler than the expression `3 + 4`: `7` is
-syntactically simple, and `3 + 4` is syntactically complex.
-
-Now let's take this folk notion of computation, and put some pressure
-on it.
-=======
complex expression `3 + 4` evaluates to `7`.  In this case, the
evaluation of the expression involves computing a sum.  There is a
clear sense in which the expression `7` is simpler than the expression
@@ -35,7 +26,6 @@ it tracks what is more useful to us in a given larger situation.

But even deciding which expression ought to count as simpler is not
always so clear.
->>>>>>> working:topics/week3_what_is_computation.mdwn

##Church arithmetic##

@@ -87,14 +77,14 @@ But now consider multiplication:
Is the final result simpler?  This time, the answer is not so straightfoward.
Compare the starting expression with the final expression:

-        *           3             4
+        *           3             4
(\lrf.l(rf))(\fz.f(f(fz)))(\fz.f(f(f(fz))))
~~> 12
(\fz.f(f(f(f(f(f(f(f(f(f(f(fz))))))))))))

And if we choose different numbers, the result is even less clear:

-        *           3             6
+        *           3             6
(\lrf.l(rf))(\fz.f(f(fz)))(\fz.f(f(f(f(f(fz))))))
~~> 18
(\fz.f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(fz))))))))))))))))))
@@ -120,15 +110,9 @@ that reduce to that term.
(y((\xx)y)) ~~> yy
etc.

-In the arithmetic example, there is only one number that corresponds
-to the sum of 3 and 4 (namely, 7).  But there are many sums that add
-up to 7: 3+4, 4+3, 5+2, 2+5, 6+1, 1+6, etc.
-=======
Likewise, in the arithmetic example, there is only one number that
corresponds to the sum of 3 and 4 (namely, 7).  But there are many
sums that add up to 7: 3+4, 4+3, 5+2, 2+5, 6+1, 1+6, etc.
->>>>>>> working:topics/week3_what_is_computation.mdwn

So the unevaluated expression contains information that is missing
from the evaluated value: information about *how* that value was
@@ -153,7 +137,7 @@ pathological examples where the results do not align so well:
In this example, reduction returns the exact same lambda term.  There
is no simplification at all.

-    (\x.xxx)(\x.xxx) ~~> ((\x.xxxx)(\x.xxxx)(\x.xxxx))
+    (\x.xxx)(\x.xxx) ~~> ((\x.xxxx)(\x.xxxx)(\x.xxxx))

Even worse, in this case, the "reduced" form is longer and more
complex by any measure.