From: Chris Date: Thu, 12 Feb 2015 15:50:55 +0000 (-0500) Subject: added discussion of computation X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=31cebc8050836005ee17dd1d20ae81b2ab9afa3c added discussion of computation --- 31cebc8050836005ee17dd1d20ae81b2ab9afa3c diff --cc topics/week3_what_is_computation.mdwn index 47748a16,79fd3999..32a4572d --- a/topics/week3_what_is_computation.mdwn +++ b/topics/week3_what_is_computation.mdwn @@@ -6,13 -6,26 +6,36 @@@ expression and replacing it with an equ 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 + `3 + 4`: `7` is syntactically simple, and `3 + 4` is syntactically + complex. + + It's worth pausing a moment and wondering why we feel that replacing a + complex expression like `3 + 4` with a simplex expression like `7` + feels like we've accomplished something. If they really are + equivalent, why shouldn't we consider them to be equally valuable, or + even to prefer the longer expression? For instance, should we prefer + 2^9, or 512? Likewise, in the realm of logic, why shold we ever + prefer `B` to the conjunction of `A` with `A --> B`? + + The question to ask here is whether our intuitions about what counts + as more evaluated always tracks simplicity of expression, or whether + 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## @@@ -97,9 -110,9 +120,15 @@@ 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