Mașina Turing nedeterministă

Spre deosebire de o mașină Turing deterministă, tranziția $\delta$ unei mașini Turing nedeterministe este o relație între mulțimile $\scriptstyle Q\times \Gamma$ și $\scriptstyle Q\times \Gamma \times \{L,R\}$ iar nu o funcție.

O relație între elemente ale unei mulțimi $A$ și elemente ale unei mulțimi $\scriptstyle B$ se definiște ca o submulțime a produsului cartezian $\scriptstyle A\times B$. Asfel, un element $\scriptstyle a\in A$ poate fi pus în relație cu mai multe elemente din mulțimea $\scriptstyle B$. O funcție definită pe mulțimea $\scriptstyle A$ cu valori in mulțimea $\scriptstyle B$ este o relație cu constrângerea ca fiecare element din $\scriptstyle A$ să fie pus in corespondență cu exact un singur element din $\scriptstyle B$.

Formal, $\scriptstyle \delta \subseteq (Q\times \Gamma )\times (Q\times \Gamma \times \{L,R\})$ în cazul mașinilor nedeterministe și $\scriptstyle \delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}$ în cazul mașinilor Turing deterministe.

Astfel, în cazul mașinilor Turing nedeterministe, unei stări interne curente și unui simbol curent pe bandă le pot corespunde mai multe stări interne alternative distincte imediat următoare. Mașina Turing nedeterministă efectuază, în mod nedeterminist, oricare dintre mai multele tranziții posibile pentru starea curentă și simbolul aflat pe bandă sub capul de citire. Astfel, există mai multe căi de execuție posibile, adică secvențe de tranziții de stare, deplasări de cap de citire și scrieri de simboluri pe bandă, pentru aceleași date de intrare.

Spunem că mașina nedeterministă se oprește, sau „acceptă” datele de intrare, dacă există cel puțin o secvență de execuție care duce din starea inițială la o stare acceptoare.

Tot așa cum o funcție este un caz particular de relație, o mașină deterministă este un caz particular de mașină nedeterministă. Astfel, mulțimea tuturor mașinilor Turing deterministe este o submulțime a mulțimii tuturor mașinilor Turing nedeterministe. Cu toate acestea, mașinile Turing nedeterministe nu au o „putere computațională” mai mare decât mașinile Turing deterministe. Adică nu există limbaje care să fie acceptate de o mașină nedeterministă și să nu se poată specifica o mașină deterministă care să accepte același limbaj. Aceasta se intâmplă pentru că orice mașină nedeterministă poate fi simulată de o mașină deterministă. Chiar dacă o mașină nedeterministă poate efectua una din mai multele tranziții disponibile pentru o pereche $\scriptstyle (q,a)\in (Q\times \Gamma )$, numărul alternativelor în fiecare pas al execuției este finit pentru că mulțimile $\scriptstyle Q$, $\scriptstyle \Gamma$ și implicit $\scriptstyle Q\times \Gamma$ sunt finite. (Faptul că alternativele de execuție sunt finite permite și o ordonare a lor, astfel încât putem vorbi de prima, a doua, ș.a.m.d. cale de execuție.) Astfel, o mașină deterministă ar putea simula una nedeterministă aplicând o strategie de backtracking depth-first. Pentru că mașina deterministă revine la stări interne parcurse deja pentru ca să repornească din ele pe noi căi sugerează că execuția mașinii deterministe ia mai mult timp decât execuția mașinii nedeterministe echivalente pentru aceleași date de intrare.

O clasă specială de mașini Turing nedeterministe au timpul de execuție limitat superior de un polinom a cărui variabilă este dimensiunea datelor de intrare. Acestea aparțin clasei de complexitate NP. Întrebarea dacă există întotdeauna o mașină Turing deterministă echivalentă care să se execute și ea în timp polinomial nu a putut fi încă răspunsă.

Vezi și

• Mașina Turing
• Mașină Turing deterministă
• NP (teoria complexității)

Legături externe

,