ГЛАВА 1. ОСНОВНЫЕ ПОНЯТИЯ . . 7
§1.1. Разрешимость диофантовых уравнений как массовая проблема 7
§ 1.2. Системы диофантовых уравнений 9
§ 1.3. Решения в натуральных числах 10
§ 1.4. Диофантовы множества 12
§ 1.5. Логическая терминология 14
§ 1.6. Простейшие примеры диофантовых множеств, свойств, отно-
отношений и функций 17
Упражнения 18
Комментарии 21
ГЛАВА 2. ДИОФАНТОВОСТЬ ВОЗВЕДЕНИЯ В СТЕПЕНЬ • • 22
§2.1. Специальные рекуррентные последовательности второго
порядка 22
§ 2.2. Диофантовость специальных рекуррентных последователь-
последовательностей (основные идеи) . 24
§ 2.3. Диофантовость специальных рекуррентных последователь-
последовательностей (доказательство) 27
§ 2.4. Диофантовость возведения в степень 31
§ 2.5. Экспоненциально диофантовы уравнения 32
Упражнения 34
Комментарии 36
ГЛАВА 3. ДИОФАНТОВО КОДИРОВАНИЕ 39
§3.1. Канторова нумерация 39
§ 3.2. Гёделево кодирование 40
§ 3.3. Позиционное кодирование 41
§ 3.4. Диофантовость биномиальных коэффициентов,' факториала и
простых чисел 43
§ 3.5. Сравнение кортежей 44
§ 3.6. Расширение функций на кортежи 46
Упражнения 48
Комментарии 49
ГЛАВА 4. УНИВЕРСАЛЬНЫЕ ДИОФАНТОВЫ УРАВНЕНИЯ 52
§ 4.1. Основные определения .52
§ 4.2. Кодировка уравнений . 54
§ 4.3. Кодировка потенциальных решений 56
§ 4.4. Вычисление значений полиномов 57
§ 4.5. Универсальные диофантовы уравнения 59
§ 4.6. Диофантовы множества с недиофантовыми дополнениями ... 60
Упражнения 61
Комментарии 63
ГЛАВА 5. АЛГОРИТМИЧЕСКАЯ НЕРАЗРЕШИМОСТЬ 10-Й ПРОБЛЕМЫ
ГИЛЬБЕРТА 65
§5.1. Машина Тьюринга 65
§ 5.2. Композиция машин 67
§ 5.3. Базисные машины : 69
§ 5.4. Распознавание диофантовых множеств машинами Тьюринга . . 76
§ 5.5. Диофантово моделирование машин Тьюринга 77
§ 5.6. Неразрешимость 10-й проблемы Гильберта на машинах
Тьюринга 83
§ 5.7. Тезис Черча 85
Упражнения 89
Комментарии 90
ГЛАВА 6. ОГРАНИЧЕННЫЕ КВАНТОРЫ ОБЩНОСТИ 94
§6.1. Первая конструкция: машины Тьюринга 94
§ 6.2. Вторая конструкция: геделево кодирование 95
§ 6.3. Третья конструкция: суммирование 99
§ 6.4. Связи между 8-й и 10-й проблемами Гильберта 106
§ 6. 5. Еще одно универсальное уравнение 111
§ 6.6. Ещё одно диофантово множество с недиофантовым до-
дополнением 113
Упражнения 114
Комментарии 115
ГЛАВА 7. МАССОВЫЕ ПРОБЛЕМЫ ТЕОРИИ ЧИСЕЛ 117
§ 7.1. Количество решений у диофантовых уравнений 117
§ 7.2. Неэффективизируемые оценки в теории экспоненциально
диофантовых уравнений 119
§ 7.3. Аналог 10-й проблемы Гильберта для гауссовых чисел . . 126
§ 7.4. Однородные уравнения и рациональные решения 133
Упражнения 136
Комментарии 137
ГЛАВА 8. ДИОФАНТОВА СЛОЖНОСТЬ ' 139
§ 8.1. Основные понятия 139
§ 8.2. Оценка количества неизвестных в экспоненциально дио-
фантовых представлениях 142
Упражнения 146
Комментарии 147
ГЛАВА 9. МАССОВЫЕ ПРОБЛЕМЫ МАТЕМАТИЧЕСКОГО АНАЛИЗА .... 150
§ 9.1. Диофантово вещественные числа 150
§ 9.2. Уравнения. неравенства и тождества с вещественными
переменными 153
§ 9.3. Системы обыкновенных дифференциальных уравнений ... 158
§ 9.4. Интегрируемость 160
Упражнения 162
Комментарии 162
ГЛАВА 10. ДРУГИЕ ПРИЛОЖЕНИЯ ДИОФАНТОВЫХ ПРЕДСТАВЛЕНИЙ. . . 164
§ 10.1. Диофантовы игры 164
§ 10.2. Обобщенные кони на многомерной шахматной доске ... 167
Упражнения 176
Комментарии 177
ПРИЛОЖЕНИЯ 180
1. Теорема о четырёх квадратах 180
2. Китайская теорема об остатках 181
3. Теорема Куммера 182
4. Суммирование обобщённой геометрической прогрессии .... 182
УКАЗАНИЯ К УПРАЖНЕНИЯМ 184
СПИСОК ЛИТЕРАТУРЫ 194
УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ 214
ПЕРЕДМЕТНЫЙ УКАЗАТЕЛЬ 216
ИМЕННОЙ УКАЗАТЕЛЬ 218
