Невычислимость, неразрешимость, недоказуемость.

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

1001101110100100101011001011010100111000100100100100101011001010100.
"Сложней", чем последовательность.
10101010101010101010101010101010101010101010101010101010101010101010101010101010, .
т. е. определим "Колмогоровскую Сложность" и изучим ряд ее "нехороших" свойств, именно, не вычислимость некоторых связанных с ней характеристик. Эти свойства сыграют решающую роль в доказательстве теоремы Гёделя о неполноте - одного из самых значительных научных открытий ХХ- го века.
А если останется время (боюсь, что вряд ли это произойдет), я расскажу как сложность связана с энтропией и энергией в статистической физике.
Программа курса:
1. вычислимые и не вычислимые функции.
2. разрешимые и неразрешимые множества. Примеры неразремимых проблем алгоритмически.
3. колмогоровская сложность.
4. первая теорема Гёделя о неполноте и ее прикладной смысл. Доказательство теоремы Гёделя методом чейтина (через колмогоровскую сложность.
Курс будет трудным, но никаких предварительных специальных знаний не требуется - он будет доступен школьникам.
Сосинский Алексей Брониславович, кандидат физико-математических наук. Летняя школа "Современная Математика", г. Дубна. 20-28 Июля 2014 г.