Limite inférieure du nombre d'appels oracle pour résoudre

J'ai rencontré la question suivante, qui est un exercice facile (spoiler ci-dessous).

On nous donne instances du problème d'arrêt (ie TMs ), et nous devons décider exactement lequel s'arrêtera sur . Autrement dit, nous devons afficher . On nous donne un oracle pour le problème d'arrêt, mais nous devons l'utiliser un nombre minimal de fois.$n$$M_1,...,M_n$$\epsilon$$\{i: M_i\text{ halts on }\epsilon\}$

Il n'est pas difficile de montrer que cela peut être fait avec des appels .$\log (n+1)$

Ma question est: pouvons-nous prouver une borne inférieure? Y a-t-il des raisons de soupçonner qu'une telle limite sera très difficile à trouver?

La réponse à la question elle-même (spoiler, hover mouse):

Prenons le cas de MT. Nous pouvons construire un TM qui exécute en parallèle et s'arrête si au moins deux d'entre eux s'arrêtent (sinon il reste bloqué). De même, nous pouvons construire un TM qui s'arrête si au moins l'un d'eux s'arrête. On peut alors appeler l'oracle sur . S'il s'arrête, nous pouvons exécuter les machines en parallèle et attendre que l'une s'arrête. Nous pouvons alors appeler l'oracle sur le dernier. Si l'oracle dit «non», nous exécutons l'oracle sur . Si ça s'arrête, alors on fait tourner les machines jusqu'à ce qu'on s'arrête, et c'est la seule qui s'arrête. Si ne s'arrête pas, aucun d'eux ne s'arrête. L'extension à machines est facile.$3$$H_2$$M_1,M_2,M_3$$H_1$$H_2$$H_1$$H_1$$n$

La première observation à propos de cette question est qu'il semble impossible de résoudre en utilisant des outils théoriques de l'information, car nous comptons essentiellement sur notre capacité à obtenir des informations en faisant fonctionner les machines sans l'oracle.

Le résultat se trouve dans

• Ensembles Beigel, R., Gasarch, WI, Gill, J. et Owings, J. Terse, superterse et verbose . Informer. et Comput. 103 (1993), no. 1, 68–85.

