# COMPUTABILITY THEORY

# COMPUTABILITY THEORY

Basic notions of mathematics and logic.

Introduction to the mathematical theory of computation, and its

applications.

Models of Computability. Decidable sets and computably enumerable sets. Undecidable sets. The Recursion Theorem. Relative computability. Turing degrees. Proof techniques (forcing, priority) in computability theory. The arithmetical hierarchy, and definability in arithmetic. Undecidable problems in mathematics. Applications of computability theory. Introduction to complexity.

Models of Computability. Partial recursive functions. Turing machines. Decidable sets and computably enumerable sets. The Recursion Theorem and applications. Undecidable sets and problems. Simple sets. Creative sets. Relative computability and oracle Turing machines. Turing reducibility. The priority method and solution to Post's Problem. Existence of minimal pairs in the computably enumerable Turing degrees. Minimal Turing degrees. The Arithmetical Hierarchy and the Kleene-Post Theorem. Definability in arithmetic and application to logic. The lattice of computably enumerable sets. Undecidable problems in mathematics: The word problem for finitely presented semigroups; the Post Correspondence Problem; the word problem for finitely presented groups. The Matiyasevich-Robinson-Davis-Putnam Theorem. Introduction to randomness. Introduction to Computable MOdel Theory. Introduction to Reverse Mathematics. Introduction to complexity. Polynomial-Time computability.

1) R. Weber, Computability Theory, Student Mathematical Library, Vol.

62, American Mathematical Society, Rhode Island, 2012

2) H.B. Enderton, Computability Theory. An Introduction to Recursion Theory.

Elsevier, Amsterdam, 2011

3) Lecture notes distributed by the teacher

Lectures

Final exam

None.