W informatyce teoretycznej , aw szczególności w teorii złożoności , naprzemienne maszyny Turinga są uogólnieniem niedeterministycznych maszyn Turinga . Ich tryb akceptacji uogólnia warunki akceptacji stosowane w klasach złożoności NP i co-NP . Koncepcja naprzemiennej maszyny Turinga została sformułowana przez Ashoka K. Chandrę i Larry'ego Stockmeyera oraz niezależnie przez Dextera Kozena w 1976 r. We wspólnym artykule opublikowanym w 1981 r. Chandra i Stockmeyer używają ich do zademonstrowania dolnych granic w czasie wykładniczym dla dwóch gier. Maszyny naprzemienne dają inną interpretację hierarchii wielomianów .
Definicja klasy NP wykorzystuje do obliczeń tryb „egzystencjalny”: obliczenie jest akceptacją, jeśli istnieje wybór, który prowadzi do stanu akceptacji. Z drugiej strony definicja co-NP wykorzystuje „uniwersalny” sposób obliczania: obliczenie akceptuje tylko wtedy, gdy wszystkie możliwe wybory prowadzą do stanu akceptacji. W naprzemiennej maszynie Turinga tryb obliczania zmienia się między tymi dwoma trybami.
Pojęcie przemiennej maszyny Turinga rozszerza pojęcie niedeterministycznej maszyny Turinga . Stany są dwojakiego rodzaju: stany egzystencjalne (oznaczone jako „lub”) i stany uniwersalne (oznaczone „i”). Zatem konfiguracja egzystencjalna (tj. Stan, słowo na wstążce i pozycja głowy) jest akceptowalna, jeśli istnieje następująca konfiguracja akceptująca; uniwersalna konfiguracja jest akceptowalna, jeśli wszystkie kolejne konfiguracje są dopuszczalne. Maszyna akceptuje wpis, jeśli konfiguracja początkowa tego wpisu jest akceptowana.
Przemiennego (jeden prążek) maszyny Turinga jest struktura , gdzie:
Mówi się, że konfiguracja w stanie q, w którym jest akceptowana, jeśli wszystkie konfiguracje dostępne w jednym kroku, akceptują, i odrzuca, jeśli co najmniej jedna taka konfiguracja odrzuca. W szczególności jest to dopuszczalne, jeśli nie ma dostępnych konfiguracji. Mówi się, że konfiguracja z akceptacją, jeśli istnieje konfiguracja dostępna w jednym kroku, która akceptuje i odrzuca, jeśli żadna konfiguracja dostępna w jednym kroku nie akceptuje (jest to typ wszystkich stanów w zwykłej niedeterministycznej maszynie Turinga). W szczególności odrzuca, jeśli nie ma dostępnych konfiuracji. Maszyna M akceptuje słowo wejściowe w, jeśli początkowa konfiguracja na w z M (w którym stan M jest , głowica znajduje się po lewej stronie czytnika, a taśma zawiera w ) jest akceptowalna i odrzuca słowo, jeśli konfiguracja początkowa jest odrzucana.
Jeśli obliczenia się zakończą, możemy rekurencyjnie zdefiniować pojęcie akceptowania konfiguracji omówionych powyżej. W przeciwnym razie używamy twierdzenia Knastera-Tarskiego o punkcie stałym .
Aby określić, czy konfiguracja naprzemiennej maszyny Turinga jest akceptowalna, czy nie, zgodnie z powyższą definicją, nie jest konieczne badanie wszystkich konfiguracji dostępnych w bieżącej konfiguracji. W ten sposób konfigurację egzystencjalną można oznaczyć jako akceptującą, gdy tylko zostanie znaleziona natychmiast dostępna konfiguracja, która sama akceptuje. Symetrycznie, konfiguracja uniwersalna jest odrzucana, jeśli odrzuca jedna z konfiguracji dostępnych w jednym kroku.
Naprzemienna maszyna Turinga decyduje, czy należeć do języka formalnego w czasie, jeśli dla dowolnego słowa o długości wystarczy zbadać sekwencje konfiguracji na większości etapów, aby określić, czy początkowa konfiguracja akceptuje, czy nie. Naprzemienna maszyna Turinga decyduje o przynależności przestrzennej, jeśli wystarczy zbadać konfiguracje, które nie modyfikują większej liczby komórek pasma.
Opisujemy tutaj alternatywną maszynę do decydowania o prawdziwości skwantyzowanej formuły boolowskiej (TQBF): każda zmienna zdaniowa może być powiązana z egzystencjalnym lub uniwersalnym kwantyfikatorem. Problem TQBF jest kompletny w PSPACE i uogólnia problem SAT, który jest NP-zupełny. Problem SAT można postrzegać jako szczególny przypadek, w którym wszystkie zmienne są egzystencjalnie kwantyfikowane.
Maszyna przemienna tworzy gałęzie egzystencjalne, aby wypróbować wszystkie możliwe wartości zmiennej egzystencjalnie skwantowanej, a gałęzie uniwersalne, aby wypróbować wszystkie możliwe wartości zmiennej skwantowanej uniwersalnie, postępując od lewej do prawej w kolejności skwantowanych zmiennych. . Po wybraniu wartości wszystkich skwantowanych zmiennych maszyna akceptuje dane wejściowe, jeśli wynikowa formuła boolowska daje wartość „prawda”, aw przeciwnym razie odrzuca je.
W przypadku problemu SAT poprzedni algorytm wykorzystuje tylko gałęzie egzystencjalne (klasyczny niedeterminizm).
Taka maszyna decyduje, czy przyjąć formułę boolowską wyrażoną ilościowo w czasie i przestrzeni .
Klasa jest zdefiniowana jako klasa języków formalnych, dla których o członkostwie decyduje przemienna w czasie maszyna Turinga dla stałej ; podobnie klasa jest klasą języków, w przypadku których o członkostwie może decydować maszyna Turinga zmieniająca przestrzeń .
W następujących klas złożoności są zdefiniowane z maszynami Turinga przemienne:
Klasy te są podobne do klas P , PSPACE i EXPTIME , zdefiniowanych na podstawie deterministycznych maszyn Turinga. Mamy następujące wyniki (tutaj i :
Więc mamy:
Klasy złożoności można udoskonalić, jeśli ograniczymy naprzemienność w obliczeniach.
Urządzenie przemiennego Turinga z k naprzemiennych to urządzenie przemiennego Turinga, który przechodzi ze stanu egzystencji do uniwersalnego stanu lub odwrotnie najwyżej k -1 razy. Formalnie jest to maszyna Turinga, której stany są podzielone na k części indeksowanych przez 1, ..., k . Stany w częściach o indeksach parzystych są uniwersalne, a o indeksach nieparzystych - egzystencjalne. Jedyne możliwe przejścia to stany w częściach większych indeksów.
to klasa funkcji czasowych rozpoczynających się w stanie egzystencjalnym i przeważnie zmieniających się . Nazywa się to poziomem hierarchii .
jest zdefiniowany w ten sam sposób, ale zaczynając od stanu uniwersalnego; jest uzupełnieniem .
jest definiowany podobnie dla obliczeń ograniczonych przestrzenią.
Rozważamy problem minimalizacji obwodu (en) : biorąc pod uwagę obwód A, który oblicza funkcję boolowską fi liczbę całkowitą n , określ, czy istnieje obwód z maksymalnie n bramkami, który oblicza tę samą funkcję f . Naprzemienna maszyna Turinga, z tylko jedną przemianą, rozpoczynającą się w stanie egzystencjalnym, może rozwiązać ten problem w czasie wielomianowym: zgaduje obwód B z maksymalnie n bramkami, a następnie przechodzi w stan uniwersalny, odgaduje wejście i sprawdza, czy wyjście B dla tego wejścia jest równe wyjściu A dla tego samego wejścia.
Mówimy, że hierarchia załamuje się na poziomie, jeśli jakikolwiek język poziomu hierarchii jest już na tym poziomie . Jedną z konsekwencji twierdzenia Immermana-Szelepcsényiego jest załamanie się hierarchii przestrzeni logarytmicznej do jej pierwszego poziomu.
Naprzemienna maszyna Turinga o k wibracjach, która zaczyna się w stanie egzystencjalnym (odpowiednio uniwersalnym), może rozstrzygać w czasie wielomianowym wszystkie problemy klasy (odpowiednio klasy ) hierarchii wielomianów .
Juraj Hromkovič zaproponował rozszerzenie zsynchronizowanych przemiennych maszyn Turinga, w których obliczenia są zsynchronizowane. Celem jest przybliżenie tych maszyn do obliczeń równoległych.