### Repository

Repository is empty

### Computability

 Code: 92912 ECTS: 5.0 Lecturers in charge: doc. dr. sc. Vedran Čačić - Lectures English level: 1,0,0 All teaching activities will be held in Croatian. However, foreign students in mixed groups will have the opportunity to attend additional office hours with the lecturer and teaching assistants in English to help master the course materials. Additionally, the lecturer will refer foreign students to the corresponding literature in English, as well as give them the possibility of taking the associated exams in English.

### 1. komponenta

Lecture typeTotal
Lectures 45
Description:
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.
Literature:
1. J. R. Shoenfiled: Recursion Theory
2. R. Smullyan: Gödel's Incompleteness Theorems
3. E. Mendelson: Introduction to Mathematical Logic
4. P. Odifreddi: Classical Recursion Theory
5. M. Sipser: Introduction to the Theory of Computation
Prerequisit for:
Enrollment :
Passed : Mathematical logic
 1. semester Izborni predmet 1, 2 - Regular study - Theoretical Mathematics 2. semester Izborni predmet 1, 2 - Regular study - Theoretical Mathematics 3. semester Izborni predmet 3, 4 - Regular study - Theoretical Mathematics 4. semester Izborni predmet 3, 4 - Regular study - Theoretical Mathematics
Consultations schedule: