Плиско В.Е. - Введение в математическую логику - 4. Неразрешимые алгоритмические проблемы

00:00:14 Вступление. Нумерация кортежей. Нумерация команд. Нумерация программ и функций 00:16:08 Пример невычислимой функции. Лямбда-обозначения. Теорема о параметризации 00:26:52 Нумерация перечислимых множеств. Универсальная функция. Существование универсальной вычислимой функции 00:37:40 Частичная вычислимая функция, не имеющая тотального вычислимого продолжения. Существование неразрешимого перечислимого множества. Неразрешимость проблемы остановки 00:46:58 О десятой проблеме Гильберта. Теорема Успенского — Райса 00:57:17 Теорема Успенского — Райса для множеств. Вполне разрешимые и вполне перечислимые множества. Теорема Райса — Шапиро 01:06:12 Применения теоремы Райса — Шапиро. Теорема Райса — Шапиро для перечислимых множеств 01:15:56 Многозадачная сводимость. Свойства m-сводимости. Роль множества K Ссылка на плейлист: #математическаялогика