Naslov Rekurzivne funkcije
Autor Brigita Švec
Mentor Zvonko Iljazović (mentor)
Član povjerenstva Zvonko Iljazović (predsjednik povjerenstva)
Član povjerenstva Mea Bombardelli (član povjerenstva)
Član povjerenstva Sanja Varošanec (član povjerenstva)
Član povjerenstva Filip Najman (č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 2014-09-24, Hrvatska
Znanstveno / umjetničko područje, polje i grana PRIRODNE ZNANOSTI Matematika
Sažetak U ovom radu smo se bavili RAM izračunljivim funkcijama, primitivno i parcijalno rekurzivnim te rekurzivnim funkcijama. Pokazali smo da je skup RAM izračunljivih funkcija zatvoren na kompoziciju funkcija, primitivnu rekurziju i \(\mu\) operator. Također smo pokazali da je svaka primitivno rekurzivna ujedno i parcijalno rekurzivna funkcija pa i rekurzivna (jer je totalna). Zanimljivo je da se svaka parcijalno rekurzivna funkcija zapravo može u konačno mnogo koraka dobiti od inicijalnih funkcija primjenom kompozicije, primitivne rekurzije i točno jednom primjenom \(\mu\) operatora (što slijedi iz Kleenijevog teorema o nor- malnoj formi). Vidjeli smo da su skup RAM izračunljivih i skup parcijalno rekurzivnih funkcija zapravo jednaki. Pokušali smo proširiti parcijalno rekurzivnu funkciju do rekurzivne i vidjeli da je to moguće ukoliko je domena funkcije rekurzivan skup. Pokazali smo da je svaki rekurzivan skup rekurzivno prebrojiv i da postoji rekurzivno prebrojiv skup koji nije rekurzivan (domena parcijalno rekurzivne funkcije koja se ne može proširiti do rekurzivne). Koristeći činjenice da se svaki \(x \in \mathbb{Z}\) i \(y \in \mathbb{Q}\) mogu zapisati kao \(x=(-1)^{c_1} \cdot a_1, \: y=(-1)^{c_2} \cdot \frac{a_2}{b_2}, \: a_1, a_2, b_2, c_1, c_2 \in \mathbb{N}\) i da je \(\mathbb{Q}\) gust u \(\mathbb{R}\), proširili smo pojam rekurzivne funkcije i na funkcije čije su kodomene \(\mathbb{Z}, \mathbb{Q}\) i \(\mathbb{R}\) te pokazali da i te funkcije imaju lijepa svojstva (npr. zbroj, umnožak i apsolutna vrijednost rekurzivnih su također rekurzivne funkcije).
Sažetak (engleski) In this thesis, we have studied the RAM computable functions, primitive and partial recursive and recursive functions. We have shown that the set of RAM computable functions is closed on the composition of functions, primitive recursion and \(\mu\) operator. We have also shown that every primitive recursive function is also partial recursive function and recursive (because it is total). What is interesting is that every partial recursive function can actually be, in a finite number of steps, obtained from the initial functions by using composition, primitive recursion and exactly one usage of \(\mu\) operator. We have seen that the set of RAM computable functions and a set of partial recursive functions are equal. We tried to extend a partial recursive function to recursive and saw that it is possible if the domain of the function is a recursive set. We have shown that every recursive set is also recursively enumerable set and that exists recursively enumerable set that is not recursive (domain of the partial recursive function that can not be extended to a recursive). Using the fact that every \(x \in \mathbb{Z}\) and \(y \in \mathbb{Q}\) can be shown as \(x=(-1)^{c_1} \cdot a_1, \: y=(-1)^{c_2} \cdot \frac{a_2}{b_2}, \: a_1, a_2, b_2, c_1, c_2 \in \mathbb{N}\) and that \(\mathbb{Q}\) is dense in \(\mathbb{R}\), we have extended the term of recursive functions to functions whose codomains are \(\mathbb{Z}, \mathbb{Q}\) and \(\mathbb{R}\), and shown that these functions have good characteristics (eg. the sum, the product and the absolute value of recursive functions are also recursive functions).
Ključne riječi
RAM izračunljivie funkcije
primitivno rekurzivna funkcija
parcijalno rekurzivna funkcija
rekurzivna funkcija
Ključne riječi (engleski)
RAM computable functions
primitive recursive functions
partial recursive functions
recursive functions
Jezik hrvatski
URN:NBN urn:nbn:hr:217:457441
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
Uvjeti korištenja
Datum i vrijeme pohrane 2019-02-15 07:41:50