From: Jim Pryor <profjim@jimpryor.net>
Date: Fri, 17 Sep 2010 20:40:39 +0000 (-0400)
Subject: tweak week3
X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=94621f911e8647cb12c1eb0a759ef2c3ffdb3f53

tweak week3

Signed-off-by: Jim Pryor <profjim@jimpryor.net>
---

diff --git a/week3.mdwn b/week3.mdwn
index 386a8b70..fe7c3153 100644
--- a/week3.mdwn
+++ b/week3.mdwn
@@ -1,9 +1,28 @@
-Even with a fold-based representation of numbers, and pred/equal/subtraction, some recursive functions are going to be out of our reach.
+Even with a fold-based representation of numbers, and pred/equal/subtraction, some computable functions are going to be out of our reach.
 
-Need a general method, where f(n) doesn't just depend on f(n-1) or (f(n-1),f(n-2),..). Fibonacci can be done without Y. 
-Ackermann function would need Y, but surely we can find some simpler demonstration?
+Fibonacci: doable without Y, but takes some ingenuity
 
-How to do with recursion with omega.
+And so on...
+
+Need a general method, where f(n) doesn't just depend on f(n-1) or (f(n-1),f(n-2),..).
+
+Looks like Ackermann function is simplest example that MUST be done with Y, Everything simpler could be done using only fixed iteration limits.
+
+A(y,x) =
+	| when x == 0 -> y + 1
+	| when y == 0 -> A(x-1,1)
+	| _ -> A(x-1, A(x,y-1))
+
+A(0,y) = y+1
+A(1,y) = y+2
+A(2,y) = 2y + 3
+A(3,y) = 2^(y+3) -3
+A(4,y) = 2^(2^(2^...2)) [y+3 2s] - 3
+
+
+Some algorithms can also be done more efficiently / intelligibly with general mechanism for recursion.
+
+How to do recursion with omega.
 
 fixed point combinators