Elméleti számítástudomány

1. F-algebrák, adattípusok kategorális definíciója. Backus--Naur-forma. Implikációs, intuicionista és klasszikus logikák természetes levezetési stílusban.
2. Levezetéskódok és redukciójuk az intuicionista logikában. Normalizációs algoritmus és normálforma tétel az implikációs logikában.
3. Típusmentes lambda kalkulus, de Bruijn indexek. Normál termek. Parallel beta redukció, Church--Rosser-tétel.
4. Inhabitációs algoritmus az egyszerű típusos lambda kalkulusban, bizonyításkereső eljárások, Curry--Howard- és Curry--Howard--Lambek-izomorfizmus.



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.