Mașina Turing deterministă

Relația de tranziție $\scriptstyle \delta$ a unei mașini Turing specifică acțiunea pe care o execută mașina (de exemplu deplasarea capului de citire la stânga sau la dreapta sau scrierea unui anumit simbol pe bandă) precum și tranziția de stare pe care o efectuează atunci când întâlnește un anumit simbol pe bandă și se află într-o anumită stare interioară. Formal, relația $\scriptstyle \delta$ asociază perechea $\scriptstyle (q,a)\in Q\times \Gamma$ la zero sau mai mulți tripleți $\scriptstyle (q',a',w)\in Q\times \Gamma \times \{L,R\}$ . ( $Q$ este mulțimea stărilor interne ale mașinii Turing, $\scriptstyle \Gamma$ este mulțimea simbolurilor de pe bandă. Vezi și definiția mașinii Turing).

Relația de tranziție $\scriptstyle \delta$ a unei mașini Turing deterministe este o funcție. Adică cel mult un triplet $\scriptstyle (q',a',w)\in Q\times \Gamma \times \{L,R\}$ corespunde unei stări interne $q$ și unui simbol $a$ de pe bandă. Comportamentul mașinii este determinist in sensul că cel mult o acțiune este posibilă pentru orice combinație de stare interioară și dată de intrare. Calea de execuție a mașinii, adică secvența de tranziții de la starea inițială, este unică pentru fiecare instanță de date de intrare.

În cazul general, al unei mașini Turing nedeterministe, când $\delta$ nu este o funcție, mașina Turing ar putea efectua, în mod nedeterminist, oricare dintre mai multele tranziții posibile pentru starea curentă și simbolul aflat pe bandă sub capul de citire. În cazul unei mașini nedeterministe, există mai multe căi de execuție posibile pentru aceleasi date de intrare.

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

Note

Vezi și

Legături externe

,