Главная / Алгоритмы и дискретные структуры / Основы теории вычислимых функций / Тест 7

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

Упражнение 1:

Номер 1

Если , то:

Ответ:

(1) Y сводимо к X по Тьюрингу

(2) X сводимо к Y по Тьюрингу

(3) Y сводимо к T по модулю Y

Номер 2

Если , то:

Ответ:

(1)

(2)

(3)

Номер 3

Если , то:

Ответ:

(1)

(2)

(3)

Упражнение 2:

Номер 1

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

Ответ:

(1) вычислима относительно math

(2) вычислима относительно math

(3) вычислима относительно math

Номер 2

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

Ответ:

(1) f вычислима относительно графика g

(2) g вычислима относительно графика f

(3) fg вычислима относительно графиков f и g

Номер 3

Образец - это функция из N в N, определенная:

Ответ:

(1) на всем N

(2) на конечном подмножестве N

(3) не для всех множеств из N

Упражнение 3:

Номер 1

Два образца - совместны, если:

Ответ:

(1) объединение их графиков - график функции

(2) пересечение их графиков - график функции

(3) их графики имеют хотя бы одну точку пересечения

Номер 2

Множество X - корректно, если:

Ответ:

(1) в X нет противоречащих троек

(2) в X нет противоположных троек

(3) все тройки принадлежат X

Номер 3

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

Ответ:

(1) реляционной

(2) релятивизацией

(3) реальной

Упражнение 4:

Номер 1

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

Ответ:

(1) область определения f

(2) область изменения f

(3) пар (x, f(x))

Номер 2

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

Ответ:

(1)

(2)

(3)

Номер 3

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

Ответ:

(1) не существует

(2) существует

(3) универсальна

Упражнение 5:

Номер 1

Множество -  0' - разрешимо, если оно:

Ответ:

(1) сводимо к m - полному перечисленному множеству

(2) совпадает с m - перечислимым множеством

(3) не сводимо к m - полному перечисленному множеству

Номер 2

Самая трудная в мире задача разрешения:

Ответ:

(1) существует в единственном числе

(2) не существует

(3) существует в конечном числе

Номер 3

Любые два множества:

Ответ:

(1) несравнимы

(2) сравнимы

(3) сравнимы по модулю

Упражнение 6:

Номер 1

Множества X и Y, для которых  и :

Ответ:

(1) существует

(2) не существует

(3) несравнимы

Номер 2

"Оракул" для множества X отвечает на вопрос:

Ответ:

(1) принадлежат ли числа X множеству Y

(2) конечно ли множество X

(3) бесконечно ли множество X

Номер 3

 "Оракул" для множества X может быть реализован вызовом внешней:

Ответ:

(1) функции

(2) процедуры

(3) записи

Упражнение 7:

Номер 1

Фрагмент - это всегда:

Ответ:

(1) функция

(2) множество

(3) отношение

Номер 2

Множество X согласовано с фрагментом x, если:

Ответ:

(1) дополнение X продолжает x

(2) характеристическая функция X продолжает x

(3) x принадлежит X

Номер 3

Несравнимые по Тьюрингу перечислимые множества:

Ответ:

(1) не существуют

(2) существуют

(3) не пересекаются

Упражнение 8:

Номер 1

Элемент - это:

Ответ:

(1) пара множеств

(2) пара любых конечных множеств

(3) пара конечных множеств натуральных чисел

Номер 2

Элемент  продолжает элемент , если:

Ответ:

(1)

(2)

(3)

Номер 3

Указание - это кортеж  , в котором:

Ответ:

(1)

(2)

(3)

Главная / Алгоритмы и дискретные структуры / Основы теории вычислимых функций / Тест 7