Anketa

Na ovoj stranici trenutno nije odabrana niti jedna anketa!

Repozitorij

Repozitorij je prazan

Izračunljivost

Šifra: 92912
ECTS: 5.0
Nositelji: doc. dr. sc. Vedran Čačić
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:
Preduvjeti za:
Upis predmeta :
Položen : Matematička logika
1. semestar
Izborni predmet 1, 2 - Redovni Studij - Teorijska matematika

2. semestar Ne predaje se
Izborni predmet 1, 2 - Redovni Studij - Teorijska matematika

3. semestar
Izborni predmet 3, 4 - Redovni Studij - Teorijska matematika

4. semestar Ne predaje se
Izborni predmet 3, 4 - Redovni Studij - Teorijska matematika
Termini konzultacija:

Linkovi

Link na stranicu kolegija: https://web.math.pmf.unizg.hr/~veky/izr/

Link na Moodle za akademsku godinu 2020/21.: https://moodle.srce.hr/2020-2021/course/view.php?id=79047


Obavijesti