Turingov stroj
Turingovi strojevi su iznimno jednostavni apstraktni uređaji za manipulaciju znakovima (simbolima) koji - unatoč jednostavnosti dizajna - mogu biti prilagođeni da simuliraju logiku bilo kojeg računalnog algoritma (uz sadašnje poimanje algoritma). Opisao ih je 1936. Alan Turing. Turingovi strojevi ne koriste se u praktične svrhe, već u misaonim eksperimentima, gdje najvažniju primjenu nalaze u istraživanju granica mogućnosti izračunavanja računalnim algoritmima. Proučavanje njihovih svojstava pruža dalekosežne uvide u pitanja računalne znanosti i teorije složenosti.
Turingov stroj koji može simulirati bilo koji drugi Turingov stroj se zove Univerzalni Turingov stroj (UTS ili jednostavno univerzalni stroj). Više matematički orijentiranu definiciju sa sličnom "univerzalnom" prirodom je uveo Alonzo Church, čiji se rad na lambda računu isprepleo s Turingovim u formalnoj teoriji izračunljivosti poznatoj kao Church-Turingova teza. Teza povezuje strogu formalnu definiciju Turingovog stroja i intuitivne ideje izračunljivosti, te na taj način pruža preciznu definiciju algoritma ili 'mehaničkog postupka'.
Formalna definicija jednotračnog Turingovog stroja
urediSažeti formalni opis Turingovog stroja:
- "Turingov stroj je konačni automat povezan s vanjskim medijem za pohranu ili memoriranje" (Minsky (1967) p. 117)
- "Turingov stroj je esencijalno konačni sekvencijalni stroj koji ima mogućnost komuniciranja s vanjskim spremištem informacija" (Booth (1967), p. 354)
Konačni automat je predstavljen tablicom stanja i svojim registrom stanja. "Vanjski medij za pohranu" jest traka. Ulaz stroja je pročitani znak s trake. Izlaz stroja jest znak koji se piše na traku ili naredba za brisanje znaka te naredba za pomicanje trake ulijevo ili udesno.
Hopcroft i Ullman (1979, p. 148) formalno definiraju (jednotračni) Turingov stroj kao uređenu sedmorku gdje
- je konačan skup stanja
- je konačan skup znakova trake (abeceda trake)
- je istaknuti znak kojim se označava prazna ćelija (jedini znak kojem je dozvoljeno da bude ispisan na traci beskonačno mnogo puta u svakom koraku izračuna)
- , podskup skupa ne uključujući b je skup ulaznih znakova (ili ulazna abeceda)
- je parcijalna funkcija (nije definirana na cijeloj domeni) zvana funkcija prijelaza, gdje je L pomak ulijevo, R pomak udesno.
- je početno ili inicijalno stanje
- je skup prihvatljivih ili finalnih stanja
Izvori
uredi- Taylor L. Booth (1967), Sequential Machines and Automata Theory, John Wiley and Sons, Inc., New York.
- John Hopcroft and Jeffrey Ullman. 1979. Introduction to Automata Theory, Languages and Computation 1st edition izdanje. Addison-Wesley, Reading Mass. ISBN 0-201-02988-X.
|edition=
sadrži dodatni tekst (pomoć) - Alan Turing (1936), "On Computable Numbers, With an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, Volume 42 (1936). Eprint.
- Marvin Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., N.J., 1967.
- Siniša Srbljić. 2003. Jezični procesori 1. Element. ISBN 953-197-129-3
Teorija automata: formalni jezici i formalne gramatike | |||
---|---|---|---|
Chomskyjeva hijerarhija |
Gramatike | Jezici | Minimalni automat |
Tip 0 | Neograničenih produkcija | Rekurzivno prebrojiv | Turingov stroj |
n/a | (nema uobičajenog imena) | Rekurzivni | Odlučitelj |
Tip 1 | Kontekstno ovisna | Kontekstno ovisni | Linearno ograničen |
n/a | Indeksirana | Indeksirani | Ugniježđenog stoga |
Tip 2 | Kontekstno neovisna | Kontekstno neovisni | Nedeterministički potisni |
n/a | Deterministička kontekstno neovisna | Deterministički kontekstno neovisni | Deterministički potisni |
Tip 3 | Regularna | Regularni | Konačni |
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije. |