Основы теории вычислимых функций

<<- Назад к вопросам

Два главных универсальных множества для класса перечислимых подмножеств N:

(Отметьте один правильный вариант ответа.)

Варианты ответа

совпадают

вычислимо изоморфны(Верный ответ)

вычислимо не изоморфны

Похожие вопросы

Декартово произведение перечислимых множеств А и В перечислимо:

Объединение перечислимых множеств А и В всегда перечислимо:

Среди перечислимых множеств множество, к которому m-сводится любое перечислимое множество X:

Если U -двухместная главная универсальная функция для класса вычислимых функций одного аргумента, то для всех p, q, x:

Для любого перечислимого множества X из декартового квадрата N существует вычислимая $f\colon N \to N$ :

Два пересекающихся перечислимых множества, не отделимые разрешимым множеством:

Непересекающиеся множества X и Y отделяются множеством Z, если:

Множество X - $\alpha$ -перечислимо тогда и только тогда, когда для некоторого перечислимого множества E:

Если U - главная вычислимая универсальная функция для класса вычислимых одноместных функций, то существует для произвольной вычислимой одноместной функции h:

Функция U(n,m), $n,m \in N$ - универсальна для класса вычислимых функций одного аргумента, если для каждого n: