Rekurzivne funkcije

diplomski rad

• 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
• Datum i vrijeme pohrane: 2019-02-15 07:41:50