Elementarni aspekti izračunljivosti

In this thesis, we studied some elementary aspects of computability. In the first chapter, we dealt with the concept of a computable function: first we defined the notion of a program, then the notion of a computable function, and then we gave some examples of computable functions. Furthermore, we studied the pseudoprograms and the macro-programs. In the following, we presented the concept of macro-computability and then we proved that every macro-computable function is computable. In the second chapter, we studied recursive functions. Firstly we defined operators such as composition and primitive recursion and we defined primitive recursive functions after which we showed some examples of these functions. After introducing the (\mi\)-operator, we defined recursive functions and proved that every recursive function is computable. In the third chapter, we defined countable sets and then proved some basic characteristics of these sets. We also studied the finite strings and finally proved the main result of the third chapter: the set of all computable functions is countable. At the very end, we concluded that then there are functions that are not computable.