Funciones recursivas primitivas y función Ackerman

La función de Ackerman es una de las características más famosas de la informática. Se asocia con al menos un resultado fundamental y al menos uno simplemente importante. El resultado fundamental, para decirlo de forma clara e incomprensible, es el siguiente: existe una función computable definida en todas partes que no es primitiva recursiva. Un resultado importante es que el bosque de conjuntos disjuntos (también conocido como unión de conjuntos disjuntos) es muy rápido .

Realmente me gusta estudiar la función de Ackerman, como Todo lo relacionado con él es muy hermoso y elegante. Por lo tanto, el resultado fundamental registrado anteriormente es mucho más fácil de entender de lo que parece.

En el siguiente texto aprenderá qué son las funciones recursivas primitivas y cómo descubrir que la función de Akkerman no se aplica a ellas. ¡Y, por supuesto, este texto te convencerá de que es un diseño increíblemente hermoso y un razonamiento increíblemente hermoso!

1. ¿Por qué puede ser interesante?

La discusión de la relación entre las funciones recursivas primitivas y la función de Ackerman es un ejemplo de resolución del problema estándar en la teoría de la computabilidad: se da un cierto modelo computacional, una determinada función, y es necesario determinar si esta función es computable en este modelo.

Otros ejemplos similares están asociados, por ejemplo, con la capacidad de decisión algorítmica , la equivalencia de varios modelos computacionales (máquinas de Turing, funciones parcialmente recursivas, algoritmos normales de Markov, etc.). Y a través de ellos ya estamos conectados con un área de definición completamente práctica para la integridad de Turing de los lenguajes de programación, transformaciones equivalentes de textos de programa y otras cosas interesantes.

La función de Ackerman parece haber sido creada especialmente para ser un ejemplo elegante de resolver tales problemas. Verás esto pronto.

2. Función de Ackerman

, « ». , , , .

$$$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))$$

Por analogía, podemos construir una función en la que $$$n$ elevado al poder $$$n$cinco veces, diez veces, cien veces, un millón de veces. La función de Ackerman crece más rápido que cualquiera de estas funciones. ¡Así de rápido crece!