Izračunljive strukture

master's thesis

• Author: Maja Vreš
• Mentor: Zvonko Iljazović (mentor)
• Committee member: Zvonko Iljazović (predsjednik povjerenstva)
• Committee member: Robert Manger (član povjerenstva)
• Committee member: Mladen Vuković (član povjerenstva)
• Committee member: Matija Bašić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2020-02-28, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U radu smo proučili pojam izračunljivih funkcija, povezan s pojmom programa. Zatim smo uveli pojam rekurzivnih funkcija. Dokazali smo da je svaka rekurzivna funkcija izračunljiva, te obrat te tvrdnje. Idući pojam koji smo uveli je pojam parcijalno izračunljive funkcije koju povezujemo uz ranije definiranu izračunljivu funkciju. U zadnjem poglavlju promatrali smo parcijalno rekurzivne funkcije i njihova svojstva, uz korištenje svojstava rekurzivnih funkcija. Konačno, dokazali smo ekvivalenciju parcijalno rekurzivnih funkcija i parcijalno izračunljivih funkcija. Na kraju smo dobili važan rezultat, da postoji rekurzivno prebrojiv skup koji nije rekurzivan.

Abstract (english)

In this paper we studied the computable functions, related to the concept of the program. Then we introduced the concept of the recursive functions. We proved that every recursive function is computable, and reverse. The next concept we introduced is the concept of the partially computable functions which we related to the earlier introduced computable functions. In the last chapter we studied the partially recursive functions and their properties, by using the properties of the recursive functions. Finally, we proved the equivalence of the partially recursive functions and the partially computable functions. In the end we got important result, that there is a recursively countable set that is not recursive.

• Keywords: izračunljive funkcije; rekurzivne funkcije; parcijalno rekurzivne funkcije
• Keywords (english): computable functions; recursive functions; partially recursive functions
• Language: croatian
• URN:NBN: urn:nbn:hr:217:817234
• 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; Embargo expiration date: 2021-10-29
• Created on: 2020-10-29 08:52:54