Leur preuve montre en fait que votre problème ne peut pas être résolu avec moins de requêtes vers n'importe quel ensemble , sans parler du problème d'arrêt lui-même. Pour certaines notations, votre problème est parfois noté ou (selon votre notation préférée pour le problème d'arrêt).X C K n C H A L T$\log_2 n$$X$$C_n^K$$C_n^{HALT}$

Pour cela et de nombreux résultats connexes, voir également:

• Cette enquête de Gasarch

• Le livre Bounded Queries in Recursion Theory de Gasarch et Martin.

EDIT: L'argument auquel j'avais répondu n'était pas faux, mais il était un peu trompeur, en ce qu'il montrait seulement que la limite supérieure devait être serrée pour certains (ce qui est en fait trivial, car il doit être serré lorsque et la limite est 1).n = $n$$n=2$

Voici un argument plus précis. Il montre que si la limite supérieure de est lâche pour tout particulier , alors pour tous le nombre d'appels oracle requis est .n n O ( 1 $\log_2 n$$n$ $n$$O(1)$

(Ce n'est sûrement pas , donc la borne supérieure n'est jamais lâche! Mais je ne prouve pas réellement que ici, et étant donné l'autre réponse au problème, cela ne semble pas valoir la peine d'être poursuivi.)$O(1)$

Considérez le problème du calcul de la sortie maximale :

Étant donné un -tuple des machines Turing, calculez la sortie maximale (des machines Turing qui s'arrêtent, si elles sont exécutées sur ). Si aucun d'entre eux ne s'arrête, retournez 0.( M 1 , … , M n ) $n$$(M_1,\ldots,M_n)$$\epsilon$

En fonction de , le nombre le plus défavorable d'appels oracle requis pour calculer cette fonction est le même que le nombre requis pour décider laquelle des n machines données arrêter. (Si je sais quelles machines s'arrêtent, je peux facilement calculer la sortie maximale. Inversement, si je veux savoir quelles machines s'arrêtent, en suivant la construction de l'énoncé du problème, je peux construire des machines { M ′ i } ( i = 1 , 2 , … , N ) où M ′ i exécute toutes les n machines données en parallèle, puis s'arrête et produit $n$$n$$\{M'_i\}$ $(i=1,2,\ldots,n)$$M'_i$$n$$i$si leur HALT jamais. La sortie maximale me dira le nombre qui s'arrête. À partir de cela, je peux calculer exactement l'arrêt.)$i$

Maintenant, soit le plus petit entier n (le cas échéant) tel que ce qui suit soit vrai:$n_0$$n$

n $C(n) = \max\{k \in \mathbb{Z} : 2^k < n\}$$n$$n$

Clairement , car . En fait, également, car , mais il est indécidable de calculer la sortie maximale de machines données (sans appels Oracle). Considérons maintenant un plus grand :C ( 1 ) = - 1 n 0 > 2 C ( 2 ) = 0 2 $n_0>1$$C(1) = -1$$n_0>2$$C(2) = 0$$2$$n$

: si est fini, alors, pour tout , on peut calculer la sortie maximale de machines données dans appels oracle. n n C ( n 0$n_0$$n$$n$$C(n_0)$(Notez que si est fini, alors .) C( n 0 )=O(1$n_0$$C(n_0) = O(1)$

Preuve. . Nous le prouvons par récurrence sur . Les cas de base sont , qui détiennent par définition et .n ≤ n 0 n 0$n$$n\le n_0$$n_0$$C$

Soit la MT qui, compte tenu des machines de Turing, calcule la sortie maximale en utilisant uniquement les appels vers l'oracle.n 0 C ( n 0$Q_0$$n_0$$C(n_0)$

Fixez . Étant donné les machines , calculez la sortie maximale comme suit. n M 1 , … , M $n>n_0$$n$$M_1,\ldots, M_n$

Concentrez-vous sur les premières machines. Pensez à exécuter sur ces machines. Notez que fait des à l'oracle, et il n'y a que réponses possibles par l'oracle à ces appels. Notez que par définition . Soit la ème réponse possible. Pour chaque , construisons une machine qui simule sur ces machines comme suit: Q 0 n 0 Q 0 C ( n 0 ) n ′ = 2 C ( n 0 ) n ′ = 2 C ( n 0 ) < n 0 o i i i = 1 , … , n ′ M ′ i Q $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$$o_i$$i$$i=1,\ldots,n'$$M'_i$$Q_0$

TM (en entrée ):$M'_i$$\epsilon$

1. Simuler sur les machines , mais au lieu d'appeler l'oracle, supposons que les répond oracle selon .n 0 ( M 1 , … , M n 0 ) o $Q_0$$n_0$$(M_1,\ldots,M_{n_0})$$o_i$
2. Cette simulation pourrait ne pas s'arrêter (par exemple si n'est pas ce que l'oracle retournerait réellement).$o_i$
3. Si la simulation s'arrête, soit la sortie maximale qui, selon , serait donnée.Q $h_i$$Q_0$
4. En queue d'aronde toutes les machines . Si l'un d'eux sort jamais , arrêtez et . ( M 1 , … , M n 0 ) h i h $n_0$$(M_1,\ldots,M_{n_0})$$h_i$$h_i$

Maintenant, dans la séquence donnée de machines, remplacez les premières machines par ces machines . Renvoie la valeur calculée en récursif sur cette séquence de machines. (Notez que l'oracle n'est pas appelé avant la récurrence, de sorte que l'oracle n'est appelé qu'une fois le cas de base atteint.)$n$$n_0$$M_1,\ldots,M_{n_0}$$n'< n_0$$M'_1,\ldots,M'_{n'}$$n-(n_0-n') < n$

Voici pourquoi ce calcul est correct. Pour le tel que est la réponse `` correcte '' de l'oracle aux requêtes, s'arrêterait et donnerait la sortie maximale correcte des machines d'origine. Ainsi, la sortie maximale des machines est au moins la sortie maximale des machines . Par contre, à l'étape 4, aucun ne peut donner une sortie supérieure à la sortie maximale de . Ainsi, la sortie maximale des machineso i Q 0 M ′ i n 0 n ′ ( M ′ 1 , … , M ′ n ′ ) n 0 ( M 1 , … , M n 0 ) M ′ i ( M 1 , … , M n 0 ) n ′ ( M ′ 1 , … , M ′ $i$$o_i$$Q_0$$M'_i$$n_0$$n'$$(M'_1,\ldots,M'_{n'})$$n_0$$(M_1,\ldots,M_{n_0})$$M'_i$$(M_1,\ldots,M_{n_0})$$n'$N $(M'_1,\ldots,M'_{n'})$ est égal à la sortie maximale des machines qu'ils remplacent. QED$n_0$