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

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

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

Перечислимое множество m-полно тогда и только тогда, когда его дополнение:

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

Варианты ответа
эффективно неперечислимо(Верный ответ)
совпадает с ним
эффективно перечислимо
Похожие вопросы
Множество X - \alpha-перечислимо тогда и только тогда, когда для некоторого перечислимого множества E:
Множество X из N перечислимо тогда и только тогда, когда:
Частичная функция f вычислима относительно всюду определенной функции g тогда и только тогда, когда она:
Свойство A(x), x \in N перечислимо тогда и только тогда, когда:
Множество X \subset N перечислимо тогда и только тогда, когда:
Частичная функция вычислима относительно всюду определенной функции тогда и только тогда, когда она:
Функция перечислима тогда и только тогда, когда
Если X - класс вычислимых одноместных функции, Y из X, Z - перечислимое неразрешимое множество, U - главная функция, то существует всюду определенная функция f со свойством:
Если X - класс вычислимых одноместных функции, Y из X, Z - перечислимое неразрешимое множество, U - главная функция, то существует всюду определенная функция f со свойством:
Среди перечислимых множеств множество, к которому m-сводится любое перечислимое множество X: