Izračunljivost

 

Predavanja i vježbe

Izvedbeni plan 

Folije s predavanja

 

Dodatni materijali

Uvod u teoriju izračunljivosti

Logika i izračunljivost

 

Ispiti i kolokviji

Primjeri ispita i kolokvija

Rezultati ispita i kolokvija

Nastavnik: dr.sc. Milica Klaričić Bakula

Raspored predavanja:  srijedom od 17.00 do 19.00 sati u sobi A302, FESB

Raspored vježbi:   srijedom od 19.00 do 20.00 sati u sobi A302, FESB

  


Raspored održavanja kolokvija

Prvi kolokvij: xxxx
Drugi kolokvij: xxxx

Raspored održavanja ispita

Pismeni ispiti: xxxx
Usmeni ispit:  po dogovoru.

 


Literatura

  • M. Vuković, Izračunljivost, skripta, PMF-MO, Zagreb, 2007.
  • M. Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997.
  • G. Boolos, J. Burgess, R. C. Jeffrey, Computability and Logic, Cabridge University Press, 2007.
  • J. R. Shoenfield, Recursion Theory, Springer-Verlag, 1993.
  • R. Smullyan, Gödel's Incopleteness Theorems, Oxford University Press, 1992.
  • P. Odifreddi, Classical Recursion Theory, North-Holland, 1987.
  • E. Mendelson, Introduction to Mathematical Logic, D. Van Nostrand Company, Inc. Princeton, 1997.
     

Sadržaj kolegija

  1. Uvod: Povijesna motivacija. Primjeri algoritma. Primjeri nerješivih problema. Opisna definicija algoritma i izračunljive funkcije.
  2. RAM-stroj: Definicija RAM-stroja i primjeri. RAM-izračunljive funkcije. Makro-stroj.
  3. Parcijalno rekurzivne funkcije: Primitivno rekurzivne funkcije. Ackermanova funkcija. Istaknuti primjer i svojstva rekurzivnih funkcija. Dokaz da je svaka rekurzivna funkcija RAM-izračunljiva. Turingov stroj.
  4. Kodiranje konačnih nizova: Kodiranje pomoću prostih brojeva. Cantorova funkcija. Primjene. β-funkcija. Simultana primitivna rekurzija. Kontrakcija.
  5. Indeksi: Kodiranje RAM-stroja. Kleenejev teorem o normalnoj formi. Indeks funkcije. Teorem o parametru. Teorem o rekurziji. Teorem o čvrstoj točki. Riceov teorem.
  6. Churchova teza: Egzistencija neizračunljive funkcije. Problem zaustavljanja. Churchov teorem o neodlučivosti logike prvog reda.
  7. Aritmetička hijerarhija: Aritmetička relacija. Kontrakcija kvantifikatora. Alternirajući prefiks. Definicija klasa Σ,Π i Δ. Teorem o aritmetičkom prebrojavanju. Teorem o aritmetičkoj hijerarhiji.
  8. Rekurzivno prebrojivi skupovi: Teorem o RE-parametrizaciji. Teorem o selektoru. Teorem o grafu. Postov teorem.
  9. Gödelovi teoremi nepotpunosti:  Peanova aritmetika. Reprezentabilnost funkcija i relacija. Aritmetizacija sintakse. (gödelizacija). Tarskijev teorem. Dijagonalna lema. Gödelov prvi teorem o nepotpunosti. Konzistentnost. ω-konzistentnost. Predikat dokazivosti. Löbovi uvjeti dokazivosti. Gödelov drugi teorem o nepotpunosti.
     

Način polaganja ispita

Ispit je cjelovit i sastoji se od pisane zadaće (rješavanje zadataka) i usmenog ispita (provjera teorijskog znanja). Pisana zadaća je eliminacijski dio ispita, to jest student može pristupiti usmenom ispitu ako postigne barem 50% bodova na pisanoj zadaći.

Student se može osloboditi pismenog ispita ako tijekom semestra položi dva kolokvija. Za pozitivnu ocjenu potrebno je u prosjeku postići barem 50% bodova, s tim što na nijednom kolokviju student ne smije postići manje od 30% bodova. Rezultati kolokvija vrijede za dva ispitna roka u zimskom semestru. Ovisno o broju studenata koji upišu ovaj kolegij u tekućoj akademskoj godini pristup usmenom ispitu može se postići i izradom domaćih i seminarskih radova.