W jaki sposób korzystanie z maszyn wyroczni Turinga nie prowadzi do sprzeczności?

W jaki sposób możemy zagwarantować, że podczas korzystania z maszyn Turinga Oracle nadal będziemy wydawać prawidłowe i prawidłowe oświadczenia o klasach złożoności? Według mojego zrozumienia (na podstawie definicji podanych we wprowadzających podręcznikach na ten temat) maszyny oracle Turing mogą określić status członkostwa w łańcuchu znaków w odniesieniu do języka Oracle w jednym kroku obliczeniowym. Jednak często używane języki wyroczni są niemożliwe do rozwiązania w stałym czasie (na przykład wyrocznia pełna EXPTIME). Wydaje mi się, że to „otwieranie drzwi” na sprzeczności, a przecież wszystko wynika z sprzeczności.

complexity-theory oracle-machines Ari
źródło

Jeśli wyrocznia „naprawdę” zajęła trochę czasu

T

$T$ to tylko czynnik wpływający na czas działania całej maszyny. Zakładając stały koszt (tj. Licz, jak często potrzebujesz wyroczni), łatwiej jest porównywać algorytmy wykorzystujące wyrocznię. (Pytanie, czy uzyskane wyniki mają jakikolwiek związek z rzeczywistością, jest tym, z którym zawsze spotykasz się i / lub ignorujesz w TCS.)

Raphael

@Raphael Przez „ty” w komentarzu w nawiasie masz na myśli teoretyków złożoności w ogóle, czy w szczególności mnie?

Ari

Były. Cóż, w pewnym sensie oba.

Raphael

zaawansowany temat. spróbuj zacząć od Fortnow, który zgadza się, że czasami są „niewłaściwie wykorzystywane” i bada obszar. spójny sposób, aby zobaczyć te wyniki, jest czymś w rodzaju „twierdzenia warunkowego”. podobnie do sposobu, w jaki wiele wyników jest warunkowo udowodnionych w matematyce na podstawie hipotezy Riemanna itp.

2014

Odpowiedzi:

Jest na to wiele sposobów.

Jednym z nich jest to, że w dowodach implikacja jest trochę jak funkcja, która przyjmuje jako dane wejściowe dowód czegoś i wysyła dowód czegoś innego.

Możemy pisać funkcje, które działają na wartościach, których nie mamy.

Rozważmy na przykład liczbę zatrzymania $h$ , którego nie można obliczyć. Potrafię napisać funkcję

$haltingPlusOne : \{h \} \rightarrow \mathbb{N}$

$haltingPlusOne(x) = x + 1$ .

Ta funkcja przyjmuje jako dane wejściowe liczbę zatrzymania i zwraca liczbę zatrzymania plus jeden. Oczywiście jest to dobrze zdefiniowana funkcja: jeśli damy jej właściwe wejście, daje właściwe wyjście. Fakt, że nie możemy znaleźć odpowiedniego wejścia, nie czyni go mniej ważnym dla transformacji.

Widzę dowody z wyroczniami jako podobne. Są to w zasadzie funkcje, które mówią: daj mi maszynę Turinga, która rozwiązuje problem $X$ , a jako wynik podam dowód jakiegoś twierdzenia.

Ważne jest również, aby zdać sobie sprawę, że kiedy mówimy coś takiego: „Nie ma maszyny Turinga, która rozstrzygałaby problem zatrzymania”, to znaczy, że nie ma TM odpowiadającej standardowej definicji TM, która decydowałaby o problemie zatrzymania.

Wyrocznia w zasadzie mówi „Załóżmy, że mamy bazę TM, która pasuje do normalnej definicji, z wyjątkiem tego, że zakładamy, że możemy rozwiązać jakiś problem”. Więc nie ma sprzeczności, ponieważ nie zakładamy, że normalna baza TM akceptuje problem, zakładamy, że istnieje specjalna baza TM akceptująca problem.

W bardzo nieformalnej analogii pomyśl o tym w ten sposób. Jeśli mogę udowodnić wam, że żaden człowiek bez supermocy nie może latać, nie ma sprzeczności, mówiąc, że istnieje superbohater, który może latać.

Te wyrocznie są obiektami czysto logicznymi. Nie wiemy, jak budować maszyny fizyczne, które je emulują, tak jak możemy to zrobić za pomocą maszyn Turinga, ale o ile wiemy, nie ma wewnętrznej sprzeczności między ich definicjami a naszymi podstawowymi aksjomatami. Jako obiekty logiczne, te wyrocznie istnieją. Wiemy, że nie są to standardowe maszyny Turinga, terminy Lambda-Calculus ani funkcje częściowo-rekurencyjne. Teza Church-Turinga głosi, że nie ma mocniejszego modelu, ale nie jest to twierdzenie, to tylko przypuszczenie i jest zbyt nieformalne, aby kiedykolwiek zostało udowodnione.

jmite
źródło

Zgadzam się / rozumiem twoją odpowiedź, ale tylko do pewnego momentu: na przykład widzę, że twoja funkcja zatrzymaniaPlusOne jest dobrze zdefiniowana, ale nie widzę, jak możemy wyciągnąć jakiekolwiek znaczące wnioski z wyroczni, ponieważ moglibyśmy „jeśli” oświadczenie fałszywego oświadczenia i dojść do jakiegokolwiek wniosku, tj. „Jeśli

n + 1 = n

$n + 1 = n$ dla wszystkich liczb naturalnych

n \geq 1

$n \geq 1$ jest tylko jedna liczba naturalna. ”

Ari

Chodzi o to, że stwierdzenia nie są fałszywe, po prostu nie możemy ich skonstruować. Kluczem jest to, że wyrocznie nie są maszynami Turinga, nie znaczy to, że nie istnieją.

jmite

„znajdź właściwe wejście”

\mapsto

$\: \mapsto \:$ „znajdź właściwe wyjście”

$\;\;\;$ ?

$\;\;\;\;\;\;\;$

Powiedziałbym, że istotną cechą oracle TM jest to, że mają oni dostęp do trudnej do rozwiązania wyroczni. Jeśli możesz zdecydować wyrocznię $A$ w stałym czasie, a następnie dla każdej klasy $B$ miałbyś $B=B^A$ . Więc po co w ogóle mieć wyrocznię w tym przypadku?

Jaki jest więc sens korzystania z wyroczni TM? Powiedziałbym, że pozwala nam to głównie na rozważania teoretyczne na temat (stopnia) twardości problemów. Wyrocznia może być nawet nierozstrzygalna. W takim przypadku możesz zdefiniować całą hierarchię nierozstrzygniętych problemów (stopień Turinga). Oczywiście, jeśli twój wyrocznia stanowi problem zatrzymania, nie możesz przekształcić swojej wyroczni w tradycyjną.

Koncepcja oracle TM jest również ważna do zdefiniowania silnej formy redukcji (redukcje Turinga).

Zauważ, że bardziej teoretyczna motywacja wyroczni TM może mieć implikacje poza światem wyroczni . Być może znasz słynnego $\sf P$ vs $\sf NP$ wynik relatywizujący.

Jako ostatnią uwagę należy zauważyć, że aby wysłać zapytanie do wyroczni, należy napisać ciąg zapytania $w$ najpierw na taśmie wyroczni. Dlatego nie można decydować o członkostwie w stałym czasie, ale w czasie $|w|$ .

A.Schulz
źródło