Шехтман В. Б. - Введение в математическую логику и теорию алгоритмов - Теория алгоритмов

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