Maszyna Turinga z wyrocznią

Maszyna Turinga z wyrocznią – w teorii obliczeń abstrakcyjny model stosowany w celu badania problemów decyzyjnych. Maszynę Turinga z wyrocznią można traktować jako wielotaśmową maszynę Turinga z wyróżnioną, przeznaczoną tylko do odczytu taśmą (zwaną taśmą wyroczni), na której zapisany jest nieskończony ciąg symboli (zwany wyrocznią)^[1][2][3]. Pod każdym innym względem maszyna Turinga z wyrocznią działa jak zwykła maszyna Turinga. Jeżeli zawartość taśmy wyroczni składa się wyłącznie z symboli zerowych, to taka maszyna jest zwykłą wielotaśmową maszyną Turinga.

Część autorów podaje alternatywną definicję, w której zbiór stanów maszyny rozszerzony jest o stany dodatkowe {q_ask,q_yes,q_no} związane z obsługą wyroczni. Odwołanie do wyroczni polega na zapisaniu słowa na taśmie wyroczni i wywołaniu stanu q_ask, co skutkuje przejściem do stanu q_yes lub q_no w zależności od rozwiązania problemu decyzyjnego, o które pytana jest wyrocznia^[4]. Wyrocznia jest więc równoważna zbiorowi słów (językowi), dla których maszyna przechodzi do stanu q_yes.

Rodzaje wyroczni

W ogólności wyrocznia może dawać rozwiązanie dowolnego problemu decyzyjnego lub problemu funkcyjnego. Taki problem nie musi być algorytmicznie rozstrzygalny, wyrocznia może reprezentować odpowiedzi w zakresie dowolnego, zdefiniowanego matematycznie zbioru problemów. Na przykład:

• Wyrocznia może zawierać informacje na temat spełnialności dowolnej formuły rachunku zdań w postaci CNF (problem 3-SAT). Ponieważ problem 3-SAT jest NP-zupełny, taka maszyna jest zdolna do rozwiązywania problemów NP w czasie wielomianowym^[5].
• Wyrocznia może zawierać informacje na temat własności stopu dowolnej maszyny Turinga dla dowolnej danej wejściowej. Taka maszyna jest zdolna do rozwiązywania niektórych problemów algorytmicznie nierozstrzygalnych, np. problemu stopu dla maszyn bez wyroczni i wszelkich problemów algorytmicznie redukujących się do problemu stopu dla maszyn bez wyroczni.

Maszyna Turinga z wyrocznią a problem stopu

Zobacz też: problem stopu.

Maszyna Turinga z wyrocznią może rozstrzygnąć w skończonej liczbie kroków, czy dowolna maszyna Turinga z określoną daną wejściową nie zakończy pracy. Jednak nie istnieje maszyna Turinga z wyrocznią determinująca w ogólności, które maszyny Turinga z taką samą wyrocznią z określoną daną wejściową nie zakończą pracy^[6]. Dowód przyjmuje identyczną formę jak w przypadku standardowych maszyn Turinga. Rozważmy pewną numerację maszyn Turinga z wyrocznią: C₁, C₂, ... Przypuśćmy, że A jest maszyną Turinga z wyrocznią taką, że jeżeli A zatrzymuje się działając na daną (q,n) to dowodzi, że C_q(n) nie kończy pracy. Dla pewnego k: C_k(n) = A(n,n). Zatem jeżeli A działa poprawnie to A(k,k) nie kończy pracy, ponieważ jeżeli A(k,k) kończy pracę, to C_k(k)=A(k,k) nie kończy pracy. Zatem jeżeli A działa poprawnie, to istnieje takie k, że pomimo że C_k(k) nie kończy pracy, A(k,k) nie kończy pracy, zatem A jest niezupełna. Pokazaną metodę diagonalizacji można w ogólności zastosować dla każdej maszyny Turinga z wyrocznią, której konfiguracja może być reprezentowana za pomocą liczby naturalnej.

Maszyna Turinga z wyrocznią a złożoność obliczeniowa

Zobacz też: klasa złożoności.

Maszyny Turinga z wyrocznią znalazły zastosowanie w badaniu problemów związanych ze złożonością obliczeniową. Niech A^L oznacza zbiór tych języków, które mogą zostać zdefiniowane przy użyciu deterministycznych, należących do klasy A maszyn Turinga z wyrocznią L. Na przykład P^3-SAT oznacza zbiór tych języków, w przypadku których przynależność słowa można zdefiniować przy pomocy działającej w czasie wielomianowym deterministycznej maszyny Turinga z wyrocznią rozwiązującą problem 3-SAT.

Maszyny Turinga z wyrocznią są użyteczne w badaniu relacji pomiędzy klasami złożoności P i NP, co wiąże się z nierozwiązanym dotychczas problemem P vs NP. W szczególności twierdzenie Bakera-Gilla-Solovaya mówi, że istnieją takie języki X i Y, że P^X = NP^X i P^Y ≠ NP^{Y [7]}. Uważa się, że fakt ten świadczy o trudności problemu P vs NP, ponieważ pokazuje, że ten problem nie może zostać rozwiązany przy pomocy większości znanych technik dowodowych. Większość metod dowodowych to rozumowania, które relatywizują się, tzn. wykorzystują własności, które nie zmieniają się nawet, jeśli założymy, że każda maszyna Turinga w dowodzie ma dostęp do dowolnej, ale takiej samej wyroczni.

Zobacz też

• Niedeterministyczna maszyna Turinga
• Transformacja Turinga
• Maszyna Turinga

Przypisy

1. Kozen 1997 ↓, s. 274.
2. Rogers 1987 ↓, s. 130.
3. Soare 1999 ↓, s. 47.
4. Arora i Barak 2009 ↓, s. 73.
5. Papadimitriou 1994 ↓, s. 339.
6. Alan Turing. Systems of Logic Based on Ordinals. „Proceedings of the London Mathematical Society”. s2-45 (1), s. 172, 1939.
7. Arora i Barak 2009 ↓, s. 74.

Bibliografia

• Dexter C. Kozen: Automata and Computability. Springer, 1997. ISBN 0-387-94907-0.
• Hartley Rogers: Theory of Recursive Functions and Effective Computability. The MIT Press, 1987. ISBN 978-0262680523.
• Robert I. Soare: Recursively Enumerable Sets and Degrees. Springer, 1999. ISBN 978-3-540-15299-6.
• Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, 2009. ISBN 978-0521424264.
• Christos H. Papadimitriou: Computational Complexity. Addison-Wesley, 1994. ISBN 0-201-53082-1.