Mașină Turing nedeterministă

În informatica teoretică^⁠(d), o mașină Turing nedeterministă (MTN) este un model teoretic de calcul ale cărui reguli de guvernare specifică mai multe acțiuni posibile atunci când se află în anumite situații date. Adică starea următoare a unei MTN nu este complet determinată de acțiunea sa și de simbolul curent pe care îl vede, spre deosebire de o mașină Turing deterministă.

MTN-urile sunt uneori folosite în experimente mentale pentru a examina abilitățile și limitele calculatoarelor. Una dintre cele mai importante probleme deschise din informatica teoretică este problema P versus NP, care (printre alte formulări echivalente) se referă la cât de dificilă este simularea calculelor nedeterministe cu un calculator determinist.

Context

În esență, o mașină Turing este imaginată a fi un calculator simplu care citește și scrie simboluri pe rând pe o bandă infinită, respectând cu strictețe un set de reguli. Ea determină ce acțiune trebuie să efectueze în continuare în funcție de starea sa internă și de ce simbol vede în prezent. Un exemplu de regulă a unei mașini Turing ar putea fi astfel: „Dacă ești în starea 2 și vezi un «A», atunci schimbă-l în «B», mută-te la stânga și treci la starea 3.”

Mașina Turing deterministă

Într-o mașină Turing deterministă (MTD), setul de reguli prescrie cel mult o acțiune care trebuie efectuată pentru orice situație dată.

O mașină Turing deterministă are o funcție de tranziție care, pentru o anumită stare și simbol sub capul benzii, specifică trei lucruri:

simbolul care urmează să fie scris pe bandă (poate fi același cu simbolul aflat în prezent în acea poziție sau chiar să nu scrie deloc, rezultând în nicio modificare practică),
direcția (stânga, dreapta sau niciuna) în care ar trebui să se miște capul și
starea următoare a automatului finit.

De exemplu, un X pe bandă în starea 3 ar putea face ca MTD să scrie un Y pe bandă, să miște capul cu o poziție la dreapta și să comute la starea 5.

Intuiție

Comparația între calculele deterministe și cele nedeterministe

Spre deosebire de o mașină Turing deterministă, într-o mașină Turing nedeterministă setul de reguli poate prescrie mai mult de o acțiune care trebuie efectuată pentru orice situație dată. De exemplu, un X pe bandă în starea 3 ar putea permite NTM să:

Scrie un Y, mută-te la dreapta și treci la starea 5

sau

Scrie un X, mută-te la stânga și rămâi în starea 3.

Rezolvarea mai multor reguli

Cum „știe” MNT care dintre aceste acțiuni ar trebui să întreprindă? Există două moduri de a privi. Unul este de a spune că mașina este „cel mai norocos ghicitor posibil”; alege întotdeauna o tranziție care duce în cele din urmă la o stare acceptoare, dacă există o astfel de tranziție. Celălalt este să ne imaginăm că mașina „se ramifică” în mai multe copii, fiecare dintre ele urmând una dintre posibilele tranziții. În timp ce o MTD are o singură „cale de calcul” pe care o urmează, o MTN are un „arbore de calcul”. Dacă cel puțin o ramură a arborelui se oprește cu o condiție de „acceptare”, atunci NTM acceptă intrarea.

Definiție

O mașină Turing nedeterministă poate fi definită formal ca un sextuplu $M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )$ , unde

$Q$ este o mulțime finită de stări
$\Sigma$ este o mulțime finită de simboluri (alfabetul benzii)
$\iota \in Q$ este starea inițială
$\sqcup \in \Sigma$ este simbolul vid
$A\subseteq Q$ este ansamblul stărilor acceptoare (finale).
$\delta \subseteq \left(Q\backslash A\times \Sigma \right)\times \left(Q\times \Sigma \times \{L,S,R\}\right)$ este o relație între stări și simboluri numită relație de tranziție. $L$ este mișcarea spre stânga, $S$ este nicio mișcare și $R$ este mișcarea spre dreapta.

Diferența față de o mașină Turing standard (deterministă) este că, pentru mașinile Turing deterministe, relația de tranziție este mai degrabă o funcție decât o relație.

