Computability and Mathematical Logic

Course guarantor:

Lecturer:

Tutor:

Supervisor:

Department of Mathematics

Synopsis:

Algorithms and algorithmically computable functions, algorithmically definable sets and their mathematical definitions. Recursion theory. Classical propositional and predicate logic. Application of the recursion theory to the logic.

Requirements:

Syllabus of lectures:

Algorithms and algorithmically computable functions, Markov?s normal algorithms, Turing machines, recursive functions, recursive and recursively enumerable sets and predicates, s-m-n theorem, productive and creative sets, algorithmically unsolvable problems. Propositions, tautologies, axioms, theorems, correctness, completeness and decidability of propositional calculus. Relational structures, language of predicate calculus, terms, formulae, axioms, theorems, satisfactions, truth, tautologies, correctness, model, Gödel completeness theorem, undecidability of predicate calculus, resolution method.

Syllabus of tutorials:

Study Objective:

To acquaint the students with classical results of the recursion theory as a mathematical definition of intuitive notion of the algorithm and with used finite and constructive methods. Principal results of the classical logic.

Study materials:

Povinná

N. Cutland: Computability. An Introduction to Recursive Functions Theory. Cambridge

University Press, Cambridge, 1980. (Selected chapters.)

A. Grzegorczyk: An Outline of Mathematical Logic. Polish Scientific Publishers,

Varšava 1974. (Selected chapters.)

Doporučená

Z. Manna: Mathematical Theory of Computation. Mc.Graw-Hill,Inc. 1974.

H.R. Lewis, C.H.Papadimitriou: Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey, 1981.

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans: