Вычислимость и логика. Лекция 1

Вычислимые функции, разрешимые и перечислимые множества

Вычислимые функции, разрешимые множества, определения перечислимого множества. Теорема Поста. Перечислимые множества как проекции разрешимых. Вычислимость функции и перечислимость ее графика. Универсальная функция. Вычислимая функция, которую нельзя доопределить до всюду определенной. Пример перечислимого, но неразрешимого множества.

Страница лекции на сайте Computer Science Center