Models of Computation
Lecture: Tuesday 14:15  15:45, room 1.64, north builing
Practice class: Tuesday 16:00  17:30, room 1.64, north builing
Lecturer:
Tamás Lukovszki
Content:
Classical models of computing: finite automata, pushdown automata,
Turing machines(TM), variants of TMs, partial recursive functions,
undecidability, time and space complexity, random access machines (RAM), circuits, cellular automata.
Models of parallel and distributed computing. Unconventional models of computing (natural computing).
Requirements, evaluation:
1. Active partitipation and work in pactice classes: solving and discussing excercises
2. passing >=50% of the 10 min. tests at the beginning of the practice classes
3. Successful exams (grade is computed as average of 2 exams)
Important dates:
 midterm test/exam (written): 20221018
 final test/exam (written): 20221122
 repeat exam (second trial exam in case of unsuccessful exam): 20221129
Slides:
 
foliák 
1. Introduction 
PDF

2. Grammars 
PDF

3. Grammars, Lsystems 
PDF

4. Regular expressions, finite automata 
PDF

5. Finite automata, DFA, NFA, minimal DFA 
PDF

6. Probabilistic automata, Pushdown automata, Contextfree languages 
PDF

7. Turing machines, Variants, ChurchTuring thesis, Recursively enumerable languages 
PDF

8: Diagonalization, Decision problems, undecidability 
PDF

Literature:
J. E. Savage, Models of Computation: Exploring the Power of Computing,
Brown University, 1998.
https://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation.pdf
M. Sipser, Introduction to the Theory of Computation, 3rd edition, Cengage, 2012.