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

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

Нумерация - вычислимая, если:

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

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

$X \subset N \times N$ является счетным

перечислимое $X \subset N \times N$ задает нумерацию(Верный ответ)

X=N

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

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

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

Если d - вычислимая функция, E(d)={0,1} и не имеет всюду определенного вычислимого продолжения, то:

Вычислимая функция, не имеющая всюду определенного вычислимого продолжения:

Всякая функция, вычислимая программой с конечным числом переменных:

Любая функция, вычислимая на машине Тьюринга не более чем за примитивно рекурсивное время:

Если нумерация является вычислимой, то последовательность $i \mapsto f_i$

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

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