¿Son recursivas primitivas hyperoperators?

Question

Pido disculpas si esta pregunta es muy básica. He leído que el de la función de Ackerman es el primer ejemplo de una computable pero NO es primitiva recursiva de la función. Hyperoperators parecen estar estrechamente relacionados con estas funciones, pero no estoy seguro de si todavía mantener la propiedad de ser NO es primitiva recursiva. Mi intuición es que lo son, pero no estoy seguro. Cualquier libro de texto o referencias a leer para obtener una mejor comprensión de esto va a ser muy apreciado (y una escalera de respuesta demasiado!).

NOTA: he leído esta relacionada con la pregunta, pero no me ayuda.

Answer 1

Si he entendido bien, sí.

Porque si sigue de la definición de hyperoperators definición.

$H_0(a,b):=S(b)$

es el sucesor de la función, y cada hyperoperation se define recursivamente a partir de la función sucesor:

(definición recursiva de $H_{n+1}$$H_n$)

$i)$ $H_{n+1}(a,0):=a_{n+1}$

$ii)$ $H_{n+1}(a,b+1):=H_n(a,H_{n+1}(a,b))$

Aquí $a_{n+1}$ es el valor inicial de la función cuando el argumento es $0$ y en el caso de hyporoperators tenemos que

$a_ {n+1}:= \begin{cases} a, & \text{if %#%#%} \\ 0, & \text{if %#%#% } \\ 1, & \text{if %#%#% } \\ \end{casos}$

Desde $n=0$ es el sucesor función y es básico primitivo rucursive función, tenemos que todos los hyperoperations (que se define a partir de $n=1$) son Primitve funciones recursivas.

Answer 2

(Elaboración de mi comentario a la aceptación de respuesta ...)

Para cada una de las $n \in \mathbb{N}$, $n$th hyperoperation $$H_n: \mathbb{N}^2 \to \mathbb{N}: (x,y) \mapsto H_n(x,y)$$ es primitiva recursiva.

Sin embargo, para cualquier entero constante $c\ge 2$, de las siguientes funciones no es primitiva recursiva:

$$\begin{align} f_c&: \mathbb{N} \to \mathbb{N}: n \mapsto H_n(c,n)\\ g_c&: \mathbb{N}^2 \to \mathbb{N}: (n,y) \mapsto H_n(c,y)\\ h&: \mathbb{N}^3 \to \mathbb{N}: (n,x,y) \mapsto H_n(x,y). \end{align}$$

Al $n$ está incluido como un argumento, la función crece demasiado rápido para ser primitiva recursiva.

E. g., $x\uparrow^n y\ $ es primitiva recursiva como una función de la $(x,y)$ fijos $n$, pero no es primitiva recursiva como una función de la $(n,y)$ fijos $x\ge 2$.

Esencialmente, estos resultados se demuestran en el Capítulo 13 de "la Computabilidad, Complejidad, y Lenguas" (1983) por Davis & Weyuker, y también esbozado en la Introducción a la Teoría de la Computabilidad por Zucker & Pretorius.