Redukcja Turinga - Turing reduction

W teorii obliczalności , redukcja Turinga z problemu decyzyjnego do problemu decyzyjnego jest maszyną wyroczni, która decyduje o problemie daną wyrocznią (Rogers 1967, Soare 1987). Może być rozumiany jako algorytm , którego można by użyć do rozwiązania, gdyby miał dostęp do podprogramu do rozwiązania B . Pojęcie to może być analogicznie zastosowane do problemów funkcjonalnych . ${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A}$

Jeśli istnieje redukcja Turinga z do , to każdy algorytm for może być użyty do stworzenia algorytmu for , poprzez wstawienie algorytmu for w każdym miejscu, w którym wyrocznia maszynowa zapytuje wyrocznię o . Jednakże, ponieważ maszyna wyroczni może wysyłać zapytania do wyroczni wiele razy, otrzymany algorytm może wymagać więcej czasu asymptotycznie niż algorytm lub obliczenie maszyny wyroczni . Redukcja Turinga, w której wyrocznia działa w czasie wielomianowym, jest znana jako redukcja Cooka . ${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle B}$${\ Displaystyle A}$

Pierwszą formalną definicję względnej obliczalności, nazywaną wówczas względną redukowalnością, podał w 1939 r. Alan Turing w kategoriach maszyn wyroczni . Później w 1943 i 1952 Stephen Kleene zdefiniował równoważne pojęcie w kategoriach funkcji rekurencyjnych . W 1944 Emil Post użył terminu „redukowalność Turinga” w odniesieniu do tej koncepcji.

Definicja

Mając dwa zestawy liczb naturalnych, mówimy, że Turing jest redukowalny do i piszemy ${\ Displaystyle A, B \ subseteq \ mathbb {N}}$${\ Displaystyle A}$${\ Displaystyle B}$

${\ Displaystyle A \ leq _ {T} B}$

czy jest maszyna Oracle , które oblicza charakterystyczną funkcję z A kiedy uruchamiane z oracle B . W tym przypadku mówimy również, że A jest B -rekurencyjne i B -obliczalne .

Jeśli istnieje maszyna Oracle , która po uruchomieniu z Oracle B , oblicza funkcję częściową w domenie A , wtedy mówi się , że A jest B - rekurencyjnie przeliczalna i B - przeliczalna .

Mówimy jest Turinga równoważne do i zapisu , jeśli oba i The klas równoważności Turinga równoważnych zestawów są nazywane Turinga stopni . Turinga stopień zestawu jest napisane . ${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A \ równoważne _ {T} B \,}$${\ Displaystyle A \ leq _ {T} B}$${\ Displaystyle B \ leq _ {T} A.}$${\ Displaystyle X}$${\displaystyle {\textbf {stopni}}(X)}$

Biorąc pod uwagę zestaw , zestaw nazywa Turinga ciężko na razie dla wszystkich . Jeśli dodatkowo wtedy nazywa się Turing zupełny dla . ${\displaystyle {\mathcal {X}}\subseteq {\mathcal {P}}(\mathbb {N})}$${\ Displaystyle A \ podseteq \ mathbb {N}}$${\displaystyle {\mathcal {X}}}$${\ Displaystyle X \ leq _ {T} A}$${\ Displaystyle X \ w {\ Mathcal {X}}}$${\ Displaystyle A \ w {\ matematyczny {X}}}$${\ Displaystyle A}$${\displaystyle {\mathcal {X}}}$

Związek kompletności Turinga z uniwersalnością obliczeniową

Zupełność Turinga, jak właśnie zdefiniowano powyżej, tylko częściowo odpowiada kompletności Turinga w sensie uniwersalności obliczeniowej. W szczególności maszyna Turinga jest uniwersalną maszyną Turinga, jeśli jej problem z zatrzymaniem (tj. zestaw danych wejściowych, dla których ostatecznie się zatrzymuje) jest kompletny . Tak więc warunkiem koniecznym, ale niewystarczającym , aby maszyna była uniwersalna obliczeniowo, jest to, aby problem zatrzymania maszyny był Turinga-zupełny dla zbioru zbiorów rekurencyjnie przeliczalnych. ${\displaystyle {\mathcal {X}}}$

Przykład

