week3.mdwn

   1 Even with a fold-based representation of numbers, and pred/equal/subtraction, some computable functions are going to be out of our reach.
   2
   3 Fibonacci: doable without Y, but takes some ingenuity
   4
   5 And so on...
   6
   7 Need a general method, where f(n) doesn't just depend on f(n-1) or (f(n-1),f(n-2),..).
   8
   9 Looks like Ackermann function is simplest example that MUST be done with Y, Everything simpler could be done using only fixed iteration limits.
  10
  11 A(y,x) =
  12         | when x == 0 -> y + 1
  13         | when y == 0 -> A(x-1,1)
  14         | _ -> A(x-1, A(x,y-1))
  15
  16 A(0,y) = y+1
  17 A(1,y) = y+2
  18 A(2,y) = 2y + 3
  19 A(3,y) = 2^(y+3) -3
  20 A(4,y) = 2^(2^(2^...2)) [y+3 2s] - 3
  21
  22
  23 Some algorithms can also be done more efficiently / intelligibly with general mechanism for recursion.
  24
  25 How to do recursion with omega.
  26
  27 fixed point combinators
  28