Шановне товариство, в 2024 році СМС проходить надзвичайно потужно, чому є свідченням такий факт: ми запрошуємо вас уже на 15-те засідання сезону!

Тема: "Складність Колмогорова та неповнота Геделя"
Доповідач: Артем Гак (@ArtemGak), МП КН-2 у КМА

Час: Вт, 16.04 о 17:30.
Місце: ауд 219 Інституту математики.
Зум: https://zoom.us/j/5197673308?pwd=eGRtaVIzbHlNT3RoRjc5U2FsVENGUT09
519 767 3308
213122

Коли ми говоримо про складність задачі, то зазвичай запитуємо, скільки ресурсів потрібно, щоб її вирішити. Наприклад, скільки кроків алгоритму потрібно, аби знайти шлях між парою вершин у графі.

Якщо у нас є два рядки символів "0101010101" та "0111010011", то інтуїтивно зрозуміло, що перший рядок "простіший": він періодичний і його можна стиснути. Чисельно можна визначити так: K(x) = довжина найменшої програми, що виводить рядок x.

У доповіді ми розглянемо поняття складності Колмогорова та скористаємось ним, щоб довести два важливі результати математики 20 ст.: проблему зупинки Черча-Тьюрінга та неповноту Геделя.