X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=exercises%2F_assignment4.mdwn;h=f998e7ac73a33c66d353463a62b91aa7b403d710;hp=fd9816dbfb3cc2a4eb0ffe8d9f0feb83312cc9d4;hb=ea4c96609b8d02f5e83a8027cf567bab5562cb5b;hpb=72b68b0bf93018ead47492255e87f1dd97827377 diff --git a/exercises/_assignment4.mdwn b/exercises/_assignment4.mdwn index fd9816db..f998e7ac 100644 --- a/exercises/_assignment4.mdwn +++ b/exercises/_assignment4.mdwn @@ -96,8 +96,8 @@ addition, and exponentiation is defined in terms of multiplication. 8. Find a fixed point `ξ` for the successor function. Prove it's a fixed point, i.e., demonstrate that `succ ξ <~~> ξ`. - We've had surprising success embedding normal arithmetic in the lambda -calculus, modeling the natural numbers, addition, multiplication, and + We've had surprising success embedding normal arithmetic in the Lambda +Calculus, modeling the natural numbers, addition, multiplication, and so on. But one thing that some versions of arithmetic supply is a notion of infinity, which we'll write as `inf`. This object usually satisfies the following constraints, for any finite natural number `n`: @@ -107,18 +107,18 @@ satisfies the following constraints, for any finite natural number `n`: n ^ inf == inf leq n inf == true - (Note, though, that with some notions of infinite numbers, operations like `+` and `*` are defined in such a way that `inf + n` is different from `n + inf`, and does exceed `inf`.) + (Note, though, that with *some* notions of infinite numbers, like [[!wikipedia ordinal numbers]], operations like `+` and `*` are defined in such a way that `inf + n` is different from `n + inf`, and does exceed `inf`.) -9. Prove that `add 1 ξ <~~> ξ`, where `ξ` is the fixed -point you found in (1). What about `add 2 ξ <~~> ξ`? +9. Prove that `add ξ 1 <~~> ξ`, where `ξ` is the fixed +point you found in (1). What about `add ξ 2 <~~> ξ`? Comment: a fixed point for the successor function is an object such that it is unchanged after adding 1 to it. It makes a certain amount of sense to use this object to model arithmetic infinity. For instance, depending on implementation details, it might happen that `leq n ξ` is true for all (finite) natural numbers `n`. However, the fixed point -you found for `succ` may not be a fixed point for `mult n` or for -`exp n`. +you found for `succ` and `(+n)` (recall this is shorthand for `\x. add x n`) may not be a fixed point for `(*n)` or for +`(^n)`. ## Mutually-recursive functions ##