База ответов ИНТУИТ

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

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

Арифметическое множество m-сводимо к множеству всех истинных арифметических формул без параметров:

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

Варианты ответа
всегда(Верный ответ)
только для \Pi_n
только для \Sigma_n
Похожие вопросы
Множество всех истинных арифметических формул без параметров:
Множество всех истинных арифметических формул без параметров:
Множество А является I-соответствующей множеству В, если:
Множество всех показателей n, для которых существует целое решение уравнения xn+yn=zn всегда:
Если X - класс вычислимых одноместных функции, Y из X, Z - перечислимое неразрешимое множество, U - главная функция, то существует всюду определенная функция f со свойством:
Если X - класс вычислимых одноместных функции, Y из X, Z - перечислимое неразрешимое множество, U - главная функция, то существует всюду определенная функция f со свойством:
Если U - главная универсальная функция, а X - множество натуральных чисел n, где Un - нигде не определена, то Un:
Среди перечислимых множеств множество, к которому m-сводится любое перечислимое множество X:
Если U -двухместная главная универсальная функция для класса вычислимых функций одного аргумента, то для всех p, q, x:
Множество X - эффективно неперечислимо, если существует всюду определенная вычислимая W-универсальная функция f: