Книга посвящена основаниям математики, проблемам вычислимости и доказуемости. Машины Тьюринга, рекурсивные функции, логика, теория моделей, неразрешимость и неаксиоматизируемость арифметики, десятая проблема Гильберта - вот рассматриваемый круг вопросов. Изложение отличается краткостью и прозрачностью. Значительное внимание уделяется мотивации результатов и прикладным аспектам. Классическая проблематика в значительной мере переосмыслена и представлена в удобном для восприятия виде. Теоремы Гёделя, например, доказываются в несколько строчек.
Содержание
1Алгоритмы и вычислимость
1.1. Универсальные вычисления
1.2. Что такое алгоритм
1.3. Вычислимость
1.4. Примеры и комментарии
1.5. Проблема неопределенности
1.6. Перечислимые множества
1.7. Эффективные процедуры
1.8. Машины Тьюринга
1.9. О "внутренней кухне"
1.10. Рекурсивные функции
1.11. Диофантовы множества
1.12. Комментарии и дополнения
2Неполнота арифметики
2.1. Теоремы Гёделя
2.2. Неформализуемость истины
2.3. Непротиворечивость
2.4. Неразрешимые уравнения
2.5. Об арифметических истинах
2.6. Можно ли помочь арифметике извне?
2.7. Доказательство второй теоремы Гёделя
2.8. Лингвистические парадоксы
3Универсальные функции и нумерации
3.1. Универсальные функции
3.2. Универсальные множества
3.3. Изоморфизм гёделевских нумераций
3.4. Теорема о неподвижной точке
3.5. Теорема Райса
3.6. Нумерации и гёделизация
4Доказуемость
4.1. Конфликт с определением истины
4.2. HSI-проблема Тарского
4.3. Нормальные алгоритмы Маркова
4.4. Системы Поста
4.5. Проблема эквивалентности слов
4.6. Таг-проблемы
4.7. Формальные грамматики
4.8. Теория и практика
5Математическая логика
5.1. В чем состоит миссия
5.2. Переменные, связки и функции
5.3. Булева алгебра
5.4. Формулы, высказывания, предикаты
5.5. Синтаксис и семантика
5.6. Исчисление высказываний
5.7. Языки первого уровня
5.8. Интерпретации и модели
5.9. Язык арифметики
5.10. Арифметичность вычислимых функций
5.11. Запрещенные средства
5.12. Комментарии
6Диофантов язык и десятая проблема Гильберта
6.1. Диофантовы множества и функции
6.2. Неразрешимые проблемы
6.3. Универсальный многочлен
6.4. Технические результаты
6.5. Дополнения
7Конструктивная математика
7.1. Конструктивные числа
7.2. Последовательность Шпеккера
7.3. Конфликт с аксиомой выбора
7.4. Актуальная бесконечность
7.5. Инструмент или реальность
8Аксиоматические теории
8.1. Арифметика Пеано
8.2. Парадокс категоричности
8.3. Аксиоматика Цермело - Френкеля
8.4. Неевклидова геометрия
8.5. Гипотеза континуума
9Теория моделей
9.1. Логический аспект
9.2. Что стоит за результатами Генцена
9.3. Парадокс Сколема
9.4. Модели булевых структур
9.5. Как модель разрушает схему
9.6. Абстрактные и конкретные модели
9.7. В чем состоит общая идея
9.8. Конечные базисы
10Степени неразрешимости
10.1. Сводимость
10.2. Продуктивность и креативность
10.3. Иммунные множества
10.4. Вычисления с оракулом
10.5. Тьюринговы степени
10.6. Иерархия степеней
Предисловие
Фундамент нужен не потому, что в подвале жить хорошо.
Диапазон "от Диофанта до Тьюринга" подразумевается смысловой. Короче, речь идет о дискретной математике в той ее части, которая касается "оснований". Вычислимость, доказуемость, теоремы Гёделя, неразрешимые проблемы, - вот круг вопросов, определяющих русло изложения.
Что касается мотивации, то в обычном понимании ее нет, поскольку основания математики то и дело натыкаются на непреодолимые преграды, оставаясь, как говорится, при своих. Но чего, собственно, ожидать на краю? На грани, где возможное переходит в невозможное, жизнь - в смерть, теорема - в парадокс. По сути - ожидать нечего. Однако, как и в поиске смысла жизни, основную роль здесь играют побочные эффекты.