Title Rekurzivne funkcije
Author Brigita Švec
Mentor Zvonko Iljazović (mentor)
Committee member Zvonko Iljazović (predsjednik povjerenstva)
Committee member Mea Bombardelli (član povjerenstva)
Committee member Sanja Varošanec (član povjerenstva)
Committee member Filip Najman (član povjerenstva)
Granter University of Zagreb Faculty of Science (Department of Mathematics) Zagreb
Defense date and country 2014-09-24, Croatia
Scientific / art field, discipline and subdiscipline NATURAL SCIENCES Mathematics
Abstract 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).
Abstract (english) 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).
Keywords
RAM izračunljivie funkcije
primitivno rekurzivna funkcija
parcijalno rekurzivna funkcija
rekurzivna funkcija
Keywords (english)
RAM computable functions
primitive recursive functions
partial recursive functions
recursive functions
Language croatian
URN:NBN urn:nbn:hr:217:457441
Study programme Title: Mathematical Statistics Study programme type: university Study level: graduate Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
Type of resource Text
File origin Born digital
Access conditions Open access
Terms of use
Created on 2019-02-15 07:41:50