Introduction to the precise definition of an algorithm and machines that verify its correctness. Deterministic and non-deterministic algorithms and their terminality. Students will be introduced to similar memory requirements. Algorithmic functions (efficient and computable) will be treated in particular.

Various problems can be simply classified as those for which we know the solution procedures and therefore may be algorithmically solvable. There is a possibility that we are not able to provide a solution. Course participants will gain the basics for recognizing the subjective inability to provide a solution or the potential impossibility of solving.

1. Historical overview of computability. Intuitive notion of algorithm 2. Turing machine - TM. Informal description of TM. TM and functions. Turing non-computable functions. 3. Classification of Turing machines and their implementation in C++. 4. Recursive functions and their relation to intuitively computable functions. 5. Partially recursive functions. 6. Turing computable and partially recursive functions. 7. Church's thesis. 8. Relative computability. 9. Predicate calculus. Decidable predicates. 10. On partially decidable predicates.

1. Parts of the Turing machine. Turing machine program. 2. Running the Turing machine simulator and distinguishing deterministic and non-deterministic instructions. 3. Turing machine configuration and programs. 4. Arithmetic functions and the Turing machine. 5. Primitive recursive functions. Factorial and f(0)=m, general case of defining f(n+1)=g(f(n),n). 6. Examples of the general case. 7. Diophantine equations. 8. Hilbert's tenth problem.

There are no conditions.

gcc, C, C++

Total assigned hours: 65

New material: 45
Elaboration and examples (recapitulation): 5

Auditory exercises: 0
Laboratory exercises: 0
Calculation tasks: 0
Seminar paper: 0
Project: 0
Consultations: 0
Discussion/workshop: 0
Research study work: 0

Review and grading of calculation tasks: 0
Review and grading of lab reports: 0
Review and grading of seminar papers: 15
Review and grading of the project: 0
Test: 0
Test: 0
Final exam: 0

Activity during lectures: 0
Test/test: 0
Laboratory practice: 0
Calculation tasks: 0
Seminar paper: 70
Project: 0
Final exam: 30
Requirement for taking the exam (required number of points): 0

Z. Ognjanović, N. Krdžavac, Uvod u teorijsko računarstvo, FON, Beograd, 2004.; C. Papadimitriou, Computational complexity, Addison-Wesley, 1995.; Ž. Mijajlović, Z. Marković, K. Došen, Hilbertovi problemi i logika, Zavod za udžbenike i nastavna sredstva, Beograd, 1986.; J.Hopcroft, J.Ullman, Formal languages and their relation to automata, Addison-Wesley, 1969.; N. Cutland, Computability, an introduction to recursive function theory, Cambridge university press, 1986.