Алексей Брониславович Сосинский
Невычислимость, неразрешимость, недоказуемость
(Тюринг → Колмогоров → Чейтин → Гёдель)
А. Б. Сосинский планирует провести 4 занятия.
Курс занятий посвящен тому, что в математики сделать нельзя. Но речь пойдет не о запрещенных действиях (типа деления на ноль или квадратуры круга), а об отсутствии общих методов для решения некоторых широких классов задач. Начиная от определения вычислимой функции (через машину Тюринга), мы узнаем про существование универсальной вычислимой функции, и как следствие — о существовании не вычислимых функций. Отсюда мы поймем, какие задачи никакой компьютер (даже сколь угодно мощный) решить не может в принципе. Затем мы выясним, в каком смысле последовательность 1001101110100100101011001011010100111000100100
10010010000111110110010100001111100 "сложней", чем последовательность 10101010101010101010101010101010101010101
010101010101010101010101010101010101010, т.е. определим "Колмогоровскую сложность" и изучим ряд ее «нехороших» свойств, именно, не вычислимость некоторых связанных с ней характеристик. Эти свойства сыграют решающую роль в доказательстве теоремы Гёделя о неполноте — одного из самых значительных научных открытий ХХ-го века.
А если останется время (боюсь, что вряд ли это произойдет), я расскажу как сложность связана с энтропией и энергией в статистической физике.
Программа курса
- 1. Вычислимые и не вычислимые функции.
- 2. Разрешимые и неразрешимые множества. Примеры алгоритмически неразрешимых проблем.
- 3. Колмогоровская сложность.
- 4. Первая теорема Гёделя о неполноте и ее прикладной смысл. Доказательство теоремы Гёделя методом Чейтина (через Колмогоровскую сложность).
Курс будет трудным, но никаких предварительных специальных знаний не требуется — он будет доступен школьникам.
E-mail оргкомитета:
dubna@mccme.ru