Вычислимость и неразрешимые задачи

Эта лекция является дополнительным семинаром для первого курса, вводящим молодых физтехов в волшебный мир неразрешимых задач. Мы поговорим о проблеме разрешимости для исчисления пропозиций и для исчисления предикатов, о трудах Гёделя, о машинах Тьюринга, о лямбда-исчислении, о простых неразрешимых задачах и о быстро растущих функциях. А также о том зачем это всё. Следующая лекция: Лектор: Константин Владимиров Дата лекции: 10 мая 2021 года Съёмка и звук: Дмитрий Рябцев Слайды к лекциям автора по логике и вычислимости: Timeline: 00:00 Введение. Исчисление пропозиций 11:20 Аксиомы и правила вывода 18:58 Проверять или доказывать? 27:10 Программа Гильберта и теоремы Гёделя 35:30 Машины Тьюринга 46:40 Универсальная машина Тьюринга и проблема останова 53:50 Лямбда-исчисление 1:13:00 Тезис Черча-Тьюринга 1:17:30 Простые неразрешимые задачи 1:29:45 Теорема