La función de Ackermann "crece más rápido" que cualquier función recursiva primitiva

Question

Estoy viendo la prueba de que la función de Ackermann no es recursiva primitiva.

En la parte:

"Demostraremos que la función de Ackermann no es recursiva primitiva demostrando que "crece más rápido" que cualquier función recursiva primitiva. Esto significa que necesitamos una forma precisa de comparar la "tasa de crecimiento" de la función de dos variables $A$ con la de un $n-$ función variable. Lo que intentaremos hacer es demostrar que para cualquier $n-$ función primitiva recursiva variable $f$ existe un número natural $k$ tal que $$A(k, \max (x_1, \dots , x_n)) > f(x_1, \dots , x_n) \tag {*}$$ para todos los valores de $x_1, \dots , x_n$ . La prueba se realiza por inducción sobre el número de composiciones y recursiones primitivas necesarias para definir la función $f$ . "

¿Podría explicarme por qué queremos mostrar que para cualquier $n-$ función primitiva recursiva variable $f$ existe un número natural $k$ tal que $A(k, \max (x_1, \dots , x_n)) > f(x_1, \dots , x_n) $ para todos los valores de $x_1, \dots , x_n$ para demostrar que la función de Ackermann "crece más rápido" que cualquier función recursiva primitiva?

Además, ¿por qué utilizamos la inducción sobre el número de composiciones y recursiones primitivas necesarias para definir la función $f$ ??

$$$$

EDITAR:

La prueba de que la función de Ackermann no es recursiva primitiva es la siguiente:

Para demostrarlo necesitamos las siguientes propiedades relativas a los valores de $A$ .

1. $A(x,y)>y$ .

2. $A(x,y+1)>A(x,y)$ .

3. Si $y_2>y_1$ entonces $A(x,y_2)>A(x,y_1)$ .

4. $A(x+1, y) \geq A(x,y+1)$ .

5. $A(x,y)>x$ .

6. Si $x_2>x_1$ entonces $A(x_2, y)>A(x_1, y)$ .

7. $A(x+2, y)>A(x,2y)$ .

Demostraremos que la función de Ackermann no es recursiva primitiva demostrando que "crece más rápido" que cualquier función recursiva primitiva. Esto significa que necesitamos una forma precisa de comparar la "tasa de crecimiento" de la función de dos variables $A$ con la de un $n-$ función variable. Lo que intentaremos hacer es demostrar que para cualquier $n-$ función primitiva recursiva variable $f$ existe un número natural $k$ tal que $$A(k, \max (x_1, \dots , x_n)) > f(x_1, \dots , x_n) \tag {*}$$ para todos los valores de $x_1, \dots , x_n$ . La prueba se realiza por inducción sobre el número de composiciones y recursiones primitivas necesarias para definir la función $f$ . Para llevar a cabo el paso de inducción de la prueba, necesitamos dos resultados auxiliares. Estos resultados aseguran que si las funciones $g_1, \dots , g_m$ y $h$ satisfacer $(*)$ , también lo hace la función $f$ obtenido de $g_1, \dots , g_m$ y $h$ por la composición funcional.

Lema 1 . Deje que el $n-$ función variable $f=h \circ (g_1, \dots , g_m)$ se obtienen a partir de las funciones $g_1, \dots , g_m$ y $h$ por composición. Supongamos la existencia de números naturales $k_1, \dots , k_m$ y $k_0$ tal que $$A(k_i, \max (x_1, \dots , x_n)) > g_i (x_1, \dots , x_n) \text{ for } 1 \leq i \leq m\\ \text{ and } \\ A(k_0, \max (y_1, \dots , y_m )) > h(y_1, \dots , y_m)$$ para todos $x_1, \dots , x_n$ y $y_1, \dots , y_m$ . Definir $k$ para ser el número natural $\max (k_0, k_1, \dots , k_m)+2$ . Entonces $A(k, \max (x_1, \dots , x_n)) > f(x_1, \dots , x_n)$ para todos $x_1, \dots , x_n$ .

Lema 2 . Deje que el $(n+1)-$ función variable $f$ se definen por recursión primitiva a partir del $n-$ función variable $g$ y el $(n+2)-$ función variable $h$ para que $$f(x_1, \dots , x_n, 0)=g(x_1, \dots , x_n) \\ f(x_1, \dots x_n, y+1)=h(x_1, \dots , x_n , y, f(x_1, \dots , x_n, y))$$ Asumir la existencia de números naturales $k_g$ y $k_h$ tal que $$A(k_g ,\max (x_1, \dots , x_n)) > g(x_1, \dots , x_n) \\ \text{ and } \\ A(k_h, \max (x_1, \dots , x_n , y , z)) > h(x_1, \dots , x_n , y, z)$$ para todos $x_1, \dots ,x_n, y$ y $z$ . Definir $k$ para ser el número natural $\max (k_g, k_h)+3$ . Entonces $A(k, \max (x_1, \dots , x_n , y)) > f(x_1, \dots ,x_n , y)$ para todos $x_1, \dots , x_n, y$ .

Teorema 1. Para cada $n-$ función primitiva recursiva variable $f$ existe un número natural $k$ tal que $A(k, \max (x_1, \dots , x_n)) > f(x_1, \dots , x_n)$ para todos $x_1, \dots , x_n$ .

Prueba. Por iducción sobre el número de composiciones y recursiones primitivas necesarias para definir $f$ . Utilizamos $\hat{x}$ para indicar $\max (x_1, \dots , x_n)$ .

Base. Si la derivación de $f$ no requiere composiciones ni recursiones primitivas, son posibles tres casos.

1. Si $f$ es la función constante cuyo valor es $c$ , elija $k=c$ . Propiedad $5$ entonces garantiza que $A(k, \hat {x})=A(c, \hat{x})>c=f(x_1, \dots , x_n)$ .

2. Si $f$ es la función de proyección cuyo valor es $x_i$ , elija $k=0$ . Entonces $A(k,\hat{x})=A(0,\hat(x))=\hat(x)+1>x_i=f(x_1, \dots , x_n)$ .

3. Si $f$ es la función sucesora, elija $k=1$ . Entonces $A(k,x)=A(1,x)>A(0,x)=x+1=f(x)$ .

Paso de inducción. Supongamos que el enunciado del teorema es verdadero para todas las funciones que requieren $w$ o menos composiciones y recursiones primitvas. Sea $f$ sea una función que requiera un total de $w+1$ composiciones y recursiones primitivas. Son posibles dos casos.

1. Si $f$ se deriva de las funciones $g_1, \dots , g_m$ y $h$ por composición, la hipótesis de inducción debe aplicarse a cada uno de $g_1, \dots , g_m$ y $h$ . Lema $1$ entonces garantiza la existencia de un número $k$ tal que $A(k,\hat{x})>f(x_1, \dots , x_n)$ .

2. Si $f$ se deriva de las funciones $g$ y $h$ por recursión primitiva, la hipótesis de inducción debe aplicarse a $g$ y $h$ . Lema $2$ entonces garantiza la existencia de un número $k$ tal que $A(k, \hat{x})>f(x_1, \dots , x_n)$ .

Teorema $1$ proporciona una expresión formal del notopn que $A$ "crece más rápido" que cualquier función recursiva primitiva. Ahora es una cuestión sencilla de establecer:

Teorema 2. La función de Ackermann no es recursiva primitiva.

Prueba. Supongamos que la función de Ackermann es recursiva primitiva. Entonces, según el Teorema 1, debe existir un número natural $k$ tal que $$A(k, \max (x,y)) > A(x,y)$$ para todos $x$ y $y$ . Configuración $x=y=k$ entonces se produce la contradicción $$A(k,k) > A(k,k)$$ de lo que se deduce que $A$ no puede ser recursivo primitivo.

Answer 1

Queremos demostrar que la función de Ackermann no es recursiva primitiva. Una forma de demostrarlo es mostrar que no es igual a ninguna de las funciones recursivas primitivas. El argumento "crece más rápido" lo consigue. Si la función de Ackermann crece más rápido que cualquier función recursiva primitiva, no es igual a ninguna de ellas.

Para que el argumento de "crece más rápido", tenemos que comparar la función de Ackermann con todas las funciones recursivas primitivas. Como las funciones recursivas primitivas se definen con una estructura de árbol utilizando la composición y la recursión primitiva, la inducción nos permite abarcarlas todas de la misma manera que la inducción aritmética nos permite abarcar todos los números naturales.