Rekurzivne funkcije

Švec, Brigita (2014) Rekurzivne funkcije. Diploma thesis, Faculty of Science > Department of Mathematics.

[img]
Preview
PDF
Language: Croatian

Download (392kB) | Preview

Abstract

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).

Item Type: Thesis (Diploma thesis)
Supervisor: Iljazović, Zvonko
Date: 2014
Number of Pages: 75
Subjects: NATURAL SCIENCES > Mathematics
Divisions: Faculty of Science > Department of Mathematics
Depositing User: Iva Prah
Date Deposited: 14 Jul 2015 11:14
Last Modified: 14 Jul 2015 11:14
URI: http://digre.pmf.unizg.hr/id/eprint/4123

Actions (login required)

View Item View Item