Primitive recursive functions and Ackerman function

Ackerman's function is one of the most famous features in Computer Science. It is associated with at least one fundamental result and at least one simply important one. The fundamental result, to put it neatly and incomprehensibly, is as follows: there exists a definite computable function everywhere that is not primitive recursive. An important result is that the forest of disjoint sets (also known as disjoint set union) is very fast .

I really like to study the function of Ackerman, as everything connected with it is very beautiful and elegant. So the fundamental result recorded above is much easier to understand than it might seem.

From the text below you will learn what primitive recursive functions are and how to find out that the Akkerman function does not apply to them. And, of course, this text will convince you that it is an incredibly beautiful design and incredibly beautiful reasoning!

1. Why it may be interesting

The discussion of the relationship between primitive recursive functions and the Ackerman function is an example of solving the standard problem in computability theory: a certain computational model, a certain function are given, and it is necessary to determine whether this function is computable in this model.

Other similar examples are associated, for example, with algorithmic decidability , the equivalence of various computational models (Turing machines, partially recursive functions, normal Markov algorithms, and so on). And through them we are already connected with a completely practical area of ​​definition for the Turing completeness of programming languages, equivalent transformations of program texts and other interesting things.

Ackerman's function seems to have been specially created in order to be an elegant example of solving such problems. You will see this soon.

2. Ackerman function

, « ». , , , .

$$$a_0, a_1, ..., a_n, ...$ . :

$$

$$a_0(x) = x + 1$$

$$

$$a_{i+1}(x) = a_{i}[x+2](x)$$

$$$f[n](x) = f\Big(f(...(f(x))...)\Big)$ — $$$n$, $$$n$ . , : , $$$x+2$ $$$x$ — $$$x$.

, — , .

:

def Foo(number, argument):
    if number == 0:
        return argument + 1

    result = argument
    for i in range(argument + 2):
        result = Foo(number - 1, result)

    return result

$$$a_i(x)$ Foo(i, x).

. -, : $$$a_i(x) > x$ $$$i$ $$$x$. , , $$$a_0(x) = x + 1 > x$, $$$a_0$ .

-, : $$$a_{i+1}(x) \gt a_i(x)$ $$$i$ $$$x$. , — , . :

$$

$$a_{i+1}(x) = a_i[x+2](x) \ge a_i[2](x) = a_i\Big(a_i(x)\Big) > a_i(x)$$

,

$$

$$a_{i+1}(x) \ge a_i\Big(a_i(x)\Big)$$

3. - ()

« ». — . : , , , .

- ? «». - :

1. , : $$$Null(x_1,x_2,...,x_k) = 0$
2. : $$$S(x)=x+1$
3. -: $$$P_k^i(x_1, x_2,...,x_k)=x_i$

. « »:

• . $$$f$ — $$$k$ , $$$g_1,g_2,...,g_k$ — $$$n$ , $$$n$ $$$F$: $$$n$ , $$$k$ $$$g_1,...,g_k$, $$$f$. !

$$

$$F(x_1,...,x_n)=f\Big(g_1(x_1,...,x_n),...,g_k(x_1,...,x_n)\Big)$$

• . $$$f$ — $$$k$ , $$$g$ — $$$k+2$ , , :

$$

$$F(x_1,...,x_k,0)=f(x_1,...,x_k)$$

$$

$$F(x_1,...,x_k,y+1)=g\Big(x_1,...,x_k,y,F(x_1,...,x_k,y)\Big)$$

, . : , . : , , . , .. , .

, — , , .

.

, . , . , :

$$

$$Sum(x,0)=P_1^1(x)$$

$$

$$Sum(x,y+1)=S\Big(P_3^3(x,y,Sum(x,y))\Big)$$

— , . , . $$$Sum(x,0)=x$, , .. $$$x$ . $$$P_1^1$. , : $$$x,y,Sum(x,y)$. , $$$P_3^3$, .

:

$$

$$Mult(x,0)=Null(x)$$

$$

$$Mult(x,y+1)=Sum\Big(P_3^1(x,y,Mult(x,y)),P_3^3(x,y,Mult(x,y))\Big)$$

- . , ! , :

$$$Fib_0 = 0$
$$$Fib_1 = 1$
$$$Fib_{n+2} = Fib_n + Fib_{n+1}$

, ; , !

, . , $$$F$, . , $$$G$, , :

$$$F(n) = Fib_n$
$$$G(n) = Fib_{n+1}$

