Izračunljive strukture

diplomski rad

• Autor: Maja Vreš
• Mentor: Zvonko Iljazović (mentor)
• Član povjerenstva: Zvonko Iljazović (predsjednik povjerenstva)
• Član povjerenstva: Robert Manger (član povjerenstva)
• Član povjerenstva: Mladen Vuković (član povjerenstva)
• Član povjerenstva: Matija Bašić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2020-02-28, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U radu smo proučili pojam izračunljivih funkcija, povezan s pojmom programa. Zatim smo uveli pojam rekurzivnih funkcija. Dokazali smo da je svaka rekurzivna funkcija izračunljiva, te obrat te tvrdnje. Idući pojam koji smo uveli je pojam parcijalno izračunljive funkcije koju povezujemo uz ranije definiranu izračunljivu funkciju. U zadnjem poglavlju promatrali smo parcijalno rekurzivne funkcije i njihova svojstva, uz korištenje svojstava rekurzivnih funkcija. Konačno, dokazali smo ekvivalenciju parcijalno rekurzivnih funkcija i parcijalno izračunljivih funkcija. Na kraju smo dobili važan rezultat, da postoji rekurzivno prebrojiv skup koji nije rekurzivan.

Sažetak (engleski)

In this paper we studied the computable functions, related to the concept of the program. Then we introduced the concept of the recursive functions. We proved that every recursive function is computable, and reverse. The next concept we introduced is the concept of the partially computable functions which we related to the earlier introduced computable functions. In the last chapter we studied the partially recursive functions and their properties, by using the properties of the recursive functions. Finally, we proved the equivalence of the partially recursive functions and the partially computable functions. In the end we got important result, that there is a recursively countable set that is not recursive.

• Ključne riječi: izračunljive funkcije; rekurzivne funkcije; parcijalno rekurzivne funkcije
• Ključne riječi (engleski): computable functions; recursive functions; partially recursive functions
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:817234
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup; Datum isteka embarga: 2021-10-29
• Datum i vrijeme pohrane: 2020-10-29 08:52:54