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

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

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

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

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

Y сводимо к T по модулю Y

X сводимо к Y по Тьюрингу

Y сводимо к X по Тьюрингу(Верный ответ)

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

Множества X и Y, для которых $X\neg \le_T Y$ и $Y\neg \le_T X$ :

Перейти

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

Перейти

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

Перейти

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

Перейти

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

Перейти

Элемент $\langle C,D \rangle$ продолжает элемент $\langle A,B\rangle$ , если:

Перейти

Классы $\Sigma_n$ и $\Pi_n$ :

Перейти

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

Перейти

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

Перейти

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

Перейти