Matemáticamente, ¿cómo se encuentra el valor de la función de Ackermann en términos de n para un m dado?

Question

Mirando la página de Wikipedia, está el tabla de valores para entradas de funciones pequeñas. Entiendo cómo se calculan los valores mirando la tabla, y cómo es fácil ver que 5,13,29,61,125 es $2^{n+3}-3$ Pero, ¿cómo se puede calcular esta fórmula "iterativa" sin identificación de patrones?

Empecé por considerar que 61 (Ackermann 3,3) es $2*(2*(2*(2*1+3)+3)+3)+3$ que lo único que estoy haciendo es ampliar la fórmula recursiva, pero no tengo ni idea de que se simplifique para crear $2^{n+3}-3$ en lugar de limitarse a observar los patrones. No se trata de una tarea, sino de curiosidad.

Answer 1

$$A(0,n) = n+1 \;\text{(by definition)}$$ $$----------------------------------------------$$ $$A(1,n) \rightarrow A(0,A(1,n-1)) \rightarrow A(1,n-1)+1 \rightarrow A(1,n-2)+2\Rightarrow A(1,0)+n$$ $$\rightarrow A(0,1)+n \rightarrow 2+n = \color{red}{2+(n+3)-3}$$ $$----------------------------------------------$$ $$A(2,n) \rightarrow A(1,A(2,n-1)) \rightarrow A(2,n-1)+2 \rightarrow A(2,n-2)+4 \Rightarrow A(2,0)+2n$$ $$\rightarrow A(1,1)+2n \rightarrow 2n+3 = \color{red}{2(n+3)-3}$$ $$----------------------------------------------$$ $$A(3,n) \rightarrow A(2,A(3,n-1)) \rightarrow 2(A(3,n-1)+3)-3 \rightarrow 4(A(3,n-2)+3)-3 $$ $$\Rightarrow 2^n(A(3,0)+3)-3 \rightarrow 2^n(A(2,1)+3)-3 = 2^n(2^3)-3 = \color{red}{2^{n+3}-3} $$ $$----------------------------------------------$$ $$A(4,n) \rightarrow A(3,A(4,n-1)) \rightarrow 2^{A(4,n-1)+3}-3 \rightarrow 2^{2^{A(4,n-2)+3}}-3 \rightarrow 2^{2^{2^{A(4,n-3)+3}}}-3 $$ $$\Rightarrow\,(^{n}2)^{A(4,0)+3}-3 \rightarrow (^{n}2)^{A(3,1)+3}-3 \rightarrow (^{n}2)^{2^3}-3 \,=\, \color{red}{{^{n+3}}2-3}$$ $$----------------------------------------------$$ $$\text{Assume}\;A(m,n) = 2[m](n+3)-3,\; \text{and note} \;2[m]2=4 \;\forall m>0$$ $$A(m+1,0) \rightarrow A(m,1) \rightarrow 2[m]4-3 = 2[m](2[m]2)-3 = \color{red}{2[m+1]3-3}$$ $$A(m+1,n+1) \rightarrow A(m,A(m+1,n)) \rightarrow 2[m](2[m+1](n+3)-3+3)-3\\ = 2[m](2[m+1](n+3))-3 = \color{red}{2[m+1](n+4)-3}$$ $$\mathbf{QED}$$ $$----------------------------------------------$$ Nota: una sola flecha a la derecha representa una sola iteración de la función de Ackermann, y una flecha doble representa muchas (normalmente $n$ iteraciones)

Answer 2

A partir de la definición de la función de Ackerman, tenemos

\begin {align*} A(3, n) &= A(2, A(3, n - 1)) \end {align*}

Ahora $A(2, b)$ se puede calcular (al menos a partir de la tabla de valores) que es $2b + 3$ Así que nos encontramos con

$$A(3, n) = 2A(3, n - 1) + 3$$

Esto da lugar a una secuencia recursiva; llamando a $A(3, n) = x_n$ tenemos la relación

$$x_n = 2x_{n - 1} + 3$$ Esto se puede resolver directamente (usando, por supuesto, una condición inicial) o sustituyendo la conjetura del patrón; de cualquier manera, es lo que escribiste.

---

Ahora todo lo que hice fue transferir el problema a una fila diferente de la tabla. Vamos a estudiar $A(2, n)$ de la misma manera: Tenemos

$$A(2, n) = A(1, A(2, n - 1))$$

A partir de la tabla, tenemos que $A(1, b) = b + 2$ , dando lugar a la recursión

$$y_n = y_{n - 1} + 2$$ Esto da exactamente la solución $y_n = 2n + 3$ cuando se calcula la condición inicial.

---

Pero, de nuevo, esto tiene el mismo problema: acabo de utilizar un diferentes fila previamente conocida. Hagamos esto una vez más:

$$A(1, n) = A(0, A(1, n - 1))$$

Pero ahora estamos de suerte. Por definición $A(0, b) = b = 1$ Así que

$$A(1, n) = A(1, n - 1) + 1$$

Esta es una recurrencia fácil de resolver. La condición $A(1, 0) = 1$ nos da la base, y encontramos

$$\boxed{A(1, n) = n + 1}$$

---

Así que ahora pongamos todo junto, al revés. Obtenemos $A(1, n)$ casi directamente de la definición de la función de Ackermann. Entonces obtenemos $A(2, n)$ de una relación de recurrencia que redujo $A(2, n)$ para estudiar $A(1, A(2, n - 1))$ . Entonces podemos obtener $A(3, n)$ de un proceso similar.