URSS.ru Магазин научной книги
Обложка Босс В. Лекции по математике. Том 6: Алгоритмы, логика, вычислимость. От Диофанта до Тьюринга и Гёделя Обложка Босс В. Лекции по математике. Том 6: Алгоритмы, логика, вычислимость. От Диофанта до Тьюринга и Гёделя
Id: 340566
899

Лекции по математике.
Том 6: Алгоритмы, логика, вычислимость. От Диофанта до Тьюринга и Гёделя. Т.6. Изд. 4, стереотип.

2026. 208 с.
Белая офсетная бумага

Аннотация

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


Оглавление
top
Предисловие к «Лекциям»6
Предисловие к шестому тому8
Глава 1. Алгоритмы и вычислимость9
1.1. Универсальные вычисления9
1.2. Что такое алгоритм10
1.3. Вычислимость12
1.4. Примеры и комментарии15
1.5. Проблема неопределенности17
1.6. Перечислимые множества19
1.7. Эффективные процедуры22
1.8. Машины Тьюринга22
1.9. О «внутренней кухне»26
1.10. Рекурсивные функции29
1.11. Диофантовы множества31
1.12. Комментарии и дополнения36
Глава 2. Неполнота арифметики39
2.1. Теоремы Гёделя39
2.2. Неформализуемость истины42
2.3. Непротиворечивость43
2.4. Неразрешимые уравнения44
2.5. Об арифметических истинах46
2.6. Можно ли помочь арифметике извне?48
2.7. Доказательство второй теоремы Гёделя49
2.8. Лингвистические парадоксы51
Глава 3. Универсальные функции и нумерации53
3.1. Универсальные функции53
3.2. Универсальные множества57
3.3. Изоморфизм гёделевских нумераций58
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. Арифметичность вычислимых функций109
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. Неевклидова геометрия154
8.5. Гипотеза континуума160
Глава 9. Теория моделей162
9.1. Логический аспект162
9.2. Что стоит за результатами Генцена164
9.3. Парадокс Сколема165
9.4. Модели булевых структур167
9.5. Как модель разрушает схему168
9.6. Абстрактные и конкретные модели170
9.7. В чем состоит общая идея172
9.8. Конечные базисы173
Глава 10. Степени неразрешимости176
10.1. Сводимость176
10.2. Продуктивность и креативность178
10.3. Иммунные множества179
10.4. Вычисления с оракулом180
10.5. Тьюринговы степени182
10.6. Иерархия степеней183
Глава 11. Сводка определений и результатов184
11.1. Алгоритмы и вычислимость184
11.2. Неполнота арифметики186
11.3. Универсальные функции и нумерации187
11.4. Доказуемость188
11.5. Математическая логика190
11.6. Диофантов язык и десятая проблема Гильберта195
11.7. Конструктивная математика196
11.8. Аксиоматические теории196
11.9. Теория моделей197
11.10. Степени неразрешимости198
Сокращения и обозначения200
Литература202
Предметный указатель204

Предисловие к "Лекциям"
top
Отвлекаясь по дороге в баню на поездку в Сочи, забываешь куда идешь.

Для нормального изучения любого математического предмета необходимы, по крайней мере, 4 ингредиента:

1) живой учитель;

2) обыкновенный подробный учебник;

3) рядовой задачник;

4) учебник, освобожденный от рутины, но дающий общую картину, мотивы, связи, "что зачем".

До четвертого пункта у системы образования руки не доходили. Конечно, подобная задача иногда ставилась и решалась, но в большинстве случаев – при параллельном исполнении функций обыкновенного учебника. Акценты из-за перегрузки менялись, и намерения со второй-третьей главы начинали дрейфовать, не достигая результата. В виртуальном пространстве так бывает. Аналог объединения гантели с теннисной ракеткой перестает решать обе задачи, хотя это не сразу бросается в глаза.

"Лекции" ставят 4-й пункт своей главной целью. Сопутствующая идея – экономия слов и средств. Правда, на фоне деклараций о краткости и ясности изложения предполагаемое издание около 20 томов может показаться тяжеловесным, но это связано с обширностью математики, а не с перегрузкой деталями.

