Anketa

Na ovoj stranici trenutno nije odabrana niti jedna anketa!

Repozitorij

Repozitorij je prazan

Izračunljivost

Šifra: 93019
ECTS: 5.0
Nositelji: doc. dr. sc. Vedran Čačić - Predavanja
Engleski jezik:

1,0,0

Nastava se odvija na hrvatskom jeziku u svim svojim elementima, a stranim studentima koji su pridruženi mješovitoj grupi nudi se mogućnost savladavanja predmeta pomoću dodatnih izravnih konzultacija s nastavnikom i asistentima na engleskom jeziku. Pri tome, nastavnik stranog studenta upućuje na odgovarajuću literaturu na engleskom jeziku te mu osigurava mogućnost polaganja predmeta na engleskom jeziku.
Opterećenje:

1. komponenta

Vrsta nastaveUkupno
Predavanja 45
* Opterećenje je izraženo u školskim satima (1 školski sat = 45 minuta)
Opis predmeta:
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.
Literatura:
  1. J. R. Shoenfiled: Recursion Theory
  2. R. Smullyan: Gödel's Incompleteness Theorems
  3. E. Mendelson: Introduction to Mathematical Logic
  4. P. Odifreddi: Classical Recursion Theory
  5. M. Sipser: Introduction to the Theory of Computation
Preduvjeti za:
Upis predmeta :
Položen : Matematička logika
3. semestar
Računarstvo - Redovni Studij - Matematika; smjer: nastavnički

4. semestar
Računarstvo - Redovni Studij - Matematika; smjer: nastavnički
Termini konzultacija:

SADRŽAJ

Link na stranicu kolegija: 


Obavijesti