Pozwolić oznacza zbiór wartości wejściowych dla którego maszyna Turinga z indeksu e przystankach. Następnie zestawy i są ekwiwalentem Turinga (tu oznacza skuteczną funkcję parowania). Pokaz redukcji można skonstruować wykorzystując fakt, że . Biorąc parę nowy wskaźnik może być wykonana za pomocą y _min twierdzenie , tak że program kodowane przez ignoruje sygnał wejściowy i tylko symuluje obliczeniowy komputera z indeks e na wejściu n . W szczególności maszyna z indeksem zatrzymuje się przy każdym wejściu lub zatrzymuje się przy braku wejścia. Tak więc obowiązuje dla wszystkich e i n . Ponieważ funkcja i jest obliczalna, pokazuje to . Przedstawione tu redukcje to nie tylko redukcje Turinga, ale redukcje wiele-jedne , omówione poniżej. ${\displaystyle W_{e}}$${\ Displaystyle A = \ {e \ mid e \ w W_ {e} \}}$${\ Displaystyle B = \ {(e, n) \ średni n \ w W_ {e} \}}$${\displaystyle (-,-)}$${\ Displaystyle A \ leq _ {T} B}$${\ Displaystyle e \ w A \ Leftrightarrow (e, e) \ w B}$${\ Displaystyle (e, n)}$${\ Displaystyle ja (e, n)}$${\ Displaystyle ja (e, n)}$${\ Displaystyle ja (e, n)}$${\ Displaystyle ja (e, n) \ w A \ Leftrightarrow (e, n) \ w B}$${\ Displaystyle B \ leq _ {T} A}$

Nieruchomości

• Każdy zestaw jest odpowiednikiem Turinga z jego uzupełnieniem.
• Każdy zbiór obliczalny jest redukowalny przez Turinga do każdego innego zbioru. Ponieważ każdy zbiór obliczalny może być obliczony bez wyroczni, może zostać obliczony przez maszynę wyroczni, która ignoruje daną wyrocznię.
• Relacja jest przechodnia: if i then . Co więcej, obowiązuje dla każdego zbioru A , a zatem relacja jest przedrządem (nie jest porządkiem częściowym, ponieważ i niekoniecznie implikuje ).${\ Displaystyle \ Leq _ {T}}$${\ Displaystyle A \ leq _ {T} B}$${\ Displaystyle B \ leq _ {T} C}$${\ Displaystyle A \ leq _ {T} C}$${\ Displaystyle A \ leq _ {T} A}$${\ Displaystyle \ Leq _ {T}}$${\ Displaystyle A \ leq _ {T} B}$${\ Displaystyle B \ leq _ {T} A}$${\ Displaystyle A = B}$
• Istnieją pary zbiorów takich, że A nie jest redukowalne przez Turinga do B i B nie jest redukowalne przez Turinga do A . Nie jest to więc porządek całkowity .${\ Displaystyle (A, B)}$${\ Displaystyle \ Leq _ {T}}$
• Istnieją nieskończone malejące sekwencje zbiorów pod . Zatem ta relacja nie jest uzasadniona .${\ Displaystyle \ Leq _ {T}}$
• Każdy zestaw jest Turinga redukowalny do własnego skoku Turinga , ale skok Turinga zestawu nigdy nie jest redukowalny do Turinga do oryginalnego zestawu.

Korzystanie z redukcji

Ponieważ każda redukcja ze zbioru do zbioru musi określać, czy pojedynczy element znajduje się tylko w skończonej liczbie kroków, może wykonać tylko skończenie wiele zapytań o członkostwo w zbiorze . Gdy omawiana jest ilość informacji o zbiorze użytej do obliczenia pojedynczego bitu, jest to precyzowane przez funkcję use. Formalnie, korzystanie z redukcją jest funkcja, która wysyła każdą liczbę naturalną do największej liczby naturalnej , której członkostwo w zbiorze B został pytani przez redukcję podczas określania członkostwa w . ${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle n}$${\ Displaystyle m}$${\ Displaystyle n}$${\ Displaystyle A}$

Silniejsze redukcje

Istnieją dwa powszechne sposoby uzyskania redukcji silniejszych niż redukowalność Turinga. Pierwszym sposobem jest ograniczenie liczby i sposobu zapytań oracle.

