Dolna granica liczby wezwań wyroczni do rozwiązania przypadków problemu zatrzymania

Spotkałem następujące pytanie, które jest łatwym ćwiczeniem (spoiler poniżej).

Dostajemy wystąpień problemu z zatrzymaniem (np. TM ) i musimy dokładnie zdecydować, które z nich zatrzymają się na . Oznacza to, że musimy . Dostajemy wyrocznię za problem zatrzymania, ale musimy go użyć minimalną liczbę razy.$n$$M_1,...,M_n$$\epsilon$$\{i: M_i\text{ halts on }\epsilon\}$

Nie jest trudno pokazać, że można tego dokonać za pomocą wywołań .$\log (n+1)$

Moje pytanie brzmi: czy możemy udowodnić dolną granicę? Czy istnieje powód, by podejrzewać, że takie ograniczenie będzie bardzo trudne do znalezienia?

Odpowiedź na samo pytanie (spoiler, kursor myszy):

Rozważ przypadek baz TM. Możemy zbudować TM która równolegle i zatrzymuje się, jeśli przynajmniej dwa z nich zatrzymają się (w przeciwnym razie utknie). Podobnie możemy zbudować TM która zatrzyma się, jeśli przynajmniej jedna z nich się zatrzyma. Następnie możemy wezwać wyrocznię na . Jeśli się zatrzyma, możemy uruchomić maszyny równolegle i poczekać, aż jedna się zatrzyma. Następnie możemy zadzwonić do wyroczni w ostatnim. Jeśli wyrocznia mówi „nie”, to uruchamiamy wyrocznię na . Jeśli się zatrzyma, wtedy uruchamiamy maszyny, aż się zatrzyma, i tylko ta się zatrzyma. Jeśli się nie zatrzyma, żaden z nich się nie zatrzyma. Rozszerzenie tego na maszyn jest łatwe.$3$$H_2$$M_1,M_2,M_3$$H_1$$H_2$$H_1$$H_1$$n$

Pierwsze spostrzeżenie na temat tego pytania jest takie, że wydaje się niemożliwe do rozwiązania za pomocą narzędzi teoretycznych, ponieważ polegamy przede wszystkim na naszej zdolności do uzyskiwania informacji przez uruchamianie maszyn bez wyroczni.

Wynik można znaleźć w

• Zestawy Beigel, R., Gasarch, WI, Gill, J. i Owings, J. Terse, superterse i verbose . Poinformować. i Comput. 103 (1993), nr. 1, 68–85.

Ich dowód w rzeczywistości pokazuje, że problemu nie można rozwiązać za pomocą mniej niż zapytań do dowolnego zestawu , nie mówiąc już o samym problemie zatrzymania. W przypadku niektórych notacji problem jest czasami oznaczany jako lub (w zależności od ulubionej notacji dotyczącej problemu zatrzymania).$\log_2 n$$X$$C_n^K$$C_n^{HALT}$

Aby zobaczyć ten i wiele powiązanych wyników, zobacz także:

• Ta ankieta przeprowadzona przez Gasarch

• Książka Bounded Queries in Recursion Theory autorstwa Gasarcha i Martina.

EDYCJA: Argument, na który odpowiedziałem, nie był zły, ale był nieco mylący, ponieważ pokazał tylko, że górna granica musiała być ciasna dla jakiegoś (co jest tak naprawdę trywialne, ponieważ musi być ciasna, gdy a granica wynosi 1).$n$$n=2$

Oto bardziej precyzyjny argument. Pokazuje, że jeśli górna granica jest luźna dla dowolnego konkretnego , to dla wszystkich wymagana liczba wywołań wyroczni wynosi .$\log_2 n$$n$ $n$$O(1)$

(Z pewnością nie jest to , więc górna granica nigdy nie jest luźna! Ale tak naprawdę nie udowadniam, że tutaj, a biorąc pod uwagę inną odpowiedź na problem, nie warto tego robić).$O(1)$

Rozważ problem obliczania maksymalnej wydajności :

Biorąc pod uwagę -tuple M_1 maszyn Turinga, oblicz maksymalną moc wyjściową (maszyn Turinga, które zatrzymają się, jeśli zostaną uruchomione na ). Jeśli żaden z nich się nie zatrzyma, zwróć 0.$n$$(M_1,\ldots,M_n)$$\epsilon$

