База ответов ИНТУИТ

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

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

Если  X \le_m Y и X - эффективно неперечислимо, то:

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

Варианты ответа
X \cup Y и X\Y - эффективно неперечислимы
X \cap Y и X\Y - эффективно неперечислимы
Y - эффективно неперечислима(Верный ответ)
Похожие вопросы
Если X \le_m Y и Y - разрешимо, то:
Если X \le_m Y и Y - перечислимо, то:
Если X \le_m Y и Y \le_m Z, то:
Множество X - эффективно неперечислимо, если существует всюду определенная вычислимая W-универсальная функция f:
Если Y \le_m X, то:
Если Y \le_m X, то:
Если  X \le_m Y,Y \in \Sigma_n, то:
Если X \le_m Y,Y \in \Pi_n, то:
Если Y - класс вычислимых одноместных функций, а X \subset Y, то множество \{n\colon U_n \in X\}:
Множество X \subset N m-сводится к Y \subset N, если существует: