Fogalmak:

0. Néhány jelölés és definíció:
	A lexikografikus rendezés
	növekvő rendezés
	f = O(g)
1. Számítási modellek:
	A Turing-gép
	T a p programmal szimulálja S-et
	Univerzális Turing-gép
	Boole-függvény
	Boole-polinom
	Diszjunktív normálforma
	logikai hálózat
2. Algoritmikus eldönthetőség:
	rekurzív függvény
	rekurzív nyelv
	rekurzíve fölsorolható nyelv
	Turing-gép leírása
	megállási feladat
	nyelvek triviális tulajdonsága
	formális rendszer (elmélet)
	konzisztens elmélet
	teljes elmélet
3. Tár és idő:
	Turing-gép időigénye
	Turing-gép tárigénye
	Turing-gép polinomiális
	DTIME(f(n))
	PTIME (P)
	teljesen időkonstruálható függvény
	jól számolható függvény

Tételek:
1. Számítási modellek:	
	kapcsolat a RAM és a Turing gép között (1.2.2. és 1.2.3. Tétel)
	kapcsolat a Turing-gépek és a Boole-hálózatok között (1.3.1. Tétel)
2. Algoritmikus eldönthetőség:
	Church-tézis
	A rekurzív és rekurzíve felsorolható nyelvek kapcsolata (2.1.2. Lemma és a 2.1.3. Tétel)
	Rice Tétele
	Soroljon fel 3 algoritmikusan eldönthetetlen problémát
	Gödel nem-teljességi tétele (2.3.2. Tétel)
	Gödel teljességi tétele (2.3.3. Tétel)
3. Tár és idő:
	Soroljon fel 3 polinomiális idejű kombinatorikai algoritmust
	Soroljon fel 3 polinomiális idejű aritmetikai algoritmust
	Az euklideszi algoritmus polinomiális idejű (3.1.1. Lemma)
	A moduláris hatványozás polinomiális idejű (3.1.2. Lemma)
	Soroljon fel 3 polinomiális idejű lineáris algebrai algoritmust
	Lineáris Gyorsítási Tétel
	Idő-hierarchia Tétel
	Hézag Tétel
	Gyorsítási Tétel