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

Если B(x,y) - некоторое разрешимое свойство, то свойства вида $A(x) \Leftrightarrow \forall y : B(x,y)$ определяют свойства:

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

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

дополнения которых перечислимы

отрицания которых не перечислимы

отрицания которых перечислимы(Верный ответ)

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

Свойство A принадлежит классу $\Sigma_n$ , если для некоторого разрешимого свойства В:

Свойство A принадлежит классу $\Pi_n$ , если для некоторого разрешимого свойства В:

Если Y - класс вычислимых одноместных функций, а $X \subset Y$ , то множество $\{n\colon U_n \in X\}$ :

Множество $X \subset N$ m-сводится к $Y \subset N$ , если существует:

Функция m=f(n), $m,n \in N$ вычислима, если существует алгоритм A(f):

Если X=[0;3], Y=[3;0], то $f\colon X\to Y$ будет:

Если X=[-2;5], Y=[0;2], то $f\colon X \to Y$ будет:

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