РЕШАЕМ МАТЕМАТИКУ ВМЕСТЕ!
 
СТУДЕНТАМ:    Учебники     Решебники    Шпаргалки    Контрольные работы   Видео уроки

ШКОЛЬНИКАМ:  ГДЗ - 1 класс  2 класс  3 класс  4 класс  5 класс  6 класс  7 класс  8 класс  9 класс  10 класс  11 класс


Главная » Файлы » Учебные материалы » Математическая логика и теория алгоритмов
Босс В. Лекции по математике. Т. 6: От Диофанта до Тьюринга.

12.12.2011, 00:38
Книга посвящена основаниям математики, проблемам вычислимости и доказуемости. Машины Тьюринга, рекурсивные функции, логика, теория моделей, неразрешимость и неаксиоматизируемость арифметики, десятая проблема Гильберта — вот рассматриваемый круг вопросов. Изложение отличается краткостью и прозрачностью. Значительное внимание уделяется мотивации результатов и прикладным аспектам. Классическая проблематика в значительной мере переосмыслена и представлена в удобном для восприятия виде.
Для студентов, преподавателей, инженеров и научных работников.

ОГЛАВЛЕНИЕ

Предисловие к «Лекциям»...................................................................... 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





Размер файла: (2.06Mb)

Категория: Математическая логика и теория алгоритмов | Добавил: nikka
Просмотров: 1200 | Загрузок: 236 | Рейтинг: 5.0/1


Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]



ВЫБОР ПО КАТЕГОРИЯМ:

Аналитическая геометрия и алгебра [0]
Высшая алгебра [52]
История математики [55]
Математика для технарей [21]
Математика для экономистов, юристов и т.д.. [5]
Математическая логика и теория алгоритмов [40]
Теория вероятностей и мат. статистика [28]
Теория чисел [33]
Учебники по математике [46]



При полном или частичном использовании материалов
активная ссылка на портал VMATE.RU обязательна


Высшая математика онлайн - всё бесплатно, наш портал создан специально для студентов кому интересна высшая математика. У нас на портале возможно скачать бесплатно учебники по высшей математике, книги по математике или сделать заказ учебных пособий, скачать контрольные по высшей математике, заказать, задачники по высшей математики и решебники. Оставить запрос по предмету - аналитическая геометрия или задать вопрос - справочная по математике Заказать решение и т.д. Высшая математика онлайн - математический портал и здесь собраны шпаргалки по высшей математике и видео уроки. миэмп Добро пожаловать! Вход