Izračunljive strukture

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