Необходимо сказать, на кого рассчитано. Ответ "на всех" выглядит наивно, но он в какой-то мере отражает суть дела. Обозримый вид, обнаженные конструкции доказательств, – такого сорта книги удобно иметь под рукой. Не секрет, что специалисты самой высокой категории тратят массу сил и времени на освоение математических секторов, лежащих за рамками собственной специализации. Здесь же ко многим проблемам предлагается короткая дорога, позволяющая быстро освоить новые области и освежить старые. Для начинающих "короткие дороги" тем более полезны, поскольку облегчают движение любыми другими путями.

В вопросе "на кого рассчитано", – есть и другой аспект. На сильных или слабых? На средний вуз или физтех? Опять-таки выходит "на всех". Звучит странно, но речь не идет о регламентации кругозора. Простым языком, коротко и прозрачно описывается предмет. Из этого каждый извлечет свое и двинется дальше.

Наконец, последнее. В условиях информационного наводнения инструменты вчерашнего дня перестают работать. Не потому, что изучаемые дисциплины чересчур разрослись, а потому, что новых секторов жизни стало слишком много. И в этих условиях мало кто готов уделять много времени чему-то одному. Поэтому учить всему – надо как-то иначе. "Лекции" дают пример. Плохой ли, хороший – покажет время. Но в любом случае, это продукт нового поколения. Те же "колеса", тот же "руль", та же математическая суть, – но по-другому.


Предисловие к шестому тому
top
Фундамент нужен не потому, что в подвале жить хорошо.

Диапазон "от Диофанта до Тьюринга" подразумевается смысловой. Короче, речь идет о дискретной математике в той ее части, которая касается "оснований". Вычислимость, доказуемость, теоремы Гёделя, неразрешимые проблемы, – вот круг вопросов, определяющих русло изложения.

Что касается мотивации, то в обычном понимании ее нет, поскольку основания математики то и дело натыкаются на непреодолимые преграды, оставаясь, как говорится, при своих. Но чего, собственно, ожидать на краю? На грани, где возможное переходит в невозможное, жизнь – в смерть, теорема – в парадокс. По сути – ожидать нечего. Однако, как и в поиске смысла жизни, основную роль здесь играют побочные эффекты.


О загадке бестселлеров В.Босса
top

Книгу В.Босса "Интуиция и математика" я перечитал три раза! Потом еще раз, чтобы разобраться, в чем дело, но скрытых пружин так и не нашел. Конечно, великолепный подбор миниатюр, точный язык, мягкий юмор, располагающая интонация, – но все это вместе взятое не объясняет результат даже наполовину. Сын моего приятеля – парню 14 лет – выучил "Интуицию" почти наизусть. Измучил родителей вопросами, прочел гору дополнительной литературы. Понятно – особый случай, но показательный! В целом ситуация, безусловно, мягче. Однако отзывы все положительные, а процент восторженных – удивителен и необъясним.

"Лекции по математике" того же автора – другое дело. Кое-кто из моих коллег принял их в штыки, поскольку система образования, естественно, противится нововведениям. Лишняя головная боль для преподавателя. Тем не менее, в результате итогового обсуждения – первые два тома "Лекций" пришли к нам на отзыв – В.Босс получил высший бал.

Лично мне "Лекции" нравятся даже больше, чем "Интуиция". Ясное и продуманное изложение предмета. Лаконичное до неправдоподобия, но без ущерба для содержания. Вот что по этому поводу пишет сам автор: "Первая часть книги – сжатый курс матанализа. Чушь более сотни страниц, но "все есть". Некоторые детали, конечно, опускаются, но это не потери, а приобретения. Сбросив десяток лишних килограмм, человек выглядит лучше, живет интереснее. Так и здесь. Многие подробности мешают видеть суть. И освобождение от балласта, как ни странно, позволяет обсуждать принципиальные вопросы, на которые в толстых учебниках не хватает места".

Первый опыт показывает, что студенты – и сильные, и слабые – благосклонно принимают "Лекции". В этом еще одна удивительная, хотя и понятная особенность изложения. Короткий и ясный взгляд на предмет, обсуждение мотивов, общая картина, – нужны всем.

