Курсы
Лекторы
Школьникам
О проекте
Войти
Главная
/
Курсы
/
Введение в математическую логику и теорию алгоритмов
/
Лекция 15. Теория алгоритмов
Понятие алгоритма
x 1.00
Математика
Введение в математическую логику и теорию алгоритмов
Лекция 15. Теория алгоритмов
Шехтман
Валентин Борисович
Предыдущая лекция
00:09
Понятие алгоритма
06:17
Формализации этого понятия
08:33
Понятие вычислимости
13:43
Тезис Чёрча-Тьюринга
17:03
Разрешимость
27:39
Полуразрешимость
33:02
Теорема 15.3 Поста
39:06
Перечислимость
59:03
Теорема 15.6 (в лекциях - 15.7) Пусть h-вычислимая тотальная функция. Тогда 1)если А - разрешимо, то h^(-1)(А) разрешимо 2)если А - перечислимо, то h[A] и h^(-1)(А) перечислимы
1:03:53
Теорема 15.7 Об универсальной вычислимой функции
1:10:48
Теорема 15.8 Существует перечислимое неразрешимое множество подмножество в N
1:17:26
О разрешимости теорий первого порядка
1:28:56
Теорема 15.12 Гёделя об определимости
1:30:32
Теорема 15.13 Гёделя о неполноте
Курсы
Лекторы
Школьникам
О проекте
Контакты
Свяжитесь с нами
Отправить
2025 МГУ имени М.В. Ломоносова
Условия использования сайта
Сведения об образовательной организации
Нашли ошибку?
