projects
/
lambda.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
fixing computation discussion
[lambda.git]
/
topics
/
week3_what_is_computation.mdwn
diff --git
a/topics/week3_what_is_computation.mdwn
b/topics/week3_what_is_computation.mdwn
index
32a4572
..
79fd399
100644
(file)
--- a/
topics/week3_what_is_computation.mdwn
+++ b/
topics/week3_what_is_computation.mdwn
@@
-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
3 + 4 == 7
This equation can be interpreted as expressing the thought that the
-<<<<<<< HEAD:topics/_week3_what_is_computation.mdwn
-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
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.
But even deciding which expression ought to count as simpler is not
always so clear.
->>>>>>> working:topics/week3_what_is_computation.mdwn
##Church arithmetic##
##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:
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:
(\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))))))))))))))))))
(\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.
(y((\xx)y)) ~~> yy
etc.
-<<<<<<< HEAD:topics/_week3_what_is_computation.mdwn
-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.
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
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.
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.
Even worse, in this case, the "reduced" form is longer and more
complex by any measure.