$$$F$ 0, 1, 1, 2, 3, 5; $$$G$, , 1, 1, 2, 3, 5, 8. :
$$$G(n+1) = G(n) + F(n)$
$$$F(n+1) = G(n)$

:

$$

$$F(0)=Null()$$

$$

$$G(0)=S(Null())$$

$$

$$F(y+1)=P_2^1\Big(G(y),F(y)\Big)$$

$$

$$G(y+1)=Sum\Big(F(y),G(y)\Big)$$

:

def G(x):
    if x == 0:
        return 1
    return G(x - 1) + F(x - 1)

def F(x):
    if x == 0:
        return 0
    return G(x - 1)

, , , , $$$n$- - !

4. ,

, - « » . : - $$$k$ $$$f$ $$$n$, :

$$

$$f(x_1,...,x_k)<a_n(max(x_1,...,x_k))$$

— . , , .

, :

$$

$$Null(x_1,...,x_k)=0<max(x_1,...,x_k) + 1=a_0(max(x_1,...,x_k))$$

$$

$$S(x)=x+1=a_0(x)<a_1(x)$$

$$

$$P_k^i(x_1,...,x_k)=x_i\le max(x_1,...,x_k)<a_0\Big(max(x_1,...,x_k)\Big)$$

, , $$$a_0$ (: , , ). — $$$a_0$, $$$a_1$. - , , , .

. : , , , , .

$$$F$ $$$f,g_1,...,g_k$, $$$a_M$. , $$$F$ . :

$$

$$F(x_1,...,x_n)=f\Big(g_1(x_1,...,x_n),...,g_k(x_1,...,x_n)\Big)<$$

$$

$$<a_M\Big(max(g_1(x_1,...,x_n),...,g_k(x_1,...,x_n))\Big)<$$

$$

$$<a_M\Big[max\Big(a_M(max(x_1,...,x_n)),...,a_M(max(x_1,...,x_n))\Big)\Big]$$

$$

$$<a_M\Big(a_M(max(x_1,...,x_n))\Big) \le a_{M+1}\Big(max(x_1,...,x_n)\Big)$$

$$$f$, $$$g_i$, $$$k$ , . $$$a_M$ , $$$a_{M+1}$.

$$$F$ $$$f$ $$$g$, $$$a_M$.

, , . : $$$f$:

$$

$$F(x_1,...,x_k,0)=f(x_1,...,x_k)<a_M\Big(max(x_1,...,x_k)\Big)$$

, , :

$$

$$F(x_1,...,x_k,1)=g\Big(x_1,...,x_k,0,F(x_1,...,x_k,0)\Big)<$$

$$

$$<a_M\Big(max(x_1,...,x_k,0,a_M(max(x_1,...,x_k))\Big)<$$

$$

$$<a_M\Big(a_M(max(x_1,...,x_k)\Big)=a_M[2](max(x_1,...,x_k))$$

$$$F$, $$$g$. $$$a_M$: ,

$$

$$a_M\Big(max(x_1,...,x_k)\Big)>max(x_1,...,x_k, 0)$$

, ,

$$

$$F(x_1,...,x_k,y)<a_M[y+1](max(x_1,...,x_k))$$

,

$$

$$a_M[y+1](max(x_1,...,x_k))<a_{M+1}\Big(max(x_1,...,x_k,y)\Big)$$

:

$$

$$F(x_1,...,x_k,y)<a_{M+1}\Big(max(x_1,...,x_k,y)\Big)$$

. , , .

5. ,

, , - $$$a_M$, . :

$$

$$A(n)=a_n(n)$$

, , : , — . , .

: $$$A$ -.

, , -. 4 $$$M$, $$$A(x)<a_M(x)$ $$$x$. , :

$$

$$A(M+1)=a_{M+1}(M+1)>a_M(M+1)$$

, -. - , ! .

6. ?

, , - , . , . $$$n^n$. ,

$$

$$n^{n^{...^{n^n}}}$$

, -. . $$$n^y$:

$$

$$Pow(n,0)=S(Null())$$

$$

$$Pow(n,y+1)=Mult\Big(P_3^1(n,y,Pow(n,y)),P_3^3(n,y,Pow(n,y))\Big)$$

$$$n^n$:

$$

$$SPow(n)=Pow(P_1^1(n),P_1^1(n))$$

, . , $$$n^{n^n}$:

$$

$$SSPow(n)=Pow(P_1^1(n),SPow(n))$$

By analogy, we can construct a function in which $$$n$ raised to the power $$$n$five times, ten times, a hundred times, a million times. Ackerman's function grows faster than any of these functions. That's how fast it grows!