1. komponenta

Vrsta nastave	Ukupno
Predavanja	45

* Opterećenje je izraženo u školskim satima (1 školski sat = 45 minuta)

CILJ KOLEGIJA: Osnovni cilj kolegija je studente upoznati s nekoliko formalnih koncepata algoritma (RAM-stroj, parcijalno rekurzivne funkcije i Turingov stroj). Također, u kolegiju se obrađuju osnove teorije rekurzivnih funkcija, a na samom kraju studenti bi trebali razumjeti u čemu se sastoji rješenje Hilbertovog 10. problema, te dokaz Godelovih teorema nepotpunosti.

NASTAVNI SADRŽAJI:
1. Uvod. Primjeri algoritama (Euklidov algoritam, Hornerova shema ...); primjeri nerješivih problema (Hilbertov 10. problem i problem riječi) kao motivacija za nužnost strogog definiranja pojma algoritma.
2. RAM-stroj. Definicija i primjeri; RAM-izračunljive funkcije; makro-stroj.
3. Parcijalno rekurzivne funkcije. Primitivno rekurzivne funkcije, Ackermanova funkcija, definicija klase parcijalno rekurzivnih funkcija, dokaz da je svaka parcijalno rekurzivna funkcija RAM-izračunljiva; istaknuti primjeri rekurzivnih funkcija i jednostavna svojstva; rekurzivni skupovi i relacija. (Na vježbama se uvodi pojam Turingovog stroja, te ističe nekoliko primjera).
4. Kodiranje konačnih nizova i primjene. Kodiranje pomoću prostih brojeva, Cantorova funkcija, beta-funkcija; simultana primitivna rekurzija; kontrakcija; course-of-values rekurzija.
5. Indeksi. Kodiranje RAM-stroja; Kleenijev teorem o normalnoj formi za parcijalno rekurzivne funkcije, indeks funkcije; teorem o parametru, teorem rekurzije, teorem o fiksnoj točki, Riceov teorem.
6. Churchova teza. Egzistencija neizračunljive funkcije; halting problem; Churchov teorem o neodlučivosti logike prvog reda.
7. Aritmetička hijerarhija. Aritmetička relacija, kontrakcija kvantifikatora, alternirajući prefiks, definicija klasa; teorem o aritemtičkom prebrajanju i teorem o aritmetičkoj hijerarhiji.
8. Rekurzivno prebrojivi skupovi. Teorem o RE-parametrizaciji; teorem o selektoru; teorem o grafu; Postov teorem; skica rješenja Hilbertovog 10. problema.
9. Godelovi teoremi nepotpunosti. Peanova aritmetika; reprezentabilnost funkcija i relacija; aritmetizacija sintakse (gedelizacija); Tarskijev teorem o nedefinabilnosti aritmetičke istine; dijagonalna lema; Gödelov prvi teorem nepotpunosti; konzistentnost i omega-konzistentnost; predikat dokazivosti; Löbovi uvjeti dokazivosti; Godelov drugi teorem nepotpunosti.

1. Recursion Theory, J. R. Shoenfiled, Springer Verlag, 1993.
2. Gödel's Incompleteness Theorems, R. Smullyan, Oxford University Press, 1992.
3. Introduction to Mathematical Logic, E. Mendelson, D. Van Nostrand Company, 1997.
4. Classical Recursion Theory, P. Odifreddi, North-Holland, 1987.
5. Introduction to the Theory of Computation, M. Sipser, PWS Publishing Company, 1996.

Upis predmeta :
Položen : Matematička logika

Obavezni predmet - Redovni Studij - Računarstvo i matematika