Матиясевич Ю.В. Десятая проблема Гильберта

М.: Физматлит, 1993. — 223 с. — (Математическая логика и основания математики 26). — ISBN 5-02-014326-X.Дается полное доказательство алгоритмической неразрешимости 10-й проблемы Гильберта, касающейся диофантовых уравнений, вместе с необходимыми сведениями из теории алгоритмов и теории чисел, а также приложения развитой для этого техники к другим массовым проблемам теории чисел, алгебры, анализа, теоретического программирования.
Для математиков, в том числе аспирантов и студентов старших курсов.ПредисловиеОсновные понятия
Разрешимость диофантовых уравнений как массовая проблема
Системы диофантовых уравнений
Решения в натуральных числах
Диофантовы множества
Логическая терминология
Простейшие примеры диофантовых множеств, свойств, отношений и функций
Упражнения
КомментарииДиофантовость возведения в степень
Специальные рекуррентные последовательности второго порядка
Диофантовость специальных рекуррентных последовательностей (основные идеи)
Диофантовость специальных рекуррентных последовательностей (доказательство)
Диофантовость возведения в степень
Экспоненциально диофантовы уравнения
Упражнения
КомментарииДиофантово кодирование
Канторова нумерация
Гёделево кодирование
Позиционное кодирование
Диофантовость биномиальных коэффициентов, факториала и простых чисел
Сравнение кортежей
Расширение функций на кортежи
Упражнения
КомментарииУниверсальные диофантовы уравнения
Основные определения
Кодировка уравнений
Кодировка потенциальных решений
Вычисление значений полиномов
Универсальные диофантовы уравнения
Диофантовы множества с недиофантовыми дополнениями
Упражнения
КомментарииАлгоритмическая неразрешимость 10-й проблемы Гильберта
Машина Тьюринга
Композиция машин
Базисные машины
Распознавание диофантовых множеств машинами Тьюринга
Диофантово моделирование машин Тьюринга
Неразрешимость 10-й проблемы Гильберта на машинах Тьюринга
Тезис Черча
Упражнения
КомментарииОграниченные кванторы общности
Первая конструкция: машины Тьюринга
Вторая конструкция: геделево кодирование
Третья конструкция: суммирование
Связи между 8-й и 10-й проблемами Гильберта
Еще одно универсальное уравнение
Ещё одно диофантово множество с недиофантовым дополнением
Упражнения
КомментарииМассовые проблемы теории чисел
Количество решений у диофантовых уравнений
Неэффективизируемые оценки в теории экспоненциально диофантовых уравнений
Аналог 10-й проблемы Гильберта для гауссовых чисел
Однородные уравнения и рациональные решения
Упражнения
КомментарииДиофантова сложность
Основные понятия
Оценка количества неизвестных в экспоненциально диофантовых представлениях
Упражнения
КомментарииМассовые проблемы математического анализа
Диофантово вещественные числа
Уравнения. неравенства и тождества с вещественными переменными
Системы обыкновенных дифференциальных уравнений
Интегрируемость
Упражнения
КомментарииДругие приложения диофантовых представлений
Диофантовы игры
Обобщенные кони на многомерной шахматной доске
Упражнения
КомментарииПриложения
Теорема о четырёх квадратах
Китайская теорема об остатках
Теорема Куммера
Суммирование обобщённой геометрической прогрессииУказания к упражнениям
Список литературы
Указатель обозначений
Предметный указатель
Именной указатель