Невычислимость, неразрешимость, недоказуемость [1] // Алексей Сосинский

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

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

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

https://forany.xyz/a-425

Видео Невычислимость, неразрешимость, недоказуемость [1] // Алексей Сосинский канала ∀ x, y, z channel