Успенский В.А. Лекции о вычислимых функциях

М.: Государственное издательство физико-математической литературы, 1960. — 492 с.Понятия алгоритма и вычислимой функции являются одними из центральных понятий современной математики. Их роль в математике середины XX в. можно, пожалуй, сравнить с ролью понятия множества в математике конца XIX в. Настоящие «Лекции» посвящены изложению основ теории вычислимых функций (проводимому на базе принятого в настоящее время отождествления их — для случая" функций с натуральными аргументами и значениями — с частично-рекурсивными функциями), а также некоторым приложениям этой теории. (Из авторского предисловия).Предварительные сведения из теории множеств и функций
Предварительные сведения из математической логики
Примитивно-рекурсивные функции, множества, предикаты
Рекурсивно-перечислимые множества и предикаты
Частично-рекурсивные функции
Обще-рекурсивные функции, множества, предикаты
Функция, универсальная для примитивно-рекурсивных функций
Функция, универсальная для частично-рекурсивных функций, и множество, универсальное для рекурсивно-перечислимых множеств
Дополнительные сведения о рекурсивно-перечислимых множествах
Нумерация и операции
Приложения теории вычислимых функций к математическому анализу: выделение вычислимых действительных чисел
Приложения теории вычислимых функций к логике: конструктизация отрицательных определений
Приложение теории вычислимых функций к вычислительной математике: возможности абстрактных вычислительных машин