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

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

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

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

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

$zsy \to zys$

$xsz \to pzy$

$zsx \to pzy$ (Верный ответ)

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

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

Перейти

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

Перейти

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

Перейти

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

Перейти

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

Перейти

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

Перейти

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

Перейти

Отношение " $x\mod y=0, x, y \in N$ " является:

Перейти

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

Перейти

Отношение " $x>y, x, y \in N$ " является:

Перейти