• Zbiór jest redukowalny do wielu-jeden, jeśli istnieje funkcja obliczalna w sumie, taka, że ​​element jest w wtedy i tylko wtedy, gdy jest w . Taką funkcję można wykorzystać do wygenerowania redukcji Turinga (poprzez obliczenie , zapytanie wyroczni, a następnie zinterpretowanie wyniku).${\ Displaystyle A}$${\ Displaystyle B}$ ${\displaystyle f}$${\ Displaystyle n}$${\ Displaystyle A}$${\ Displaystyle f (n)}$${\ Displaystyle B}$${\ Displaystyle f (n)}$
• Redukcja tabela prawdy lub słaby prawda redukcja stół musi przedstawić wszystkie swoje pytania wyroczni w tym samym czasie. W redukcji tablicą prawdy, redukcja daje również funkcję logiczną ( tablicę prawdy ), która po otrzymaniu odpowiedzi na zapytania da ostateczną odpowiedź redukcji. W przypadku słabej redukcji tabeli prawdy, redukcja wykorzystuje odpowiedzi wyroczni jako podstawę do dalszych obliczeń w zależności od podanych odpowiedzi (ale nie przy użyciu wyroczni). Równoważnie słaba redukcja tabeli prawdy to taka, w której użycie redukcji jest ograniczone funkcją obliczalną. Z tego powodu słabe redukcje tabeli prawdy są czasami nazywane „ograniczonymi redukcjami Turinga”.

Drugim sposobem na stworzenie silniejszego pojęcia redukowalności jest ograniczenie zasobów obliczeniowych, z których może korzystać program implementujący redukcję Turinga. Te ograniczenia złożoności obliczeniowej redukcji są ważne podczas badania klas podrekurencyjnych, takich jak P . Zbiór A jest redukowalny w czasie wielomianowym do zbioru, jeśli istnieje redukcja Turinga do tego, który przebiega w czasie wielomianowym. Podobna jest koncepcja redukcji przestrzeni logarytmicznej . ${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle B}$

Te redukcje są silniejsze w tym sensie, że zapewniają dokładniejsze rozróżnienie na klasy równoważności i spełniają bardziej restrykcyjne wymagania niż redukcje Turinga. W konsekwencji takie redukcje są trudniejsze do znalezienia. Może nie być możliwości zbudowania redukcji wiele-jednego z jednego zestawu do drugiego, nawet jeśli istnieje redukcja Turinga dla tych samych zestawów.

Słabsze redukcje

Zgodnie z tezą Churcha-Turinga redukcja Turinga jest najogólniejszą formą skutecznie obliczalnej redukcji. Niemniej jednak rozważane są również słabsze redukcje. Zestaw mówi się arytmetyczny w jeśli jest definiowane przez wzór z Peano arytmetycznych w postaci parametru. Zestaw jest hyperarithmetical w jeśli jest rekurencyjne porządkowej taki sposób, że jest od obliczeniowy , a-powtórzyć Turingowi skoku . Pojęcie względnej konstruowalności jest ważnym pojęciem redukowalności w teorii mnogości. ${\ Displaystyle A}$ ${\ Displaystyle B}$${\ Displaystyle A}$${\ Displaystyle B}$${\ Displaystyle A}$ ${\ Displaystyle B}$ ${\ Displaystyle \ alfa}$${\ Displaystyle A}$${\ Displaystyle B ^ {(\ alfa )}}$${\ Displaystyle B}$

Zobacz też

• Redukcja karpia

Uwagi

Bibliografia

• M. Davis, red., 1965. The Undecidable — Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions , Raven, New York. Przedruk, Dover, 2004. ISBN  0-486-43228-9 .
• SC Kleene, 1952. Wprowadzenie do metamatematyki. Amsterdam: Holandia Północna.
• SC Kleene i EL Post, 1954. „Górna półsiatka stopni rekurencyjnej nierozwiązywalności”. Roczniki Matematyki t . 2 przyb. 59, 379-407.
• Poczta, EL (1944). "Rekurencyjnie przeliczalne zbiory liczb całkowitych dodatnich i ich problemy decyzyjne" ( PDF ) . Biuletyn Amerykańskiego Towarzystwa Matematycznego . 50 : 284–316. doi : 10.1090/s0002-9904-1944-08111-1 . Źródło 2015-12-17 .
• A. Turing, 1939. „Systemy logiki oparte na liczbach porządkowych”. Materiały Londyńskiego Towarzystwa Matematycznego , ser. 2 t. 45, s. 161–228. Przedruk w „Nierozstrzygalni”, red. M. Davis, 1965.
• H. Rogers, 1967. Teoria funkcji rekurencyjnych i efektywna obliczalność. McGraw-Hill.
• R. Soare, 1987. Zbiory i stopnie rekurencyjnie przeliczalne, Springer.
• Davis, Martin (listopad 2006). „Co to jest… redukowalność Turinga?” ( PDF ) . Zawiadomienia Amerykańskiego Towarzystwa Matematycznego . 53 (10): 1218–1219 . Źródło 2008-01-16 .

Linki zewnętrzne

• Słownik algorytmów i struktur danych NIST: redukcja Turinga