Наконец, я бы не писал в газету, если бы речь шла просто о хороших и даже очень хороших книгах. "Лекции" В.Босса, на мой взгляд, явление неординарное. Дело в том, что информационная лавина сейчас многое меняет. В результате, сложившаяся система образования подходит к критической точке. Конечно, как в доме накапливаются ненужные вещи, так и в образовании со временем укореняется масса атавизмов. Но хуже другое. То, без чего вроде бы нельзя обойтись, перестает помещаться в рамки. Поэтому необходимы новые подходы и принципы. "Лекции" обеспечивают прорыв в этом направлении.

Профессор МФТИ А.П.Афанасьев

Из интервью с В.Боссом
top
dop

Нельзя ли в двух словах о главной особенности "Лекций"?

– Диалектика обучения – во взаимодействии сторон. Понимание – умение. Суть – детали. "Лекции" добиваются понимания.

Как?

– Правдами и неправдами (улыбается). Очень важно, например, поместить проблему "целиком в кадр". Чтобы видно было "сразу все".

Объяснениями на пальцах?

– Когда как, только "коротко и ясно". Упрощения, недомолвки. Но главное – обнажение сути.

А что посоветуете, если завтра экзамен, а в голове пусто?

– Таблетку димедрола.


В условиях информационного наводнения инструменты вчерашнего дня перестают работать. Поэтому учить надо как-то иначе. "Лекции" дают пример. Плохой ли, хороший – покажет время. Но в любом случае, это продукт нового поколения. Те же "колеса", тот же "руль", та же математическая суть, – но по-другому.

В.Босс

Чтобы усвоить предмет, надо освободить его от деталей, обнажить центральные конструкции, понять, как до теорем можно было додуматься. Это тяжелая работа, на которую не всегда хватает сил и времени. В "Лекциях" такая работа проделывается автором.

Популярность книг В. Босса среди преподавателей легко объяснима. Дается то, чего недостает. Общая картина, мотивация, взаимосвязи. И самое главное – легкость вхождения в любую тему.

Содержание продумано и хорошо увязано. Громоздкие доказательства ужаты до нескольких строчек. Виртуозное владение языком. Что касается замысла изложить всю математику в 20 томах, с трудом верится, что это по силам одному человеку.

Лекции В. Босса – замечательные математические книги. Как учебные пособия, они не всегда отвечают канонам преподавания, но студентам это почему-то нравится.


Об авторе
top
photoБосс В.
Российский ученый, просветитель и популяризатор науки, заведующий сектором Института проблем управления Российской академии наук (ИПУ РАН); доктор физико-математических наук, профессор кафедры проблем управления Московского физико-технического института (МФТИ). Создатель и автор крупного Интернет-проекта «Школа Опойцева».

Практически вся его научная деятельность связана с работой в Институте проблем управления, где в качестве ведущего специалиста в области управления социальными и экономическими системами, статики и динамики сложных систем, он принимал участие во многих научно-прикладных программах и разработках. Руководил прикладными исследованиями для Госплана и Министерства связи СССР, а также крупной научно-исследовательской работой по расчету и оптимизации структуры бортовых вычислительных систем.

Талантливый лектор, Валерий Иванович всегда был увлечен просветительской деятельностью, часто разъезжал по стране, буквально — от Балтики до Камчатки, в качестве активного члена Общества «Знание» — «академии миллионов».

За время работы в Австралии (1998–2001) опубликовал множество статей по математике на английском языке и читал лекции для профессоров в Квинслендском университете.

Последние годы Валерий Иванович посвятил проекту «Школа Опойцева» — это книги, видеолекции и учебные материалы по математике и физике для высшего и школьного образования.

Он был убежден, что: «В условиях информационного наводнения инструменты вчерашнего дня перестают работать. Поэтому учить надо как-то иначе. „Лекции“ дают пример. Плохой ли, хороший — покажет время. Но в любом случае это продукт нового поколения. Те же „колеса“, тот же „руль“, та же математическая суть — но по-другому».