1. komponenta

Lecture type	Total
Lectures	45

* Load is given in academic hour (1 academic hour = 45 minutes)

COURSE AIMS AND OBJECTIVES: The main aim of the course is to introduce a few formal definiton of the notion of algorithm (RAM-machine, partial recursive functions and Turing machine). The basics of the theory of recursive functions are studied.
At the end of course the students should be understand what is a content of the solution of Hilbert tenth problem, and proof of Godel incompleteness theorem.

COURSE DESCRIPTION AND SYLLABUS:
Introduction: examples of algorithms (Euklid's algorithm, Horner method,...); examples of unsolvable problems (Hilbert tenth problem and word problem) as a motivation for a formal definition of the notion of algorithm.
RAM-machine: definition and examples; RAM-computable functions; macro-machine.
Partial recursive function: primitive recursive functions, Ackerman function, definition of the class of partial recursive functions, the proof that each partial recursive function is RAM-computable; examples of recursive function and basic properties; recursive sets and relations (The notion of Turing machine is defined in the examples classes.)
Coding of finite sequences and applications: coding with prim numbers, Cantor function,
Gödel beta-function; simultaneous definitions by primitive recursion; contraction; course-of-values recursion.
Indices: coding of RAM-machine; Kleene normal form theorem, index of function; parameter theorem, recursion theorem, fixed point theorem, Rice theorem.
Church's thesis: non-recursive function; halting problem; undecidability of first order logic.

Arithmetical hierarchy: arithmetical relations, contraction of quantifiers, alternating prefix, definition of classes; arithmetical enumeration theorem and arithmetical hierarchy theorem.
Recursively enumerable sets: RE-parameter theorem; selector theorem; graph theorem; Post theorem; sketch of proof of unsolvability of Hilbert tenth problem.
Godel incompleteness theorems: Peano arithmetic; representability of functions and relations; coding of syntax; Tarski theorem; diagonal lemma; the first incompleteness theorem; consistency and omega-consistency; provability predicate; Hilbert-Bernays-Lob derivability conditions; the second incompleteness theorem.

1. Recursion Theory, J. R. Shoenfiled, Springer Verlag, 1993.
2. Gödel's Incompleteness Theorems, R. Smullyan, Oxford University Press, 1992.
3. Introduction to Mathematical Logic, E. Mendelson, D. Van Nostrand Company, 1997.
4. Classical Recursion Theory, P. Odifreddi, North-Holland, 1987.
5. Introduction to the Theory of Computation, M. Sipser, PWS Publishing Company, 1996.

Enrollment :
Attended : Mathematical logic

Examination :
Passed : Mathematical logic

Računarstvo - Regular study - Mathematics Education

Računarstvo - Regular study - Mathematics Education