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

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

Для доказательства неразрешимости множества X достаточно доказать, что:

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

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

некоторое перечислимое множество - разрешимо

N перечислимо вместе с X

любое перечислимое множество - разрешимо(Верный ответ)

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

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

Непересекающиеся множества X и Y отделяются множеством Z, если:

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

Если X - класс вычислимых одноместных функции, Y из X, Z - перечислимое неразрешимое множество, U - главная функция, то существует всюду определенная функция f со свойством:

Образ множества X для частичной функции f(n) - это:

Прообраз множества X для частичной функции f(n) - это:

Если U - главная универсальная функция, а X - множество натуральных чисел n, где U_n - нигде не определена, то U_n:

Если U -двухместная главная универсальная функция для класса вычислимых функций одного аргумента, то для всех p, q, x:

Для универсального перечислимого множества W-перечислимо множество: