Límite inferior en el número de llamadas de Oracle para resolver instancias del problema de detención

Encontré la siguiente pregunta, que es un ejercicio fácil (spoiler a continuación).

Se nos dan instancias del problema de detención (es decir ), y debemos decidir exactamente cuál de ellas se detendrá en . Es decir, necesitamos generar . Se nos da un oráculo para el problema de detención, pero tenemos que usarlo un número mínimo de veces.M 1 , . . . , M n ϵ { i : M i se  detiene en  ϵ $n$$M_1,...,M_n$$\epsilon$$\{i: M_i\text{ halts on }\epsilon\}$

No es difícil demostrar que se puede hacer con llamadas .$\log (n+1)$

Mi pregunta es: ¿podemos probar un límite inferior? ¿Hay alguna razón para sospechar que tal límite será muy difícil de encontrar?

La respuesta a la pregunta en sí (spoiler, mouse de desplazamiento):

Considere el caso de TM. Podemos construir un TM que ejecuta en paralelo y se detiene si al menos dos de ellos se detienen (de lo contrario, se atasca). Del mismo modo, podemos construir un TM que se detenga si al menos uno de ellos se detiene. Entonces podemos llamar al oráculo en . Si se detiene, podemos ejecutar las máquinas en paralelo y esperar a que se detenga. Entonces podemos llamar al oráculo en el último. Si el oráculo dice "no", ejecutamos el oráculo en . Si se detiene, ejecutamos las máquinas hasta que una se detiene, y es la única que se detiene. Si no se detiene, ninguno de ellos se detendrá. Ampliar esto a máquinas es fácil.H 2 M 1 , M 2 , M 3 H 1 H 2 H 1 H 1$3$$H_2$$M_1,M_2,M_3$$H_1$$H_2$$H_1$$H_1$$n$

La primera observación sobre esta pregunta es que parece imposible de resolver utilizando herramientas teóricas de la información, ya que confiamos de manera crucial en nuestra capacidad de obtener información ejecutando las máquinas sin el oráculo.

El resultado se puede encontrar en

• Beigel, R., Gasarch, WI, Gill, J. y Owings, J. Terse, superterse y conjuntos detallados . Informar. y Comput. 103 (1993), no. 1, 68-85.

De hecho, su prueba muestra que su problema no puede resolverse con menos de consultas a cualquier conjunto , y mucho menos al problema de detención en sí. Para alguna notación, su problema a veces se denota o (dependiendo de su notación favorita para el problema de detención).X C K n C H A L T$\log_2 n$$X$$C_n^K$$C_n^{HALT}$

Para este y muchos resultados relacionados, vea también:

• Esta encuesta realizada por Gasarch

• El libro Bounded Queries in Recursion Theory de Gasarch y Martin.

EDITAR: El argumento con el que había respondido no era incorrecto, pero fue un poco engañoso, ya que solo mostraba que el límite superior tenía que estar ajustado para alguna (lo que en realidad es trivial, ya que tiene que ser ajustado cuando n = 2 y el límite es 1).$n$$n=2$

Aquí hay un argumento más preciso. Muestra que si el límite superior de está suelto para cualquier n en particular , entonces para todos n el número de llamadas al oráculo requerido es O ( 1 ) .$\log_2 n$$n$ $n$$O(1)$

(Sin duda, es no , por lo que el límite superior no está suelto! Pero en realidad no prueba que aquí, y se le dio la otra respuesta al problema, no parece que vale la pena.)$O(1)$

Considere el problema de calcular la salida máxima :

Dada una -tupla ( M 1 , ... , M n ) de las máquinas de Turing, calcule la salida máxima (de las máquinas de Turing que se detienen, si se ejecutan en ϵ ). Si ninguno de ellos se detiene, devuelve 0.$n$$(M_1,\ldots,M_n)$$\epsilon$

Como una función de , el número del peor caso de las llamadas de Oracle requiere para calcular esta función es el mismo que el número requerido para decidir cuál de n máquinas dadas alto. (Si sé qué máquinas se detienen, puedo calcular fácilmente la salida máxima. Por el contrario, si quiero saber qué máquinas se detienen, después de la construcción en el enunciado del problema, puedo construir máquinas { M ′ i } ( i = 1 , 2 , ... , n ) , donde M ' i ejecuta todos los n máquinas dadas en paralelo, a continuación, se detiene y la salida $n$$n$$\{M'_i\}$ $(i=1,2,\ldots,n)$$M'_i$$n$$i$si de ellos ha detenido. La salida máxima me dirá el número que se detiene. A partir de eso puedo calcular exactamente qué detener).$i$

Ahora, deje que sea ​​el número entero más pequeño n (si lo hay) de modo que se cumpla lo siguiente:$n_0$$n$

Usando llamadas al oráculo, se puede calcular la salida máxima de máquinas dadas. (Es decir, el límite superior no es ajustado para .)$C(n) = \max\{k \in \mathbb{Z} : 2^k < n\}$$n$$n$

Claramente , porque . De hecho, n 0 > 2 también, porque C ( 2 ) = 0 , pero es indecidible calcular la salida máxima de 2 máquinas dadas (sin llamadas de oráculo). Ahora considere mayor n :C ( 1 ) = - $n_0>1$$C(1) = -1$$n_0>2$$C(2) = 0$$2$$n$

Reclamación: si es finito, entonces, para cualquier n , se puede calcular la salida máxima de n máquinas dadas en llamadas de oráculo C ( n 0 ) . $n_0$$n$$n$$C(n_0)$(Tenga en cuenta que si es finito, entonces C ( n 0 ) = O ( 1 ) .)$n_0$$C(n_0) = O(1)$

Prueba. . Lo probamos por inducción en . Los casos base son n ≤ n 0 , que mantenga por definición de n 0 y C .$n$$n\le n_0$$n_0$$C$

Deje que sea ​​la TM que, dadas las máquinas n 0 Turing, calcula la salida máxima utilizando solo llamadas C ( n 0 ) al oráculo.$Q_0$$n_0$$C(n_0)$

Arregle cualquier . Dadas las n máquinas M 1 , ... , M n , calcule la salida máxima de la siguiente manera.$n>n_0$$n$$M_1,\ldots, M_n$

Concéntrese en las primeras máquinas . Considere ejecutar Q 0 en estas máquinas n 0 . Tenga en cuenta que Q 0 hace llamadas C ( n 0 ) al oráculo, y solo hay n ′ = 2 C ( n 0 ) posibles respuestas del oráculo a estas llamadas. Tenga en cuenta que, por definición, n ′ = 2 C ( n 0 ) < n $M_1,\ldots,M_{n_0}$$Q_0$$n_0$$Q_0$$C(n_0)$$n' = 2^{C(n_0)}$$n' = 2^{C(n_0)} < n_0$. Let denota el i º posible respuesta. Para cada i = 1 , ... , n ′ , construya una máquina M ′ i que simule Q 0 en estas máquinas de la siguiente manera:$o_i$$i$$i=1,\ldots,n'$$M'_i$$Q_0$

TM (en la entrada ϵ ):$M'_i$$\epsilon$

1. Simule en las máquinas n 0 ( M 1 , ... , M n 0 ) , pero en lugar de llamar al oráculo, suponga que el oráculo responde de acuerdo con o i .$Q_0$$n_0$$(M_1,\ldots,M_{n_0})$$o_i$
2. Es posible que esta simulación no se detenga (por ejemplo, si no es lo que el oráculo realmente devolvería).$o_i$
3. Si se detiene la simulación, vamos sea la potencia máxima que Q 0 dice que sería dado.$h_i$$Q_0$
4. Haga cola de milano todas las máquinas ( M 1 , … , M n 0 ) . Si alguna de ellas emite h i , deténgase y emita h i .$n_0$$(M_1,\ldots,M_{n_0})$$h_i$$h_i$

Ahora, en la secuencia dada de máquinas, reemplace las primeras n 0 máquinas M 1 , ... , M n 0 por estas n ′ < n 0 máquinas M ′ 1 , ... , M ′ n ′ . Devuelve el valor calculado recurriendo en esta secuencia de n - ( n 0 - n ′ ) < $n$$n_0$$M_1,\ldots,M_{n_0}$$n'< n_0$$M'_1,\ldots,M'_{n'}$$n-(n_0-n') < n$máquinas. (Tenga en cuenta que el oráculo no se llama antes de recurrir, por lo que solo se llama una vez que se alcanza el caso base).

Aquí es por qué este cálculo es correcto. Para el tal que o i es la respuesta `` correcta '' del oráculo Q 0 a las consultas, M ′ me detendría y daría la salida máxima correcta de las máquinas n 0 originales . Así, la salida máxima de las máquinas n ' ( M ' 1 , ... , M ' n ' ) es al menos la salida máxima de las máquinas n 0 ( M 1 , ... $i$$o_i$$Q_0$$M'_i$$n_0$$n'$$(M'_1,\ldots,M'_{n'})$$n_0$ . Por otro lado, en el paso 4, no M ' i puede dar una salida que sea mayor que la salida máxima de ( M 1 , ... , M n 0 ) . Por lo tanto, la salida máxima de lasmáquinas n ' ( M ' 1 , ... , M ' n ' ) es igual a la salida máxima de lasmáquinas n 0 que reemplazan. QED$(M_1,\ldots,M_{n_0})$$M'_i$$(M_1,\ldots,M_{n_0})$$n'$$(M'_1,\ldots,M'_{n'})$$n_0$