Elementarni aspekti izračunljivosti

diplomski rad

• Naslov (engleski): Elementary aspects of computability
• Autor: Petra Kraljević
• Mentor: Zvonko Iljazović (mentor)
• Član povjerenstva: Zvonko Iljazović (predsjednik povjerenstva)
• Član povjerenstva: Vedran Čačić (član povjerenstva)
• Član povjerenstva: Mladen Vuković (član povjerenstva)
• Član povjerenstva: Marko Horvat (č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-09-29, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom diplomskom radu proučavali smo neke elementarne aspekte izračunljivosti. U prvom poglavlju bavili smo se pojmom izračunljive funkcije: prvo smo definirali pojam programa pa pojam izračunljive funkcije, a zatim smo naveli neke primjere izračunljivih funkcija. Nadalje, proučavali smo presudoprograme i makro-programe. U nastavku smo obradili pojam makro-izračunljivosti te dokazali da je svaka makro-izračunljiva funkcija izračunljiva. U drugom poglavlju proučavali smo rekurzivne funkcije. Najprije smo definirali operatore kompozicije i primitivne rekurzije, a nakon toga i primitivno rekurzivne funkcije te smo pokazali neke primjere tih funkcija. Nakon uvodenja \(\mu\)-operatora, definirali smo rekurzivne funkcije te dokazali da je svaka rekurzivna funkcija izračunljiva. U trećem poglavlju definirali smo prebrojive skupove, a zatim dokazali neka osnovna svojstva tih skupova. Proučavali smo i konačne nizove te naposlijetku dokazali glavni rezultat trećeg poglavlja: skup svih izračunljivih funkcija je prebrojiv. Na samom smo kraju izveli zaključak da onda postoje funkcije koje nisu izračunljive.

Sažetak (engleski)

In this thesis, we studied some elementary aspects of computability. In the first chapter, we dealt with the concept of a computable function: first we defined the notion of a program, then the notion of a computable function, and then we gave some examples of computable functions. Furthermore, we studied the pseudoprograms and the macro-programs. In the following, we presented the concept of macro-computability and then we proved that every macro-computable function is computable. In the second chapter, we studied recursive functions. Firstly we defined operators such as composition and primitive recursion and we defined primitive recursive functions after which we showed some examples of these functions. After introducing the \(\mu\)-operator, we defined recursive functions and proved that every recursive function is computable. In the third chapter, we defined countable sets and then proved some basic characteristics of these sets. We also studied the finite strings and finally proved the main result of the third chapter: the set of all computable functions is countable. At the very end, we concluded that then there are functions that are not computable.

• Ključne riječi: izračunljiva funkcija; presudoprogram; makro-program
• Ključne riječi (engleski): computable function; pseudoprograms; macro-programs
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:529443
• Studijski program: Naziv: Matematika; smjerovi: nastavnički; Smjer: nastavnički; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra edukacije matematike (mag. educ. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2021-02-26 12:41:07