Configurațiile și relația de rezultate pe configurații, care descrie acțiunile posibile ale mașinii Turing, având în vedere orice conținut posibil al benzii, sunt la fel ca pentru mașinile Turing standard, cu excepția faptului că relația de rezultate nu mai este cu o singură valoare. (Dacă mașina este deterministă, calculele posibile sunt toate prefixe ale unei singure căi, posibil infinite.)

Intrarea pentru o MTN este furnizată în același mod ca și pentru o mașină Turing deterministă: mașina este pornită în configurația în care capul benzii se află pe primul caracter al șirului (dacă există), iar banda este toată goală în caz contrar.

O MTN acceptă un șir de intrare dacă și numai dacă cel puțin una dintre căile de calcul posibile care pornesc de la acel șir pune mașina într-o stare acceptoare. Când se simulează numeroasele căi de ramificare a unei MTN pe o mașină deterministă, se poate opri întreaga simulare de îndată ce orice ramură atinge o stare acceptoare.

Definiții alternative

Întrucât MTN este o construcție matematică folosită în principal în demonstrații, există o serie de variații minore ale definiției unei MTN, dar toate aceste variații acceptă limbaje echivalente.

Mișcarea capului în ieșirea relației de tranziție este adesea codificată numeric în loc să se folosească litere pentru a reprezenta mișcarea capului la stânga (-1), la staționar (0) și la dreapta (+1); înseamnă că ieșirea funcției de tranziție poate fi $\left(Q\times \Sigma \times \{-1,0,+1\}\right)$ . Adesa ieșirea staționară (0) se omite,^[1] și, în schimb, se introduce închiderea tranzitivă a oricăror tranziții staționare dorite.

Unii autori adaugă o stare explicită de respingere,^[2] care determină oprirea MTN fără a accepta. Această definiție păstrează încă asimetria pe care orice ramură nedeterministă o poate accepta, dar toate ramurile trebuie să o respingă pentru ca șirul să fie respins.

Echivalența computațională cu MTD-urile

Orice problemă de calcul care poate fi rezolvată printr-un MTD poate fi rezolvată și printr-un MTN și invers. Cu toate acestea, se crede că, în general, complexitatea în timp poate să nu fie aceeași.

MTD ca un caz special de MTN

MTN-urile includ MTD-urile drept cazuri speciale, astfel încât fiecare calcul care poate fi efectuat de un MTD poate fi efectuat și de un MTN echivalent.

Simularea unui MTN cu un MTD

S-ar putea părea că MTN-urile sunt mai puternice decât MTD-urile, deoarece pot permite arbori de calcule posibile care decurg din aceeași configurație inițială, acceptând un șir dacă orice ramură din arbore îl acceptă. Cu toate acestea, este posibil să se simuleze MTN-uri cu MTD-uri și, de fapt, acest lucru se poate face în mai multe moduri.

Multiplicarea stărilor de configurare

O abordare este utilizarea unui MTD ale cărei configurații reprezintă mai multe configurații ale MTN, iar operarea MTD constă în vizitarea pe rând a fiecăreia dintre ele, executarea unui singur pas la fiecare vizită și generarea de noi configurații ori de câte ori relația de tranziție definește continuări multiple.

Multiplicarea benzilor

O altă construcție simulează MTN-uri cu MTD-uri cu 3 benzi, dintre care prima bandă deține întotdeauna șirul de intrare original, a doua este folosită pentru a simula un anumit calcul al MTN, iar a treia codifică o cale în arborele de calcul al MTN.^[3] MTD-urile cu 3 benzi sunt ușor de simulat cu un MTD normal cu o singură bandă.

Complexitatea în timp și P versus NP

În a doua construcție, MTD construită efectuează în mod eficient o căutare în lățime prin arborele de calcul al MTN, vizitând toate calculele posibile ale MTN în ordinea crescătoare a lungimii până când găsește unul care acceptă. Prin urmare, lungimea unui calcul MTD care acceptă este, în general, exponențială în raport cu lungimea celui mai scurt calcul MTN care acceptă. Se crede că aceasta este o proprietate generală a simulărilor MTN de către MTD. Problema P = NP, cea mai faimoasă întrebare nerezolvată din informatică, se referă la un caz al acestei probleme: dacă orice problemă rezolvabilă de o MTN în timp polinomial este în mod necesar rezolvabilă și de un MTD în timp polinomial.

