From: Chris Date: Thu, 12 Feb 2015 16:01:24 +0000 (-0500) Subject: fixing computation discussion X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=5f69cb4b3489f4c902ba990cb254bf3ba112d43b fixing computation discussion --- diff --git a/topics/week3_what_is_computation.mdwn b/topics/week3_what_is_computation.mdwn index 32a4572d..79fd3999 100644 --- 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 -<<<<<<< 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 @@ -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. -<<<<<<< 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. ->>>>>>> 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.