x 1.00
Скачать видео

Лекция 15. Теория алгоритмов

  1. 00:09Понятие алгоритма
  2. 06:17Формализации этого понятия
  3. 08:33Понятие вычислимости
  4. 13:43Тезис Чёрча-Тьюринга
  5. 17:03Разрешимость
  6. 27:39Полуразрешимость
  7. 33:02Теорема 15.3 Поста
  8. 39:06Перечислимость
  9. 59:03Теорема 15.6 (в лекциях - 15.7) Пусть h-вычислимая тотальная функция. Тогда 1)если А - разрешимо, то h^(-1)(А) разрешимо 2)если А - перечислимо, то h[A] и h^(-1)(А) перечислимы
  10. 01:03:53Теорема 15.7 Об универсальной вычислимой функции
  11. 01:10:48Теорема 15.8 Существует перечислимое неразрешимое множество подмножество в N
  12. 01:17:26О разрешимости теорий первого порядка
  13. 01:28:56Теорема 15.12 Гёделя об определимости
  14. 01:30:32Теорема 15.13 Гёделя о неполноте