Funciones no computables de rápido crecimiento

Question

Un famoso 1962 papel de Tibor Radó muestra que la función "castor ocupado" $h$ (que calcula el número máximo de pasos para los que una máquina de Turing de parada con $n$ estados pueden correr por) satisface la propiedad

• (A) para toda función total computable $f\colon\mathbb{N}\to\mathbb{N}$ tenemos $h(n) \geq f(n)$ eventualmente (es decir, existe $N$ tal que para todo $n\geq N$ tenemos $h(n) \geq f(n)$ )

Ahora lo que es muy fácil de probar es el más débil

• (B) para toda función total computable $f\colon\mathbb{N}\to\mathbb{N}$ tenemos $h(n) \geq f(n)$ con una frecuencia infinita (es decir, para cada $N$ existe $n\geq N$ tal que $h(n) \geq f(n)$ )

(porque si hubiera una $f$ tal que $f(n)\geq h(n)$ eventualmente podríamos encontrar uno tal que $f(n)\geq h(n)$ siempre, y entonces podríamos resolver el problema de detención para $n$ máquinas de Turing de estado esperando como máximo $f(n)$ pasos).

Ahora bien, la prueba de Radó es bastante opaca, parece un poco de magia, no consigo averiguar la razón profunda por la que es capaz de demostrar (A) y no sólo (B): ¿es algo realmente específico de la función del castor ocupado, o hay algún truco general que permite derivar (A) de (B)? Entonces:

¿Realiza una función creciente $h$ que satisface (B) satisface automáticamente (A)? Si no es así, ¿hay alguna condición sencilla que podamos añadir para obtener (A) a partir de (B) y que "explique" la prueba de Radó?

Y, si las preguntas anteriores no lo hacen trivial:

¿Existen grados de Turing que contengan funciones $h$ que satisfaga (B) pero ninguna función que satisfaga (A)?

Answer 1

No he leído detenidamente la prueba de Radó, pero el siguiente camino hacia (A) parece ser bastante sencillo, al menos para los más ocupados salida función $BB_o$ , donde $BB_o(n)$ es el número máximo de 1 s que quedan en la cinta después de un $n$ -La máquina de estado termina:

Dejemos que $f$ sea cualquier función total computable. Entonces hay un número $m$ de manera que el programa

 1. X = m;
 2. X = f(X);
 3. X = X+1;
 4. output X

puede implementarse en una máquina con exactamente $m$ estados. (Básicamente se trata de observar que podemos construir el número $2^k$ utilizando $O(k)$ estados, por ejemplo). Además, podemos insertar cualquier número de X=X+1 entre los pasos 1 y 2, cada uno de los cuales cuesta exactamente un estado (es decir, moverse a la izquierda y escribir un 1 en la cinta). Así que el programa anterior se puede implementar en realidad en $m$ estados para todo suficientemente grande $m$ .

Ahora bien, si $f(m) \ge BB_o(m)$ para un número infinito de $m$ Entonces, uno de esos $m$ s debe ser suficientemente grande, pero eso lleva a una contradicción, porque la máquina aludida tiene $m$ estados, y así por definición $BB(m)$ debe ser como mínimo $f(m)+1$ .

Por lo tanto, debemos tener $f(n) < BB_o(m)$ finalmente.

Su objetivo es que la persona ocupada tiempo función, $BB_t(n)$ es el número máximo de pasos un $n$ -que puede tomar la máquina antes de terminar. Pero esto se reduce fácilmente al caso anterior: ya que $BB_t(n)\ge BB_o(n)$ una función que supera $BB_t(n)$ infinitamente a menudo también debe exceder $BB_o(n)$ infinitamente a menudo - lo que acabamos de ver es imposible para las funciones computables.

---

Para un $h$ que satisface (B) pero no (A) podemos tomar

$$ h(n) = \begin{cases} 42 & \text{if } n=0 \\ BB(n) & \text{if } h(n-1) < (n-1)^2 \\ h(n-1)+1 & \text{otherwise} \end{cases} $$

Entonces $h(n) < n^2$ infinitamente a menudo, así que $f(n)=n^2$ es un contraejemplo de (A).

Por otro lado $h(n)=BB(n)$ infinitamente a menudo, por lo que un $f$ que finalmente supera $h(n)$ superaría $BB(n)$ infinitamente a menudo, lo que es imposible por el argumento anterior.

Answer 2

Después de indagar un poco, puedo responder a la parte de los títulos de Turing en mi propia pregunta. Resulta que la condición (B) es, efectivamente, más débil que la condición (A) a nivel de grados de Turing. Más concretamente:

• Un título de Turing $\mathbf{a}$ es " hiperinmune "si hay un $\mathbf{a}$ -función computable $h$ que satisfaga (B), es decir, que no esté dominada por ninguna función computable  $f$ . (Véase, por ejemplo, Downey & Hirschfeldt, Aleatoriedad y complejidad algorítmica (Springer, 2010), definición 2.17.1 en la página 67, o Miller & Martin, "The Degrees of Hyperimmune Sets", Z. Matemáticas. Logik 14 (1968), corolario 1.1 en la p. 160).

