COURSE AIMS AND OBJECTIVES: The main aim of the course is to introduce a few formal definiton of the notion of algorithm (RAMmachine, 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.
RAMmachine: definition and examples; RAMcomputable functions; macromachine.
Partial recursive function: primitive recursive functions, Ackerman function, definition of the class of partial recursive functions, the proof that each partial recursive function is RAMcomputable; 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 betafunction; simultaneous definitions by primitive recursion; contraction; courseofvalues recursion.
Indices: coding of RAMmachine; Kleene normal form theorem, index of function; parameter theorem, recursion theorem, fixed point theorem, Rice theorem.
Church's thesis: nonrecursive 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: REparameter 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 omegaconsistency; provability predicate; HilbertBernaysLob derivability conditions; the second incompleteness theorem.
