¿Esta función es una función primitiva recursiva?

Question

Deje $t \in \mathbb{N}$ y considere la función $f: \mathbb{N} \rightarrow \mathbb{N}$, definido por $f_t (m)= 2 \uparrow^{m} t$,

donde "$\uparrow$" es Knuth de la flecha hacia arriba notación (que pueden ser definidos de forma recursiva - como me parece que no puede llegar rápidamente con una línea de referencia para este definición recursiva $x\uparrow^{0}t=x\cdot t,\ x\uparrow^{m}0=1$ (si $m \neq 0$), $\ x\uparrow^{m+1}\left(t+1\right)=x\uparrow^{m}\left(x\uparrow^{m+1}t\right)$)

Mi pregunta es, si esta función es primitiva recursiva para todos los $t \in \mathbb{N}$. Para los valores de $t=0,1 \dots$ obtenemos $f_0 (m)=$ sgn$(x)$, $f_1 (m)=x\uparrow^{m} 1,\ \dots $ así que supongo, ya que estos son primitivas, funciones recursivas, que es primitiva recursiva para todos los $t \in \mathbb{N}$.

(Parece obvio que una prueba por inducción es necesario, pero me parece que no puede averiguar el paso de inducción:

Suponiendo que $f_t (m)$ es primitiva recursiva, entonces tenemos que mostrar que $f_{t+1} (m) $ es primitiva recursiva así. Mi idea era mostrar esto mediante la definición de funciones recursivas primitivas, es decir, mediante el uso de primitivas de recursividad:

$f_{t+1} (0)= 1 $ que es primitiva recursiva.

$f_{t+1} (m+1)= 2 \uparrow^{m+1} (t+1)=2 \uparrow^{m} (2 \uparrow^{m+1} t)$, pero el problema es que no puedo usar la hipótesis de inducción para demostrar que $2 \uparrow^{m} (2 \uparrow^{m+1} t)$ es una primitiva de la función recursiva, ya que $ (2 \uparrow^{m+1} t)>t$.)

Cualquier ayuda sería muy apreciada.

EDITAR (En respuesta a chandok la respuesta; porque esto no habría cabido en los comentarios):

Lo siento, que aún no tengo, pero no estoy seguro, si puedo modificar la prueba de que la función de Ackermann no es primitiva recursiva, para satisfacer las necesidades de mi función de $f_3$. Si yo quiero probar el closedness en virtud de la composición, es decir, dadas las funciones $h:\mathbb{N}^l \rightarrow \mathbb{N}$$g:\mathbb{N}^k \rightarrow \mathbb{N}$, que tienen la propiedad de que:

$\exists N_1 \ \forall n_1,\ldots,n_{l}>N_1$ tal que $h(n_1 ,\ldots ,n_{l})<2 \uparrow^{n_1 + \ldots + n_{l}} 3$

y

$\forall i \in \left\{1,\ldots,l \right\} \ \exists N_{i+1} \ \forall n_1,\ldots,n_{k}>N_{i+1} $ tal que $g_i(n_1, \ldots ,n_{k})<2 \uparrow^{n_1 + \ldots + n_{k}} 3$

entonces existe un $N$ tal que $\forall n_1,\ldots,n_{k}>N$ también debemos tener, que $t(n_1,\ldots,n_k):=f(g_1(n_1,\ldots ,n_k),\ldots ,g_l(n_1,\ldots,n_k))<2 \uparrow^{n_1 + \ldots + n_{k}} 3$

puedo ejecutar en problemas: En el intento de demostrar la afirmación anterior, que de alguna manera tienen que hacer uso de las propiedades antes mencionadas. Pero no puedo usar el "boudedness" de $h$ porque, porque no puedo controlar la cantidad de las funciones de $g_i$ crecer - si no hay valores de $n_1,\ldots ,n_k$ de manera tal que cada una de las $g_i$'s crecer por encima de $N_1$, entonces yo no puedo hacer uso de $h$'s propiedades. Tal vez hay alguna otra manera de probar la closedness en virtud de la composición, pero no lo veo. .

Answer 1

Ok yo,ve por fin se ha solucionado, gracias a una pista (es decir, aplicar el lema) alguien me dio. La solución es bastante corto, si tenemos este lema en la mano:

Lema: $\forall y\geqslant3 \ \forall n \in \mathbb{N}: 2\uparrow^{n+1} y\geqslant 2 \uparrow^n (y+1)$

Esto puede ser demostrado fácilmente por inducción.

Lo voy a probar ahora, es que el $2 \uparrow^n 4$ no es primitiva recursiva (de ahora en adelante abreviado como "p.r."): Supongamos $2 \uparrow^n 4$ sería p.r. A continuación, $2 \uparrow^{2n} 4$ p.r. como una composición de p.r. funciones.

Si pensamos de nuevo a la prueba, que la función de Ackermann no es p.r., podemos recordar que hemos tenido este obligado, que cada p.r. de la función a cumplir, a saber, (en nuestro caso ahora):

$\exists N \in \mathbb{N} \ \forall n \geqslant N: \ 2 \uparrow^{2n} 4 \leqslant 2 \uparrow ^N (n+3)$.

Elija $n=N$. Luego tenemos la $ 2 \uparrow^{2N} 4 \leqslant 2 \uparrow^N (N+3)$.

Aplicar el lema anterior $N$ veces, para obtener:

$ 2 \uparrow^{N} (N+4) \leqslant 2 \uparrow^{2N} 4 \leqslant 2 \uparrow^N (N+3)$. Contradicción, porque $ 2 \uparrow^{N} (N+4) > 2 \uparrow^N (N+3)$.

Todavía me sorprendo (y levemente molesto) ¿cuánto tiempo llevo en este problema y lo corto que era, en fin...

P. S. yo todavía estaría interesado, si alguien tenía otra prueba, tal vez por la gestión de modificar, no obstante, la prueba de que la función de Ackermann no es p.r. ...

Answer 2

Para cualquier $t \ge 3$, su función $f_t$ no es primitiva recursiva.

Usted probablemente puede demostrar que la misma manera como de Ackermann función: demostrar por inducción que cualquier $k$-% de función primitiva recursiva ary $f$, usted tiene $\forall t \ge 3, \exists n, \forall n_1 \ldots n_k, (n_1 + \ldots + n_k \ge n \implies f(n_1,\ldots n_k) \lt f_t(n_1 + \ldots + n_k))$