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

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

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

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

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

не существует

существует(Верный ответ)

несравнимы

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

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

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

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

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

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

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

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

Умножение чисел x, y $((x,y) \to x*y)$ реализует рекурсия:

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

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

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