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

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

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

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

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

$B \subset A, D \subset B$

$A \subset B \subset C$

$A \subset C, B \subset D$ (Верный ответ)

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

Указание - это кортеж $\langle A^+,A^-,B^+,B^- \rangle$ , в котором:

Перейти

Инструкции "находясь в состоянии $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$ , если существует:

Перейти

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

Перейти

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

Перейти

Для $\alpha$ - всюду определенной функции, $\alpha$ -вычислимая функция двух аргументов являющаяся универсальной:

Перейти

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

Перейти

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

Перейти

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

Перейти