Teoria Algorytmów i Obliczeń

Poruszane zagadnienia:

1. Maszyny Turinga, kodowanie maszyny Turinga, język rekurencyjny, język RP, hierarchia języków.
2. Język uniwersalny, język przekątniowy, dopełnienia języków, język kodów maszyn Turinga generujących puste języki i jego dopełnienie i ich miejsce w hierarchii języków, miejsce w hierarchii języków języka przekątniowego i jego dopełnienia, miejsce w hierarchii języka uniwersalnego.
3. Języki L_n i L_nr i ich miejsce w hierarchii, instrukcje maszyny RAM, dodawanie liczb binarnych przy pomocy maszyny RAM, szkic dowodu równoważności maszyny RAM i maszyny Turinga.
4. Funkcje pierwotnie rekursywne, definicja, przykłady. Definicja i dowód pierwotnej rekursywności dla minimum efektywnego.
5. Funkcja Ackermana, dowód, że funkcja Ackermana nie jest pierwotnie rekursywna.
6. Równoważność funkcji rekurencyjnych z maszynami Turinga.
7. Twierdzenie Cooka, twierdzenie Savitcha.
8. Sprawdzian