5.Turing-gép és változatai (több
szalagos, illetve nemdeterminisztikus), ezek ekvivalenciája.
Church--Turing-tézis.
6.Rekurzív és rekurzívan felsorolható
nyelvek. Az R, RE, coRE nyelvosztályok, zártsági tulajdonságaik.
7.Nevezetes nyelvek és osztályuk:
diagonális, univerzális és megállási nyelv, a semmit el nem fogadó
Turing-gépek nyelve. Rice-tétel. PCP és Dominó nyelv.
8.Idő- és tárkorlátos Turing-gépek, idő-
és tárosztályok. Tár-idő tétel. A P, NP, coNP, PSPACE és EXPTIME
osztályok, ezek kapcsolata egymással és az R osztállyal.