X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=topics%2Fweek4_fixed_point_combinators.mdwn;h=20c2974826966af354518de09b5c1ebb7c994e29;hp=3ac5db349a2d2cfb5ab9b439a99be748ef5db836;hb=26a6be49777defe30bc86974e0b7d21b1c1057e2;hpb=d0a881712576b267e3d1d4451b71cefca025890e;ds=sidebyside
diff --git a/topics/week4_fixed_point_combinators.mdwn b/topics/week4_fixed_point_combinators.mdwn
index 3ac5db34..20c29748 100644
--- a/topics/week4_fixed_point_combinators.mdwn
+++ b/topics/week4_fixed_point_combinators.mdwn
@@ -186,7 +186,17 @@ returns `#t`, because if we follow the path from the head of the list argument,
(looking '(6 2 grits caviar 5 7 3))
-our path will take us from `6` to `7` to `3` to `grits`, which is not a number but not the `'caviar` we were looking for either. So this returns `#f`. It would be very difficult to define these functions without recourse to something like `letrec` or `define`, or the techniques developed below (and also in that chapter of *The Little Schemer*).
+our path will take us from `6` to `7` to `3` to `grits`, which is not a number but not the `'caviar` we were looking for either. So this returns `#f`. It's not clear how to define such functions without recourse to something like `letrec` or `define`, or the techniques developed below (and also in that chapter of *The Little Schemer*).
+
+*The Little Schemer* also mentions the Ackermann function, as well as the interesting [[!wikipedia Collatz conjecture]]. They also point out that functions like their `looking` never return any value --- neither `#t` nor `#f` --- for some arguments, as in the example:
+
+ (looking '(7 1 2 caviar 5 6 3))
+
+Here our path takes us from `7` to `3` to `2` to `1` back to `7`, and the cycle repeats. So in this case, the `looking` function never returns any value.
+
+We've already tacitly been dealing with functions that we assumed to be defined only for expressions representing booleans, or only for expressions representing numbers. But in all such cases we could specify in advance what the intended domain of the function was. With examples like the above, it's not clear how to specify the domain in advance, in such a way that our function will still give a definite result for every argument in the domain. Instead, the capacity for fully general recursion brings with it also the downside that some functions will be only **partially defined**, even over restricted domains we're able to define in advance. We will see more extreme examples of this below.
+
+(Being only definable with the power of fully general recursion doesn't by itself render you only partially defined: the Ackermann function is total. The downside is rather that there's no way to let fully general recursion in, while limiting its use to just the cases where a definite value will be returned for every argument.)
## Using fixed-point combinators to define recursive functions ##
@@ -269,6 +279,7 @@ it's not complete, since we don't know what value to use for the
symbol `LENGTH`. Technically, it has the status of an unbound
variable.
+
Imagine now binding the mysterious variable, and calling the resulting
term `h`: