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.
|
Pristupačnost
