老师用ackerman函数来测试我们的lisp interpreter是否能应付extremely recursive function，虽然我们都不能，但也说明了一个健壮的interpreter是需要优化recursive function的一个道理。

ackerman函数 wiki 上有介绍：http://en.wikipedia.org/wiki/Ackerman_function

我下面记录的是怎么算出来A(4,2)。（如下表述中，ns就代表A）
ns(0,x) = x + 1
ns(1,x) = ns(0, ns(x-1)) && ns(1,0) = 2. so, ns(1,x) = x + 2
ns(2,x) = ns(1, ns(2,x-1)) = ns(2,x-1)+2 && ns(2,0) = ns(1,1) = 3. so, ns(2,x) = 2x+3
ns(3,x) = ns(2,ns(3,x-1)) = 2*ns(3,x-1)+3 && ns(3,0) = ns(2,1)=5. so, ns(3,x) = 2^(x+3) - 3
ns(4,x) = ns(3, ns(x-1)) = 2^(ns(3,x-1)+3) - 3 && ns(4,0) = ns(3,1) = 13
but if we let g(x) = ns(4,x) + 3
we have g(x) = 2^(g(x-1)) && g(0) = 16 = 2^{^4}
so I think it's the end of this story (unless we use the symbol from knuth, which I just learned from wiki,
but I can manually get ns(4,2) = g(2) -3 = 2^(g(1)) - 3 = 2^(2^(g(0))) - 3 = 2^(2^{^16})) - 3 = 2^{^65536} - 3

these links may be helpful:
http://www.wolframalpha.com/input/?i=f%28x%29%3Df%28x-1%29%2B1%2Cf%280%29%3D2
http://www.wolframalpha.com/input/?i=f%28x%29+%3D+f%28x-1%29%2B2%2Cf%280%29%3D3
http://www.wolframalpha.com/input/?i=f%28x%29%3D2*f%28x-1%29%2B3%2Cf%280%29%3D5
http://www.wolframalpha.com/input/?i=f%28x%29%3D2^%28f%28x-1%29%2B3%29-3%2Cf%280%29%3D13
http://www.wolframalpha.com/input/?i=log2%28g%28x%29%29%3Dg%28x-1%29%2Cg%280%29%3D16
http://www.wolframalpha.com/input/?i=2^65536-3

当我算出来(4,2)后，我想尝试下得到ackerman函数的通式，结果后来尝试下后也可以了，需要引入wiki里学到的knuth发明的符号。“向上箭头符号”。↑
懂得这个符号以及扩展符号↑↑后，就可以证明ackerman函数的通式了，最傻瓜的方法是用归纳法证明，首先证明base case (1,1)成立，然后证明(1,x)成立；然后假设对于小于等于m的i或小于等于n的j (i,j)都成立，证明(i,j+1)成立。这样归纳法就完整了。

但是归纳法要求事先知道通式，这个不符合认识的流程。认识的流程应该是探索->猜想->证明。
以上我得出(4,2)的过程就是一个探索的过程。但是从中观察出规律确实很难，我也是在得到wiki的启发后知道的，接下来可以证明一下(4,x)，有了knuth的符号，很容易证明；接下来再证明(5,x)，也是可以的，无非knuth符号多了一层。最后再猜想，便很自然了。

ackerman函数通式的得出就写到这里。

还有一个有趣的现象，是我一个同学冷潇泠想到的，他建议把函数递归过程中的B打印出来，并且配上递归层数i,形成一些(i,B)对，把这个画在坐标系上会形成无数个抛物线，且每个抛物线都是下个抛物线的前面部分。

这个图也许还不清晰，把抛物线下的点都删掉，便有更清晰的图

这个现象还是蛮有意思的。
我的ackerman函数实现如下：