阿克曼 (Ackermann) 函数

阿克曼函数是递归函数的经典示例，特别值得注意的是它并不是一个原始递归函数。它的值增长得非常快，调用树也增长得非常快。阿克曼函数通常定义如下：

\[\begin{split}A(m, n) = \begin{cases} n+1 & \mbox{if } m = 0 \\ A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases}\end{split}\]

sCrypt 设计了一种使用 原生脚本 计算阿克曼函数值的方法。该方法是非常复杂的。下面我们提供一个更简单的版本。

contract Ackermann {
    int a;  // a = 2
    int b;  // b = 1

    function ackermann(int m, int n): int {
        bytes stk = num2bin(m, 1);

        // run this function off chain to get the loop count and set it here
        // e.g., (2, 1) requires 14 loops, (3, 5) 42438
        loop (14) {
            if (len(stk) > 0) {
                bytes top = stk[0:1];
                m = unpack(top);

                // pop
                stk = stk[1:len(stk)];

                if (m == 0) {
                    n = n + m + 1;
                } else if (n == 0) {
                    n = n + 1;
                    m = m - 1;
                    // push
                    stk = num2bin(m, 1) + stk;
                } else {
                    stk = num2bin(m - 1, 1) + stk;
                    stk = num2bin(m, 1) + stk;
                    n = n - 1;
                }
            }
        }

        return n;
    }

    // y = 5
    public function unlock(int y) {
        require(y == this.ackermann(this.a, this.b));
    }
}