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

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

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

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

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

вычислима относительно $\{\langle n, g(n)\rangle\colon n \in N\}$ (Верный ответ)

вычислима относительно $\{\langle f(n), g(n)\rangle\colon n \in N\}$

вычислима относительно $\{\langle n, f(n)\rangle\colon n \in N\}$

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

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

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

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

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

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

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

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

Множество X - эффективно неперечислимо, если существует всюду определенная вычислимая W-универсальная функция f:

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