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

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

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

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

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

$\langle x, n \rangle \in X \Leftrightarrow \langle s(n), x \rangle \in N \times N$

$\langle n, x \rangle \in X \Leftrightarrow \langle s(n), x \rangle \in Y, Y \subset N \times N$ (Верный ответ)

$\langle n, x \rangle \in X \Leftrightarrow \langle s(n), x \rangle \in N \times N$

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

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

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

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

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

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

Для любого n в классе $\Sigma_n$ :

Функции, получаемые с помощью операций подстановки и рекурсии из константы 0, операции прибавления единицы k штук k-местных функций $(x_1,x_2, \ldots ,x_n) \to x_i$ называют:

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

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

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

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