Босс В. Лекции по математике. Том 6: От Диофанта до Тьюринга

Босс В. Лекции по математике. Т. 6: От Диофанта до Тьюринга. - М., 2006. - 208 с.
Книга посвящена основаниям математики, проблемам вычислимости и доказуемости. Машины Тьюринга, рекурсивные функции, логика, теория моделей, неразрешимость и неаксиоматизируемость арифметики, десятая проблема Гильберта — вот рассматриваемый круг вопросов. Изложение отличается краткостью и прозрачностью. Значительное внимание уделяется мотивации результатов и прикладным аспектам. Классическая проблематика в значительной мере переосмыслена и представлена в удобном для восприятия виде.
Для студентов, преподавателей, инженеров и научных работников.
Оглавление
Предисловие к «Лекциям»....................................................7
Предисловие к шестому тому................................................9
Глава 1. Алгоритмы и вычислимость...................10
1.1. Универсальные вычисления....................................10
1.2. Что такое алгоритм................................................11
1.3. Вычислимость......................................................12
1.4. Примеры и комментарии........................................16
1.5. Проблема неопределенности ..................................18
1.6. Перечислимые множества...................20
1.7. Эффективные процедуры....................23
1.8. Машины Тьюринга........................23
1.9. О «внутренней кухне»......................26
1.10. Рекурсивные функции......................29
1.11. Диофантовы множества.....................32
1.12. Комментарии и дополнения..................36
Глава 2. Неполнота арифметики......................40
2.1. Теоремы Гёделя..........................40
2.2. Неформализуемость истины..................43
2.3. Непротиворечивость.......................44
2.4. Неразрешимые уравнения...................45
2.5. Об арифметических истинах..................47
2.6. Можно ли помочь арифметике извне?...........48
2.7. Доказательство второй теоремы Гёделя..........49
2.8. Лингвистические парадоксы..................51
Глава 3. Универсальные функции и нумерации ............53
3.1. Универсальные функции....................53
3.2. Универсальные множества...................57
3.3. Изоморфизм гёделевских нумераций............57
3.4. Теорема о неподвижной точке ................58
3.5. Теорема Райса...........................59
3.6. Нумерации и гёделизация...................61
Глава 4. Доказуемость............................64
4.1. Конфликт с определением истины.............64
4.2. HSI-проблема Тарского.....................67
4.3. Нормальные алгоритмы Маркова..............71
4.4. Системы Поста...........................73
4.5. Проблема эквивалентности слов...............76
4.6. Таг-проблемы............................79
4.7. Формальные грамматики....................80
4.8. Теория и практика ........................81
Глава 5. Математическая логика.....................85
5.1. В чем состоит миссия......................85
5.2. Переменные, связки и функции...............86
5.3. Булева алгебра...........................89
5.4. Формулы, высказывания, предикаты............92
5.5. Синтаксис и семантика.....................96
5.6. Исчисление высказываний...................99
5.7. Языки первого уровня......................100
5.8. Интерпретации и модели....................102
5.9. Язык арифметики.........................106
5.10. Арифметичность вычислимых функций..........108
5.11. Запрещенные средства......................112
5.12. Комментарии............................113
Глава 6. Диофантов язык и десятая проблема Гильберта......115
6.1. Диофантовы множества и функции.............115
6.2. Неразрешимые проблемы ...................117
6.3. Универсальный многочлен...................121
6.4. Технические результаты.....................123
6.5. Дополнения.............................133
Глава 7. Конструктивная математика ..................134
7.1. Конструктивные числа .....................134
7.2. Последовательность Шпеккера................136
7.3. Конфликт с аксиомой выбора.................138
7.4. Актуальная бесконечность...................139
7.5. Инструмент или реальность..................142
Глава 8. Аксиоматические теории.....................145
8.1. Арифметика Пеано........................145
8.2. Парадокс категоричности....................148
8.3. Аксиоматика Цермело—Френкеля..............150
8.4. Неевклидова геометрия.....................153
8.5. Гипотеза континуума.......................160
Глава 9. Теория моделей...........................161
9.1. Логический аспект........................161
9.2. Что стоит за результатами Генцена .............163
9.3. Парадокс Сколема........................164
9.4. Модели булевых структур....................166
9.5. Как модель разрушает схему..................167
9.6. Абстрактные и конкретные модели.............169
9.7. В чем состоит общая идея...................171
9.8. Конечные базисы.........................172
Глава 10. Степени неразрешимости....................175
10.1. Сводимость.............................175
10.2. Продуктивность и креативность...............177
10.3. Иммунные множества......................178
10.4. Вычисления с оракулом.....................179
10.5. Тьюринговы степени.......................180
10.6. Иерархия степеней........................182
Глава 11. Сводка определений и результатов..............183
11.1. Алгоритмы и вычислимость..................183
11.2. Неполнота арифметики.....................185
11.3. Универсальные функции и нумерации...........186
11.4. Доказуемость............................187
11.5. Математическая логика.....................189
11.6. Диофантов язык и десятая проблема Гильберта.....194
11.7. Конструктивная математика..................195
11.8. Аксиоматические теории....................195
11.9. Теория моделей ..........................196
11.10. Степени неразрешимости....................197
Сокращения и обозначения .........................198
Литература....................................200
Предметный указатель............................202

Created using FlowPaper Flipbook Maker ↗