Учебное пособие. — М.: КомКнига, 2006. — 208 с. — ISBN
5-484-00463-2.
Книга посвящена основаниям математики, проблемам вычислимости и
доказуемости. Машины Тьюринга, рекурсивные функции, логика, теория
моделей, неразрешимость и неаксиоматизируемость арифметики, десятая
проблема Гильберта - вот рассматриваемый круг вопросов. Изложение
отличается краткостью и прозрачностью. Значительное внимание
уделяется мотивации результатов и прикладным аспектам. Классическая
проблематика в значительной мере переосмыслена и представлена в
удобном для восприятия виде. Теоремы Геделя, например, доказываются
в несколько строчек.
Алгоритмы и вычислимость
Универсальные вычисления
Что такое алгоритм
Вычислимость
Примеры и комментарии
Проблема неопределенности
Перечислимые множества
Эффективные процедуры
Машины Тьюринга
О "внутренней кухне"
Рекурсивные функции
Диофантовы множества
Комментарии и дополнения
Неполнота арифметики
Теоремы Гёделя
Неформализуемость истины
Непротиворечивость
Неразрешимые уравнения
Об арифметических истинах
Можно ли помочь арифметике извне?
Доказательство второй теоремы Гёделя
Лингвистические парадоксы
Универсальные функции и нумерации
Универсальные функции
Универсальные множества
Изоморфизм гёделевских нумераций
Теорема о неподвижной точке
Теорема Райса
Нумерации и гёделизация
Доказуемость
Конфликт с определением истины
HSI-проблема Тарского
Нормальные алгоритмы Маркова
Системы Поста
Проблема эквивалентности слов
Таг-проблемы
Формальные грамматики
Теория и практика
Математическая логика
В чем состоит миссия
Переменные, связки и функции
Булева алгебра
Формулы, высказывания, предикаты
Синтаксис и семантика
Исчисление высказываний
Языки первого уровня
Интерпретации и модели
Язык арифметики
Арифметичность вычислимых функций
Запрещенные средства
Комментарии
Диофантов язык и десятая проблема Гильберта
Диофантовы множества и функции
Неразрешимые проблемы
Универсальный многочлен
Технические результаты
Дополнения
Конструктивная математика
Конструктивные числа
Последовательность Шпеккера
Конфликт с аксиомой выбора
Актуальная бесконечность
Инструмент или реальность
Аксиоматические теории
Арифметика Пеано
Парадокс категоричности
Аксиоматика Цермело-Френкеля
Неевклидова геометрия
Гипотеза континуума
Теория моделей
Логический аспект
Что стоит за результатами Генцена
Парадокс Сколема
Модели булевых структур
Как модель разрушает схему
Абстрактные и конкретные модели
В чем состоит общая идея
Конечные базисы
Степени неразрешимости
Сводимость
Продуктивность и креативность
Иммунные множества
Вычисления с оракулом
Тьюринговы степени
Иерархия степеней
Сводка определений и результатов
Алгоритмы и вычислимость
Неполнота арифметики
Универсальные функции и нумерации
Доказуемость
Математическая логика
Диофантов язык и десятая проблема Гильберта
Конструктивная математика
Аксиоматические теории
Теория моделей
Степени неразрешимости
Универсальные вычисления
Что такое алгоритм
Вычислимость
Примеры и комментарии
Проблема неопределенности
Перечислимые множества
Эффективные процедуры
Машины Тьюринга
О "внутренней кухне"
Рекурсивные функции
Диофантовы множества
Комментарии и дополнения
Неполнота арифметики
Теоремы Гёделя
Неформализуемость истины
Непротиворечивость
Неразрешимые уравнения
Об арифметических истинах
Можно ли помочь арифметике извне?
Доказательство второй теоремы Гёделя
Лингвистические парадоксы
Универсальные функции и нумерации
Универсальные функции
Универсальные множества
Изоморфизм гёделевских нумераций
Теорема о неподвижной точке
Теорема Райса
Нумерации и гёделизация
Доказуемость
Конфликт с определением истины
HSI-проблема Тарского
Нормальные алгоритмы Маркова
Системы Поста
Проблема эквивалентности слов
Таг-проблемы
Формальные грамматики
Теория и практика
Математическая логика
В чем состоит миссия
Переменные, связки и функции
Булева алгебра
Формулы, высказывания, предикаты
Синтаксис и семантика
Исчисление высказываний
Языки первого уровня
Интерпретации и модели
Язык арифметики
Арифметичность вычислимых функций
Запрещенные средства
Комментарии
Диофантов язык и десятая проблема Гильберта
Диофантовы множества и функции
Неразрешимые проблемы
Универсальный многочлен
Технические результаты
Дополнения
Конструктивная математика
Конструктивные числа
Последовательность Шпеккера
Конфликт с аксиомой выбора
Актуальная бесконечность
Инструмент или реальность
Аксиоматические теории
Арифметика Пеано
Парадокс категоричности
Аксиоматика Цермело-Френкеля
Неевклидова геометрия
Гипотеза континуума
Теория моделей
Логический аспект
Что стоит за результатами Генцена
Парадокс Сколема
Модели булевых структур
Как модель разрушает схему
Абстрактные и конкретные модели
В чем состоит общая идея
Конечные базисы
Степени неразрешимости
Сводимость
Продуктивность и креативность
Иммунные множества
Вычисления с оракулом
Тьюринговы степени
Иерархия степеней
Сводка определений и результатов
Алгоритмы и вычислимость
Неполнота арифметики
Универсальные функции и нумерации
Доказуемость
Математическая логика
Диофантов язык и десятая проблема Гильберта
Конструктивная математика
Аксиоматические теории
Теория моделей
Степени неразрешимости