1. komponenta

Vrsta nastave	Ukupno

* 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.