Load:
|
1. komponenta
Lecture type | Total |
Lectures |
45 |
* Load is given in academic hour (1 academic hour = 45 minutes)
|
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:
|
-
Recursion Theory, J. R. Shoenfiled, Springer Verlag, 1993.
-
Gödel's Incompleteness Theorems, R. Smullyan, Oxford University Press, 1992.
-
Introduction to Mathematical Logic, E. Mendelson, D. Van Nostrand Company, 1997.
-
Classical Recursion Theory, P. Odifreddi, North-Holland, 1987.
-
Introduction to the Theory of Computation, M. Sipser, PWS Publishing Company, 1996.
|
Prerequisit for:
|
Enrollment
:
Attended
:
Mathematical logic
Examination
:
Passed
:
Mathematical logic
|