• Un título de Turing $\mathbf{a}$ es satisface $\mathbf{a}'\geq 0''$ (cuando $\mathbf{a} \leq 0'$ esta condición se llama " alto ") si existe un $\mathbf{a}$ -función computable $h$ que satisfaga (A), es decir, que domine cualquier función computable  $f$ . (Véase, por ejemplo, Downey & Hirschfeldt, Aleatoriedad y complejidad algorítmica (Springer, 2010), teorema 2.33.7 en la página 97, o Martin, "Classes of Recursively Enumerable Sets and Degrees of Unsolvability", Z. Matemáticas. Logik 12 (1966), lemmata 1.1 y 1.2).

Así que mi pregunta era si existe un grado de Turing que satisfaga el primero pero no el segundo. Pero de hecho, cualquier grado computablemente enumerable que no sea $0$ es hiperinmune (este era esencialmente mi argumento de por qué el castor ocupado satisface (B): ver aquí lo que, de hecho, responde a mi pregunta, entre otras cosas), y no todos esos grados son altos (por ejemplo, existen grados de c.e. bajos).

Answer 3

(Publicando una segunda respuesta para mayor claridad porque esto se relaciona con una parte diferente de mi pregunta).

Inspirado en la obra de Henning Makholm responder Puedo demostrar la siguiente afirmación que no hace ninguna referencia a un modelo específico de computabilidad como las máquinas de Turing:

Dejemos que $\varphi_e$ sea una enumeración estándar de funciones parcialmente computables $\mathbb{N}^k\rightharpoonup\mathbb{N}$ El hecho crucial en la "norma" es que el teorema s-m-n se mantiene con la función de sustitución recursiva primitiva, es decir, existe $s$ primitiva recursiva tal que $\varphi_e(m,n) = \varphi_{s(e,m)}(n)$ .

Dejemos que $h\colon\mathbb{N}\to\mathbb{N}$ se define por $h(n) := \max\{\varphi_e(e) : 0\leq e\leq n \land \varphi_e(e)\downarrow\}$ . (Es bastante obvio que $h$ satisface (B).)

Por probar: De hecho, $h$ satisface (A), es decir, si $f\colon\mathbb{N}\to\mathbb{N}$ es computable entonces existe $N$ tal que $h(n) \geq f(n)$ para $n\geq N$ .

Prueba: Dejemos que $\gamma\colon\mathbb{N}\to\mathbb{N}$ sea la función diagonal de Ackermann. (Lo que necesitamos es que $\gamma$ es computable, creciente y eventualmente domina todas las funciones recursivas primitivas, es decir, satisface el análogo de (A) para las funciones recursivas primitivas  $f$ .)

Dejemos que $f\colon\mathbb{N}\to\mathbb{N}$ sea cualquier función computable. Queremos demostrar que $h(n) \geq f(n)$ para todos $n$ suficientemente grande. Definimos $g(k, j) := \max\{f(i) : 0\leq i\leq \gamma(k)\}$ (la variable $j$ se ignora). Sea $p$ sea un índice para  $g$ es decir, $g = \varphi_p$ .

Ahora tenemos $\varphi_{s(p,k)}(j) = \varphi_p(k,j) = g(k,j) = \max\{f(i) : 0\leq i\leq \gamma(k)\}$ (de nuevo, $j$ se ignora). Por lo tanto, si $n \geq s(p,k)$ y $i \leq \gamma(k)$ entonces $h(n) \geq f(i)$ . En particular, si $s(p,k) \leq n \leq \gamma(k)$ entonces $h(n) \geq f(n)$ .

Pero como $s(p,k+1)$ es una función de recursión primitiva de  $k$ existe $k_0$ de manera que si $k \geq k_0$ tenemos $\gamma(k) \geq s(p,k+1)$ . Entonces, si $n \geq s(p,k_0)$ es evidente que existe $k$ tal que $s(p,k) \leq n \leq \gamma(k)$ , lo que implica $h(n) \geq f(n)$ como se acaba de explicar. Esto demuestra que $h$ finalmente domina  $f$ . QED

Obsérvese que la prueba funciona al pie de la letra si definimos $h$ por $h(n) := \max\{\varphi_e(0) : 0\leq e\leq n \land \varphi_e(0)\downarrow\}$ (el argumento para $\varphi_e$ sólo está ahí porque a veces es molesto considerar y enumerar funciones computables parciales de $0$ argumentos).

Aplicando esto a las máquinas de Turing, dice que la función $h$ que mapea $n$ a la máxima salida posible de los entre los $n$ primeras máquinas de Turing que se detienen (para cualquier numeración "razonable"), domina finalmente cualquier función computable. Dado que la máxima salida de parada posible de la $n$ de las primeras máquinas de Turing es ciertamente, como máximo, igual a la máxima salida de parada posible de la máquina más $n$ -máquinas de Turing de estado, recuperamos el resultado de Radó sobre la función estándar del castor ocupado. Pero lo que me parece interesante de este planteamiento es que deja claro que necesitamos suponer muy poco en la numeración: para cualquier lenguaje de programación en el que la composición sea recursiva primitiva (a muy débil ), la máxima salida de parada posible del $n$ los primeros programas acabarán dominando cualquier función computable.

(¿Cómo me inspiré en la respuesta de Henning Makholm? Básicamente utiliza $\gamma(k) = 2^k$ al decir "podemos construir el número $2^k$ en $O(k)$ estados", algo que es suficiente para el caso de las máquinas de Turing y si nos limitamos a contar su número de estados: es este argumento clave de "arranque" el que no entendí en la prueba de Radó y que intenté explicitar más arriba).