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

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

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

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

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

всюду определенная вычислимая $f(n)\colon n \in X \Leftrightarrow f(n) \in Y$ (Верный ответ)

вычислимая функция y=f(x), где x, y - натуральные:

$n \in Y \Leftrightarrow f(n) \in X$

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

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

Множество $X \subset N$ перечислимо тогда и только тогда, когда:

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

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

При любом n любое множество из класса $\Pi_n$ :

При любом n любое множество из класса $\Sigma_n$ :

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

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

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

Множество m-сводится к , если существует:

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