INFORMATIKAI KAR DOKTORI PROGRAM
SZIGORLATI TEMATIKA

Számítási modellek és absztrakt matematikai gépek


Rekurzív függvények, Turing-kiszámítható függvények, RAM -géppel kiszámítható függvények. A három számítási modell egyenértékûsége.
Matematikai gépek, mint nyelvfelismerõk. A Chomsky-hierarchiának megfelelõ géphierarchia.
A véges felismerõ automaták különbözõ változatai (determinisztikus, nemdeterminisztikus, epszilon-átmenetes nemdeterminisztikus, alternáló, kétirányú) és egyenértékûségük. Minimális véges determinisztikus automaták. Véges szekvenciális automata (Mealy, Moore), kapcsolatuk az automata leképezésekkel.
Sztochasztikus felismerõ automaták és sztochasztikus nyelvek. Nem reguláris sztochasztikus nyelvek létezése és regularitási kritériumok sztochasztikus automatákra. Sztochasztikus szekvenciális gépek (Mealy, Moore) és sztochasztikus leképezések. Sztochasztikus automaták minimalizálása.
Veremautomaták egy, illetve több veremtárral. Determinisztikus veremautomaták és kapcsolatuk a nemdeterminisztikus alapváltozattal.
A Post-gép.
A Turing-gépek különbözõ változatai (egyszalagos, több olvasó fejû, többszalagos, nemdeterminisztikus), egyenértékûségük.
A Turing-gép, a Post-gép és a kettõ-verem egyenértékûsége a nyelvfelismerés szempontjából.
Az univerzális Turing-gép és a megállási probléma algoritmikus eldönthetetlensége.
Sejt-automaták. Az életjáték. A tûzparancs-szinkronizáció. A sejt-automaták és Turing-gépek kölcsönös szimulációja.


Irodalom:

Handbook of Formal Languages, Springer-Verlag, Berlin, Heidelberg, New York 1997.
Jozef Gruska (Ed.), Foundation of Computing, International Thomson Computer Press, 1997.
Daniel I. A. Cohen, Introduction to Computer Theory, John Wiley & Sons, Inc., New Yolk, 1991.
C. H. Papadimitriu, Computational Complexity, Addison-Wesley Publishing Company, Inc., 1994. (magyar fordítása megjelent 1999-ben a Novodat kiadásában, fordító-szerkesztõ Ésik Zoltán).
A. Salomaa, Theory of Automata, Academic Press, New York, 1969.
J. E. Hopcroft, J. D. Ullman, Fomal Languages and Their Relations to Automata, Addison-Wesley, Reading, Mass., 1969
J. E. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, Mass., 1979