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

Эта лекция является дополнительным семинаром для первого курса, вводящим молодых физтехов в волшебный мир неразрешимых задач. Мы поговорим о проблеме разрешимости для исчисления пропозиций и для исчисления предикатов, о трудах Гёделя, о машинах Тьюринга, о лямбда-исчислении, о простых неразрешимых задачах и о быстро растущих функциях. А также о том зачем это всё. Следующая лекция: Лектор: Константин Владимиров Дата лекции: 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 Теорема Райса 1:34:00 Быстро растущие и частично рекурсивные функции 1:41:50 Игра в бобра 1:49:17 Возвращаясь к программе Гильберта 1:52:20 Заключение Errata: * 1:18:38 -- рациональное это отношение двух целых. Единички в двоичном расширении могут и не заканчиваться, например для числа 1/3.