Untergrenze für die Anzahl der Orakelaufrufe zur Lösung von

Ich bin auf die folgende Frage gestoßen, die eine einfache Übung ist (Spoiler unten).

Wir erhalten Instanzen des Stoppproblems (dh TMs ), und wir müssen genau entscheiden, welche von ihnen auf anhalten . Das heißt, wir müssen ausgeben . Wir bekommen ein Orakel für das Problem des Anhaltens, aber wir müssen es nur minimal verwenden.$n$$M_1,...,M_n$$\epsilon$$\{i: M_i\text{ halts on }\epsilon\}$

Es ist nicht schwer zu zeigen, dass dies mit -Aufrufen möglich ist.$\log (n+1)$

Meine Frage ist: Können wir eine Untergrenze beweisen? Gibt es Grund zu der Annahme, dass eine solche Bindung sehr schwer zu finden sein wird?

Die Antwort auf die Frage selbst (Spoiler, Schwebemaus):

Betrachten Sie den Fall von $3$ TMs. Wir können ein TM konstruieren $H_2$, das $M_1,M_2,M_3$ parallel läuft und anhält, wenn mindestens zwei von ihnen anhalten (andernfalls bleibt es stecken). In ähnlicher Weise können wir ein TM konstruieren $H_1$, das anhält, wenn mindestens einer von ihnen anhält. Wir können dann das Orakel auf $H_2$ . Wenn es anhält, können wir die Maschinen parallel laufen lassen und warten, bis eine anhält. Wir können dann das Orakel beim letzten nennen. Wenn das Orakel "Nein" sagt, führen wir das Orakel auf $H_1$. Wenn es anhält, lassen wir die Maschinen laufen, bis eine anhält, und es ist die einzige, die anhält. Wenn $H_1$ nicht anhält, hält keiner von ihnen an. Die Erweiterung auf $n$ Maschinen ist einfach.

Die erste Beobachtung zu dieser Frage ist, dass es unmöglich erscheint, sie mit informationstheoretischen Werkzeugen zu lösen, da wir uns entscheidend auf unsere Fähigkeit verlassen, Informationen zu erhalten, indem wir die Maschinen ohne Orakel betreiben.

Das Ergebnis finden Sie in

• Beigel, R., Gasarch, WI, Gill, J. und Owings, J. Terse, superterse und wortreiche Mengen . Informieren. und Comput. 103 (1993), Nr. 1, 68–85.

Ihr Beweis zeigt tatsächlich, dass Ihr Problem nicht mit weniger als Abfragen an eine beliebige Menge X gelöst werden kann , geschweige denn mit dem Stoppproblem selbst. Bei einigen Notationen wird Ihr Problem manchmal als C K n oder C H A L T n bezeichnet (abhängig von Ihrer bevorzugten Notation für das Stoppproblem).$\log_2 n$$X$$C_n^K$$C_n^{HALT}$

Zu diesem und vielen verwandten Ergebnissen siehe auch:

• Diese Umfrage von Gasarch

• Das Buch Bounded Queries in Recursion Theory von Gasarch und Martin.

EDIT: Das Argument, mit dem ich geantwortet hatte, war nicht falsch, aber es war ein bisschen irreführend, da es nur zeigte, dass die Obergrenze für einige eng sein musste (was eigentlich trivial ist, da es eng sein muss, wenn n = 2 und die Grenze ist 1).$n$$n=2$

Hier ist ein genaueres Argument. Es zeigt, dass, wenn die Obergrenze von für ein bestimmtes n locker ist , für alle n die Anzahl der erforderlichen Orakelaufrufe O ( 1 ) ist .$\log_2 n$$n$ $n$$O(1)$

(Sicher ist es nicht , also ist die Obergrenze nie locker! Aber ich beweise das hier nicht wirklich, und angesichts der anderen Antwort auf das Problem scheint es nicht wert zu sein, es zu verfolgen.)$O(1)$

Betrachten Sie das Problem der Berechnung der maximalen Leistung :

Berechnen Sie bei einem Tupel ( M 1 , … , M n ) von Turing-Maschinen die maximale Leistung (der Turing-Maschinen, die anhalten, wenn sie auf ϵ ausgeführt werden ). Wenn keiner von ihnen anhält, geben Sie 0 zurück.$n$$(M_1,\ldots,M_n)$$\epsilon$

In Abhängigkeit von die zur Berechnung dieser Funktion erforderliche Worst-Case-Anzahl von Orakelaufrufen der Anzahl, die erforderlich ist, um zu entscheiden, welche von n bestimmten Maschinen anhalten. (Wenn ich weiß, welche Maschinen anhalten, kann ich leicht die maximale Ausgabe berechnen. Wenn ich umgekehrt wissen möchte, welche Maschinen anhalten, kann ich gemäß der Konstruktion in der Problemstellung Maschinen { M ′ i } ( i = 1 , 2) erstellen , … , N ) wobei M ' i alle n gegebenen Maschinen parallel laufen lässt , dann anhält und i ausgibt$n$$n$$\{M'_i\}$ $(i=1,2,\ldots,n)$$M'_i$$n$$i$wenn von ihnen jemals aufhöre. Die maximale Ausgabe gibt mir die Nummer an, die anhält. Daraus kann ich genau berechnen, welcher Halt.)$i$

Nun sei die kleinste ganze Zahl n (falls vorhanden), so dass Folgendes gilt:$n_0$$n$

Mit Orakelaufrufen kann man die maximale Leistung von n gegebenen Maschinen berechnen . (Das heißt, die Obergrenze ist für n nicht eng .)$C(n) = \max\{k \in \mathbb{Z} : 2^k < n\}$$n$$n$

Klar , weil C ( 1 ) = - 1 . Tatsächlich ist n 0 > 2 auch, weil C ( 2 ) = 0 ist , aber es ist unentscheidbar, die maximale Ausgabe von 2 gegebenen Maschinen (ohne Orakelaufrufe) zu berechnen . Betrachten Sie nun ein größeres n :$n_0>1$$C(1) = -1$$n_0>2$$C(2) = 0$$2$$n$

Behauptung: Wenn endlich ist, kann man für jedes n die maximale Ausgabe von n gegebenen Maschinen in C ( n 0 ) Orakelaufrufen berechnen . $n_0$$n$$n$$C(n_0)$(Beachten Sie, dass wenn endlich ist, C ( n 0 ) = O ( 1 ) ist .)$n_0$$C(n_0) = O(1)$

Beweis. . Wir beweisen es durch Induktion auf . Die Basisfälle sind n ≤ n 0 , die per Definition von n 0 und C gelten .$n$$n\le n_0$$n_0$$C$

$Q_0$$n_0$$C(n_0)$

$n>n_0$$n$$M_1,\ldots, M_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$$o_i$$i$$i=1,\ldots,n'$$M'_i$$Q_0$

$M'_i$$\epsilon$

1. $Q_0$$n_0$$(M_1,\ldots,M_{n_0})$$o_i$
2. $o_i$
3. $h_i$$Q_0$
4. $n_0$$(M_1,\ldots,M_{n_0})$$h_i$$h_i$

$n$$n_0$$M_1,\ldots,M_{n_0}$$n'< n_0$$M'_1,\ldots,M'_{n'}$$n-(n_0-n') < n$Maschinen. (Beachten Sie, dass das Orakel vor dem Rekursieren nicht aufgerufen wird, sodass das Orakel erst aufgerufen wird, wenn der Basisfall erreicht ist.)

$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'$$(M'_1,\ldots,M'_{n'})$$n_0$