W zależności od liczby najgorszy przypadek wywołań wyroczni wymaganych do obliczenia tej funkcji jest taki sam, jak liczba wymagana do podjęcia decyzji, które danych maszyn ma się zatrzymać. (Jeśli wiem, które maszyny się zatrzymają, mogę łatwo obliczyć maksymalną moc wyjściową. I odwrotnie, jeśli chcę wiedzieć, które maszyny się zatrzymują, postępując zgodnie z konstrukcją w problemu, mogę konstruować maszyny gdzie obsługuje wszystkie danych maszyn równolegle, a następnie zatrzymuje się i wyprowadza jeśli kiedykolwiek z nich się zatrzyma. Maksymalna wydajność powie mi liczbę, która się zatrzymała. Na tej podstawie mogę obliczyć który dokładnie się zatrzyma.)$n$$n$$\{M'_i\}$ $(i=1,2,\ldots,n)$$M'_i$$n$$i$$i$

Teraz niech będzie najmniejszą liczbą całkowitą (jeśli istnieje) taką, że następujące:$n_0$$n$

Używając wywołań oracle, można obliczyć maksymalną wydajność danych maszyn. (To znaczy, górna granica nie jest ciasna dla .)$C(n) = \max\{k \in \mathbb{Z} : 2^k < n\}$$n$$n$

Wyraźnie , ponieważ . W rzeczywistości również, ponieważ , ale nie jest możliwe obliczenie maksymalnej wydajności danych maszyn (bez wywołań wyroczni). Teraz rozważ większe :$n_0>1$$C(1) = -1$$n_0>2$$C(2) = 0$$2$$n$

Twierdzenie: Jeśli jest skończone, to dla dowolnego można obliczyć maksymalną wydajność danych maszyn w wywołaniach oracle. $n_0$$n$$n$$C(n_0)$(Zauważ, że jeśli jest skończone, to .)$n_0$$C(n_0) = O(1)$

Dowód. . Udowadniamy to przez indukcję na . Przypadki bazowe są , które posiadają z definicji i .$n$$n\le n_0$$n_0$$C$

Niech będzie TM, która, biorąc pod uwagę dowolne maszyny Turinga , oblicza maksymalną moc wyjściową, używając tylko wywołań do wyroczni.$Q_0$$n_0$$C(n_0)$

Napraw dowolne . Biorąc pod uwagę dowolne maszyn , oblicz maksymalną moc w następujący sposób.$n>n_0$$n$$M_1,\ldots, M_n$

Skoncentruj się na pierwszych maszynach . Rozważ uruchomienie na tych komputerach . Zauważ, że wykonuje do wyroczni, i istnieje tylko możliwych odpowiedzi wyroczni na te wywołania. Zauważ, że z definicji . Niech oznacza tą możliwą odpowiedź. Dla każdego maszynę która symuluje na tych komputerach w następujący sposób:$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 (na wejściu ):$M'_i$$\epsilon$

1. Symuluj na maszynach , ale zamiast wywoływać wyrocznię, , że wyrocznia odpowiada zgodnie z .$Q_0$$n_0$$(M_1,\ldots,M_{n_0})$$o_i$
2. Ta symulacja może się nie zatrzymać (np. Jeśli nie jest tym, co rzeczywiście powróciłaby wyrocznia).$o_i$
3. Jeśli symulacja się zatrzyma, niech będzie maksymalnym wyjściem, które według zostanie podane.$h_i$$Q_0$
4. Dovetail wszystkie maszyny . Jeśli jeden z nich kiedykolwiek wyprowadza , zatrzymaj i .$n_0$$(M_1,\ldots,M_{n_0})$$h_i$$h_i$

Teraz, w podanej sekwencji maszyn, zamień pierwsze maszyny na te maszyny . Zwraca wartość obliczoną przez rekurencję w tej sekwencji maszyn. (Zauważ, że wyrocznia nie jest wywoływana przed powtórzeniem, więc wyrocznia jest wywoływana dopiero po osiągnięciu przypadku podstawowego).$n$$n_0$$M_1,\ldots,M_{n_0}$$n'< n_0$$M'_1,\ldots,M'_{n'}$$n-(n_0-n') < n$

Oto dlaczego to obliczenie jest poprawne. Dla , że jest `` poprawną '' odpowiedzią wyroczni na zapytania, zatrzyma się i da poprawną maksymalną wydajność oryginalnych maszyn . Zatem maksymalna wydajność maszyn to co najmniej maksymalna wydajność maszyn . Z drugiej strony, w kroku 4 żaden nie może dać wyniku większego niż maksymalny wynik . Tak więc, dane wyjściowe maksimum maszyny$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'})$ równa się maksymalnej wydajności maszyn , które zastępują. CO BYŁO DO OKAZANIA$n_0$