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

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

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

(Ответ считается верным, если отмечены все правильные варианты ответов.)

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

X - проекция Y(Верный ответ)

X совпадает с N

$\exists Y \subset NxN$ - разрешимое(Верный ответ)

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

Свойство A(x), $x \in N$ перечислимо тогда и только тогда, когда:

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

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

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

Перечислимое множество m-полно тогда и только тогда, когда его дополнение:

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

Частичная функция вычислима относительно всюду определенной функции тогда и только тогда, когда она:

Функция перечислима тогда и только тогда, когда

Если $X \le_m Y$ и Y - перечислимо, то:

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

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

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

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