x, y, z

Невычислимость, неразрешимость, недоказуемость (Тюринг → Колмогоров → Чейтин → Гёдель)

Алексей Сосинский

Комментарии: 0
Лекция 1

Лекция 2

Лекция 3

Лекция 4

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

100110111010010010101100101101010011100010010010010010000111110110010100001111100

«сложней», чем последовательность

10101010101010101010101010101010101010101010101010101010101010101010101010101010,

т. е. определим «Колмогоровскую сложность» и изучим ряд ее «нехороших» свойств, именно, не вычислимость некоторых связанных с ней характеристик. Эти свойства сыграют решающую роль в доказательстве теоремы Гёделя о неполноте – одного из самых значительных научных открытий ХХ-го века.

А если останется время (боюсь, что вряд ли это произойдет), я расскажу как сложность связана с энтропией и энергией в статистической физике.

Программа курса:
1. Вычислимые и не вычислимые функции.
2. Разрешимые и неразрешимые множества. Примеры алгоритмически неразремимых проблем.
3. Колмогоровская сложность.
4. Первая теорема Гёделя о неполноте и ее прикладной смысл. Доказательство теоремы Гёделя методом Чейтина (через Колмогоровскую сложность).

Курс будет трудным, но никаких предварительных специальных знаний не требуется – он будет доступен школьникам.

Сосинский Алексей Брониславович, кандидат физико-математических наук.

Летняя школа «Современная математика», г. Дубна.
20–28 июля 2014 г.
Комментарии: 0