Главная / Алгоритмы и дискретные структуры /
Основы теории вычислимых функций / Тест 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) вычислима относительно
 
 
(2) вычислима относительно
 
 
(3) вычислима относительно
 
Номер 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)