Computability and Mathematical Logic

Lecturer:

Jan Mareš (gar.)

Tutor:

Jan Mareš (gar.)

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:

Time-table for winter semester 2011/2012:

Time-table is not available yet

Time-table for summer semester 2011/2012:

Time-table is not available yet

The course is a part of the following study plans: