Лекция 4. Неразрешимые алгоритмические проблемы

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