Niedeterministyczna maszyna Turinga
Niedeterministyczna maszyna Turinga – teoretyczny model rozważany w teorii obliczeń w celu badania problemów decyzyjnych. Niedeterministyczna maszyna Turinga jest zdefiniowana tak samo jak deterministyczna maszyna Turinga z jedyną różnicą dotyczącą postaci funkcji przejścia, która w przypadku maszyn niedeterministycznych zwraca zbiór możliwych działań maszyny.
Ewolucje niedeterministycznej maszyny Turinga można reprezentować w postaci drzewa w którym każdy poziom odpowiada jednemu krokowi maszyny, natomiast rozgałęzienia wynikają z niedeterminizmu funkcji przejścia. Taka maszyna kończy prace w momencie, gdy dochodzi do poziomu ze stanem końcowym w co najmniej jednym z węzłów. W tym modelu kolejny krok maszyny liczony jest jako przejście do następnego zbioru możliwych stanów (poziomu drzewa).
Dany problem może zostać rozwiązany w czasie wielomianowym na niedeterministycznej maszynie Turinga wtedy i tylko wtedy, gdy poprawność rozwiązania tego problemu jest weryfikowalna w czasie wielomianowym na deterministycznej maszynie Turinga. Tego rodzaju problemy należą do klasy NP (nondeterministic polynomial time).
Definicja formalna edytuj
Niedeterministyczna maszyna Turinga jest krotką [1]:
M = (K, Σ, Δ, s, H)
gdzie:
K – zbiór stanów maszyny
Σ – alfabet taśmy z wyróżnionym symbolem zerowym (∅ ∊ Σ)
s – stan początkowy (s ∊ K)
H – zbiór stanów końcowych (H ⊆ K)
Δ – podzbiór iloczynu kartezjańskiego ((K – H) x Σ) x (K x Σ x {L,R})
Jedyna istotna różnica względem definicji deterministycznej maszyny Turinga polega na zastąpieniu funkcji postaci ((K – H) x Σ) → (K x Σ x {L,R}) relacją Δ ⊆ ((K – H) x Σ) x (K x Σ x {L,R}). Z tego powodu deterministyczne maszyny Turinga można traktować jako szczególne przypadki niedeterministycznych maszyn Turinga, mianowicie takich w których Δ jest funkcją.
Obliczeniowa równoważność z deterministyczną maszyną Turinga edytuj
Niedeterministyczne maszyny Turinga podlegają dokładnie takim samym ograniczeniom obliczeniowym (patrz: problem stopu) jakim podlegają deterministyczne maszyny Turinga. Można pokazać, że dany problem jest rozstrzygalny na niedeterministycznej maszynie Turinga wtedy i tylko wtedy, gdy jest rozstrzygalny na deterministycznej maszynie Turinga.
Każdy problem rozstrzygalny na deterministycznej maszynie Turinga jest rozstrzygalny na niedeterministycznej maszynie Turinga. Jest to oczywiste, jako że deterministyczną maszynę Turinga można traktować jako szczególny przypadek niedeterministycznej maszyny Turinga.
Każdy problem rozstrzygalny na niedeterministycznej maszynie Turinga jest rozstrzygalny na deterministycznej maszynie Turinga. Idea dowodu polega na pokazaniu, że dysponując algorytmem niedeterministycznym rozstrzygającym dany problem, można skonstruować algorytm deterministyczny poprzez przeszukiwanie wszerz drzewa obliczeń algorytmu niedeterministycznego.
Realizacja fizyczna edytuj
W przeciwieństwie do maszyn Turinga w modelu podstawowym, maszynom niedeterministycznym nie odpowiada działanie jakiegokolwiek klasycznego urządzenia (z dokładnością do przejść pomiędzy zbiorami stanów).
Powszechnie panuje błędne przekonanie, że komputery kwantowe pod względem osiąganej złożoności są równoważne niedeterministycznym maszynom Turinga. Jednak do tej pory nie są znane metody rozwiązywania problemów NP-zupełnych na komputerach kwantowych w czasie wielomianowym. Na przykład kwantowy algorytm faktoryzacji Shora pozwala rozwiązać problem faktoryzacji całkowitej w czasie wielomianowym, jednak nie ma dowodów na to, że faktoryzacja jest NP-zupełna. A więc nie wynika z tego, że komputery kwantowe mogą w ogólności rozwiązywać problemy NP w czasie wielomianowym [2].
Zobacz też edytuj
Przypisy edytuj
- ↑ Lewis i Papadimitriou 1997 ↓, s. 221.
- ↑ Le Bellac 2011 ↓, s. 112.
Bibliografia edytuj
- Harry Lewis, Christos H. Papadimitriou: Elements of the Theory of Computation. Prentice Hall, 1997. ISBN 978-0-13-262478-7.
- Michel Le Bellac: Wstęp do informatyki kwantowej. przeł. Helena Kucał, Jerzy Karczmarczuk. Wydawnictwo Naukowe PWN, 2011. ISBN 978-83-01-16570-3.