Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Части 1,2,3

М.: МЦНМО, 1999-2000.
Книга написана по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ.
Начала теории множеств.
Множества и мощности.
Упорядоченные множества.
Языки и исчисления.
Логика высказываний.
Исчисление высказываний.
Языки первого порядка.
Исчисление предикатов.
Теории и модели.
Вычислимые функции.
Вычислимость, разрешимость и перечислимость.
Универсальные функции и неразрешимость.
Нумерации и операции.
Свойства главных нумераций.
Теорема о неподвижной точке.
m-сводимость и свойства перечислимых множеств.
Вычисления с оракулом.
Арифметическая иерархия.
Машины Тьюринга.
Арифметичность вычислимых функций.
Рекурсивные функции.