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

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

Если $T = \{(x,y)\colon x \in s(X),y \in s(Y), x \to y \}$ , то это множество:

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

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

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

универсально

не перечислимо

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

Если $T = \{(x,y)\colon x \in s(X),y \in s(Y), x \to y \}$ , то:

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

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

Инструкции "находясь в состоянии $s \in S$ и читая символ $x \in X$ перейти в состояние для всех $z \in X,p \in S$ , напечатать символ $y \in X$ и сдвинуться влево" соответствует:

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

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

Универсальное $\Pi_n$ множество:

Универсальное $\Sigma_n$ множество:

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

Если $X \le_m Y$ и $Y \le_m Z$ , то:

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

Если , то это множество:

Если $T = \{(x,y)\colon x \in s(X),y \in s(Y), x \to y \}$ , то это множество: