Основы вычислимости и теории сложности, лекция 1

Вычислимые функции, разрешимые множества, определения перечислимого множества. Теорема Поста. Перечислимые множества как проекции разрешимых. Вычислимость функции и перечислимость ее графика. Универсальная функция. Вычислимая функция, которую нельзя доопределить до всюду определенной. Пример перечислимого, но неразрешимого множества.Страница лекции на сайте Курс: Основы вычислимости и теории сложности Лектор: Дмитрий Ицыксон Канал: Computer Science Center ID 13