Главная / Алгоритмы и дискретные структуры /
Основы теории вычислимых функций / Тест 6
Основы теории вычислимых функций - тест 6
Упражнение 1:
Номер 1
Для доказательства неразрешимости множества X
достаточно доказать, что:
Ответ:
 (1) любое перечислимое множество - разрешимо 
 (2) некоторое перечислимое множество - разрешимо 
 (3) N
перечислимо вместе с X
 
Номер 2
Множество m
-сводится к , если существует:
Ответ:
 (1) вычислимая функция y=f(x)
, где x
, y
- натуральные: 
 
(2)  
 
(3) всюду определенная вычислимая
 
Номер 3
Для m
-сводящей X
к Y
функции f
используют обозначение:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Упражнение 2:
Номер 1
Если и Y
- разрешимо, то:
Ответ:
 (1) X
- разрешимо 
 (2) Y
- m
-разрешимо 
 (3) X
- не разрешимо 
Номер 2
Если и Y
- перечислимо, то:
Ответ:
 (1) X
- перечислимо 
 (2) Y
- m
-разрешимо 
 (3) X
- не перечислимо 
Номер 3
Если и , то:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Упражнение 3:
Номер 1
m
-сводящей X
к X
будет функция:
Ответ:
 (1) тождественная 
 (2) единичная (для любого аргумента равна 1
) 
 (3) характеристическая 
Номер 2
Если f
сводит Х
к Y
, g - Y
к Z
, то:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 3
Если f
сводит Х
к Y
, то она сводит:
Ответ:
 (1) N\X
к N\Y
 
 
(2) к
 
 
(3) к
 
Упражнение 4:
Номер 1
Неверно для произвольных множеств:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 2
Неверно для произвольных множеств:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 3
Неверно для произвольных множеств:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Упражнение 5:
Номер 1
Среди перечислимых множеств множество, к которому m
-сводится любое перечислимое множество X
:
Ответ:
 (1) существует всегда 
 (2) существует не всегда 
 (3) не существует всегда 
Номер 2
m
-полное множество относительно m
-сводимости - это множество:
Ответ:
 (1) наибольшее 
 (2) наименьшее 
 (3) дополнение 
Номер 3
m
-полнота - это отношение:
Ответ:
 (1) транзитивное 
 (2) не транзитивное 
 (3) нерефлексивное 
Упражнение 6:
Номер 1
Если универсальное множество - главное, то его:
Ответ:
 (1) диагональ - m
-полна 
 (2) дополнение и пересечение с N
- тоже 
 (3) дополнение и объединение с N
- тоже 
Номер 2
Множество всех самоприменимых программ:
Ответ:
 (1) m
-полно 
 (2) не m
-полно 
 (3) пусто 
Номер 3
Множество всех программ, останавливающихся хотя бы на одном входе является:
Ответ:
 (1) m
-полным 
 (2) не m
-полным 
 (3) универсальным 
Упражнение 7:
Номер 1
Множество X
- эффективно бесконечное, если алгоритм конструирования по любому n
различных элементов из X
:
Ответ:
 (1) существует 
 (2) не существует 
 (3) существует только для простых n
 
Номер 2
Множество X
- эффективно неперечислимо, если существует всюду определенная вычислимая W
-универсальная функция f
:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 3
Если и X
- эффективно неперечислимо, то:
Ответ:
 
(1) и
X\Y
- эффективно неперечислимы 
 
(2) и
X\Y
- эффективно неперечислимы 
 (3) Y
- эффективно неперечислима 
Упражнение 8:
Номер 1
Для универсального перечислимого множества W
-перечислимо множество:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 2
Множества с эффективно неперечислимыми дополнениями:
Ответ:
 (1) существуют 
 (2) не существуют 
 (3) не существуют только для простых дополнений 
Номер 3
Перечислимое множество m
-полно тогда и только тогда, когда его дополнение:
Ответ:
 (1) эффективно неперечислимо 
 (2) эффективно перечислимо 
 (3) совпадает с ним