Nedeterminism mărginit

O MTN are proprietatea de nedeterminism mărginit, adică: dacă o MTN se oprește întotdeauna pe o bandă de intrare dată T, atunci se oprește într-un număr mărginit de pași și, prin urmare, poate avea doar un număr mărginit de configurații posibile.

Comparație cu calculatoarele cuantice

Forma suspectată a gamei de probleme rezolvabile de calculatoarele cuantice în timp polinomial^⁠(d) (BQP). De reținut că figura sugerează că

{\mathsf {P}}\neq {\mathsf {NP}}

și

{\mathsf {NP}}\neq {\mathsf {PSPACE}}

. Dacă aceasta nu este adevărată, atunci figura ar trebui să arate diferit.

Deoarece calculatoarele cuantice^⁠(d) folosesc biți cuantici, care pot fi în suprapuneri^⁠(d) de stări, și nu biți convenționali, există uneori o concepție greșită că calculatoarele cuantice^⁠(d) sunt MTN.^[4] Cu toate acestea, experții cred (dar nu s-a demonstrat) că puterea calculatoarelor cuantice este, de fapt, incomparabilă cu cea a MTN-urilor; adică, există probabil probleme pe care un MTN le-ar putea rezolva eficient dar pe care un calculator cuantic nu poate, și invers.^[5] În special, este probabil ca problemele NP-complete să fie rezolvabile prin MTN, dar nu prin calculatoare cuantice în timp polinomial.

Intuitiv vorbind, în timp ce un calculator cuantic poate fi într-adevăr într-o stare de suprapunere corespunzătoare tuturor ramurilor de calcul posibile care au fost executate în același timp (similar cu o MTN), măsurarea finală va plia computerul cuantic într-o singură ramură aleasă aleatoriu. Această ramură nu reprezintă, în general, soluția căutată, spre deosebire de MTN, căreia îi este permis să aleagă soluția potrivită dintre ramurile în număr exponențial.

Note

^ Garey, Michael R.; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0-7167-1045-5.
^ Erickson, Jeff. „Nondeterministic Turing Machines” (PDF). U. Illinois Urbana-Champaign. Accesat în 7 aprilie 2019.
^ Lewis, Harry R.; Papadimitriou, Christos (1981). „Section 4.6: Nondeterministic Turing machines”. Elements of the Theory of Computation (ed. 1st). Englewood Cliffs, New Jersey: Prentice-Hall. pp. 204–211. ISBN 978-0132624787.
^ The Orion Quantum Computer Anti-Hype FAQ, Scott Aaronson^⁠(d).
^ Tušarová. „Quantum complexity classes”. arXiv:cs/0409051  . .

Bibliografie

Martin, John C. (1997). „Section 9.6: Nondeterministic Turing machines”. Introduction to Languages and the Theory of Computation (ed. 2nd). McGraw-Hill. pp. 277–281. ISBN 978-0073191461.
Papadimitriou, Christos (1993). „Section 2.7: Nondeterministic machines”. Computational Complexity (ed. 1st). Addison-Wesley. pp. 45–50. ISBN 978-0201530827.

[GJ-1] Garey, Michael R.; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0-7167-1045-5.

[jeffe-2] Erickson, Jeff. „Nondeterministic Turing Machines” (PDF). U. Illinois Urbana-Champaign. Accesat în 7 aprilie 2019.

[3] Lewis, Harry R.; Papadimitriou, Christos (1981). „Section 4.6: Nondeterministic Turing machines”. Elements of the Theory of Computation (ed. 1st). Englewood Cliffs, New Jersey: Prentice-Hall. pp. 204–211. ISBN 978-0132624787.

[4] The Orion Quantum Computer Anti-Hype FAQ, Scott Aaronson^⁠(d).

[5] Tušarová. „Quantum complexity classes”. arXiv:cs/0409051  . .

[1]

[2]

[3]

[4]

[5]