Funções recursivas primitivas e função Ackerman

A função de Ackerman é uma das características mais famosas da Ciência da Computação. Está associado a pelo menos um resultado fundamental e pelo menos um simplesmente importante. O resultado fundamental, para colocá-lo de maneira clara e incompreensível, é o seguinte: existe uma função computável definida em todos os lugares que não é recursiva primitiva. Um resultado importante é que a floresta de conjuntos disjuntos (também conhecida como união de conjuntos disjuntos) é muito rápida .

Eu realmente gosto de estudar a função de Ackerman, como tudo relacionado a ela é muito bonito e elegante. Portanto, o resultado fundamental registrado acima é muito mais fácil de entender do que parece.

No texto abaixo, você aprenderá o que são funções recursivas primitivas e como descobrir que a função Akkerman não se aplica a elas. E, é claro, este texto o convencerá de que é um design incrivelmente bonito e um raciocínio incrivelmente bonito!

1. Por que pode ser interessante

A discussão da relação entre funções recursivas primitivas e a função Ackerman é um exemplo de solução de um problema padrão na teoria da computabilidade: um determinado modelo de cálculo, uma determinada função é fornecida e é necessário determinar se essa função é computável nesse modelo.

Outros exemplos semelhantes estão associados, por exemplo, à decidibilidade algorítmica , à equivalência de vários modelos computacionais (máquinas de Turing, funções parcialmente recursivas, algoritmos normais de Markov e assim por diante). E através deles já estamos conectados a uma área de definição completamente prática para a integridade de Turing das linguagens de programação, transformações equivalentes dos textos dos programas e outras coisas interessantes.

A função de Ackerman parece ter sido criada especialmente para ser um exemplo elegante de solução de tais problemas. Você verá isso em breve.

2. função 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))$$

E as propriedades da sequência introduzida de funções garantem que

$$

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

Finalmente:

$$

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

E é aqui que a nossa prova termina. O engraçado é que, cada aplicação de composição ou recursão primitiva aumenta em um o número da função necessária pelas condições da instrução.

5. Função Ackerman e PRF, parte dois

Portanto, sabemos que, para qualquer função recursiva primitiva, existe uma função $$$a_M$que crescerá mais rápido. Agora você pode definir a seguinte função:

$$

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

De fato, introduzindo a sequência de funções de um argumento, introduzimos a função de dois argumentos: o primeiro deles define o número da função na sequência, o segundo - o próprio argumento. Igualando o número e o argumento, obtemos a função de um argumento.

: $$$A$ -.

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

$$

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

, -. - , ! .

6. ?

, , - , . , . $$$n^n$. Além disso, qualquer função da forma

$$

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

com um número predeterminado de expoentes, é recursivo primitivo. Eu não vou ser preguiçoso e provar isso. Para começar, eu construirei uma função$$$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)$$

Agora eu uso para definir uma função $$$n^n$:

$$

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

Como você pode ver, isso é feito por simples substituição. Agora não há dificuldade em definir uma função$$$n^{n^n}$:

$$

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

Por analogia, podemos construir uma função na qual $$$n$ elevado ao poder $$$n$cinco vezes, dez vezes, cem vezes, um milhão de vezes. A função de Ackerman cresce mais rapidamente do que qualquer uma dessas funções. É assim que cresce rápido!