Mașina Turing nedeterministă

Spre deosebire de o mașină Turing deterministă, tranziția unei mașini Turing nedeterministe este o relație între mulțimile și iar nu o funcție.

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

Formal, în cazul mașinilor nedeterministe și î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 , numărul alternativelor în fiecare pas al execuției este finit pentru că mulțimile , și implicit 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ă.

NoteModificare

Vezi șiModificare

Legături externeModificare

,