Nedeterministický Turingův stroj

Nedeterministická Turingův stroj je podobný obvyklému Turing stroj , který je deterministický , ale liší se od něj v tom, že je non-deterministický může mít několik aktivovatelných přechodů pro daný stav.

Prezentace

Zatímco deterministický Turingův stroj , který zná znak přečtený na pásu karet a aktuální stav, má nejvýše jeden možný přechod, nedeterministický Turingův stroj může mít několik. V důsledku toho, zatímco výpočty deterministického Turingova stroje tvoří posloupnost, výpočty nedeterministického Turingova stroje tvoří strom, ve kterém každá cesta odpovídá posloupnosti možných výpočtů.

Můžeme si představit vývoj nedeterministického Turingova stroje následovně: ve stavu, kdy existuje několik možných přechodů, duplikuje (triplikáty atd.) A pro každý jiný přechod se vytvoří podřízený stroj. Nedeterministický Turingův stroj přijímá vstup, pokud existuje posloupnost voleb (větev stromu, samopal), která dosáhne přijímajícího stavu.

Dalším způsobem, jak si představit volby nedeterministického Turingova stroje, je představit si to co nejšťastnější: jinými slovy, pokud existuje řada možností, která má za následek přijetí konečného stavu, stroj provede tuto řadu. řada možností možných přechodů.

Formální popis

$Q$ je konečná sada států.
$\ Sigma$ , abeceda, je konečná sada symbolů.
$\ iota \ v Q$ je počáteční stav.
$\ textvisiblespace$ je bílý symbol ( ) $\ textvisiblespace \ in \ Sigma$
$A \ subseteq Q$ je množina „přijímajících“ nebo konečných stavů.
$\ delta: Q \ zpětné lomítko A \ times \ Sigma \ rightarrow \ left (Q \ times \ Sigma \ times \ {L, R \} \ right)$ je binární relace na stavech a symbolech. Jedná se o přechodný vztah. L je levý posun a R je pravý posun.

Deterministický Turingův stroj lze popsat jako nedeterministický Turingův stroj, jehož přechodový vztah je funkční .

Pojem přijetí vstupu se nezmění: nedeterministický Turingův stroj přijímá slovo jako vstup právě tehdy, když se stroj spustí v konfiguraci, kde je hlava umístěna na prvním znaku slova na bílé stuze všude jinde, alespoň jedna z výpočtových sekvencí stroje dosáhne přijímacího stavu . Rozdíl je v tom, že vzhledem ke vstupu má deterministický stroj pouze jednu možnou sekvenci konfigurací. Nedeterministický Turingův stroj má několik, což znamená, že může přijmout slovo a zároveň mít několik nepřijatelných výpočtů pro toto slovo. To je důvod, proč je komplementarizace jazyka pro nedeterministické stroje mnohem dražší, nestačí invertovat konečné a nedefinální stavy. ${\ displaystyle \ v A}$

Dopad na výpočetní čas

Koncept nedeterministického Turingova stroje nerozšiřuje představu o vypočítatelnosti . Proto nedeterministické Turingovy stroje počítají přesně stejné funkce jako deterministické Turingovy stroje, protože nedeterministický Turingův stroj může být simulován deterministickým Turingovým strojem. Složitost výpočtů se však liší: třída polynomiální složitosti s nimi spojená je třída složitosti $NP$ , která obsahuje odpovídající třídu pro deterministické Turingovy stroje. To je důvod, proč označení této třídy, jmenovitě $NP$ , pochází z jejich jména a prostředky N na deterministické P olynomial , jinými slovy třídy problémů, které mohou být řešeny v polynomial čase nedeterministických Turingových strojů. Všimněte si, že nevíme, zda je tato třída $NP$ stejná nebo ne třídě $P$ problémů, které lze vyřešit v polynomiálním čase pomocí deterministických Turingových strojů: jedná se o slavný problém P = NP .

Související články