Mașină care se termină întotdeauna

În teoria calculabilității, o mașină care se termină întotdeauna , numită și un decider ^[1] sau o mașină totală Turing , ^[2] este un anumit tip de mașină Turing pentru care, spre deosebire de modelul general, există o garanție că se termină de fiecare intrare.

Deoarece se oprește întotdeauna, mașina este capabilă să decidă dacă un șir dat este membru al unui limbaj formal . Clasa de limbi care poate fi decisă de mașini de acest tip este exact setul de limbaje recursive . Având în vedere problema de oprire , determinarea dacă o mașină Turing arbitrară se termină întotdeauna este nedecidabilă , nu există un algoritm care să o determine. ^{[ Construcția sintactică implicată face înțelegerea acestei perioade extrem de dificilă. ]}

Funcții calculabile de mașinile totale Turing

În practică, este posibil să construiți o mașină care se termină întotdeauna și care calculează deja o mulțime de funcții interesante, cum ar fi, de exemplu, atunci când limitați capacitățile de control al fluxului , astfel încât niciun program să nu determine mașina să intre într-o buclă infinită . ^{[ Construcția sintactică implicată face înțelegerea acestei perioade extrem de dificilă. ]} De exemplu, un arbore de decizie finit nu conține cicluri și, prin urmare, se termină în mod natural. Mașina nu este obligată să nu poată efectua cicluri. Dacă limităm buclele la o limită predictibilă bine definită (cum ar fi bucla FOR în BASIC ), putem exprima toate funcțiile recursive primitive ^[3] . Un exemplu al acestei mașini este oferit de limbajul de programare a jucăriilor PL- {GOTO} de la Brainerd și Landweber ^[4] .

În plus, puteți defini un program în care vă puteți asigura că funcțiile și mai sofisticate se termină întotdeauna. De exemplu, funcția Ackermann , care nu este recursivă primitivă, se termină întotdeauna și această proprietate poate fi garantată considerând-o un sistem de rescriere cu o bună ordine a argumentelor sale ^[5] . Este asemănător cu utilizarea inducției matematice pentru a demonstra că o funcție recursivă ajunge întotdeauna la cazul său de bază.

Notă

^ Sipser, M. (1996), Introducere în teoria calculelor, PWS Publishing Co.
^ Kozen, DC (1997), Automate and Computability, Springer.
^ Meyer, AR, Ritchie, DM (1967), Complexitatea programelor de buclă , Proc. Of the ACM National Meetings, 465.
^ Brainerd, WS, Landweber, LH (1974), Theory of Computation , Wiley.
^ Ohlebusch, E. (2002), Subiecte avansate în rescrierea termenului, Springer. pagina 67

Teoria automatelor : limbaje formale și gramatici formale
Ierarhia Chomsky	Gramatica formală	Limba	Automat minim
Tipul-0	(nelimitat)	Recursiv enumerabil	Mașină Turing
	(nelimitat)	Recursiv	Decider
Tipul 1	Context dependent	Context dependent	Automat liniar
Tipul 2	Fără context	Fără context	Automat cu baterie ND
Tipul 3	Regulat	Regulat	Stări finite
Fiecare categorie de limbă sau gramatică este un subset adecvat al categoriei imediat deasupra acesteia.

[1] Sipser, M. (1996), Introducere în teoria calculelor, PWS Publishing Co.

[2] Kozen, DC (1997), Automate and Computability, Springer.

[3] Meyer, AR, Ritchie, DM (1967), Complexitatea programelor de buclă , Proc. Of the ACM National Meetings, 465.

[4] Brainerd, WS, Landweber, LH (1974), Theory of Computation , Wiley.

[5] Ohlebusch, E. (2002), Subiecte avansate în rescrierea termenului, Springer. pagina 67

[1]

[2]

[3]

[4]

[5]