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

Среда, 14 сентября 2011, 18:30–19:50
ПОМИ РАН

Описание

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