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

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

Упражнение 1:
Номер 1
Для доказательства неразрешимости множества X достаточно доказать, что:

Ответ:

 (1) любое перечислимое множество - разрешимо 

 (2) некоторое перечислимое множество - разрешимо 

 (3) N перечислимо вместе с X  


Номер 2
Множество math m-сводится к math, если существует:

Ответ:

 (1) вычислимая функция y=f(x), где x, y - натуральные: 

 (2) math 

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


Номер 3
Для m-сводящей X к Y функции f используют обозначение:

Ответ:

 (1) math 

 (2) math 

 (3) math 


Упражнение 2:
Номер 1
Если math и Y - разрешимо, то: 

Ответ:

 (1) X - разрешимо 

 (2) Y - m-разрешимо 

 (3) X - не разрешимо 


Номер 2
Если math и Y - перечислимо, то: 

Ответ:

 (1) X - перечислимо 

 (2) Y - m-разрешимо 

 (3) X - не перечислимо 


Номер 3
Если math и math, то: 

Ответ:

 (1) math 

 (2) math 

 (3) math 


Упражнение 3:
Номер 1
m-сводящей X к X будет функция: 

Ответ:

 (1) тождественная 

 (2) единичная (для любого аргумента равна 1

 (3) характеристическая 


Номер 2
Если f сводит Х к Y, g - Y к Z, то: 

Ответ:

 (1) math 

 (2) math 

 (3) math 


Номер 3
Если f сводит Х к Y, то она сводит: 

Ответ:

 (1) N\X к N\Y 

 (2) math к math 

 (3) math к math 


Упражнение 4:
Номер 1
Неверно для произвольных множеств:

Ответ:

 (1) math 

 (2) math 

 (3) math 


Номер 2
Неверно для произвольных множеств:

Ответ:

 (1) math 

 (2) math 

 (3) math 


Номер 3
Неверно для произвольных множеств:

Ответ:

 (1) math 

 (2) math 

 (3) math 


Упражнение 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) math 

 (2) math 

 (3) math 


Номер 3
Если math и X - эффективно неперечислимо, то: 

Ответ:

 (1) math и X\Y - эффективно неперечислимы 

 (2) math и X\Y - эффективно неперечислимы 

 (3) Y - эффективно неперечислима 


Упражнение 8:
Номер 1
Для универсального перечислимого множества W-перечислимо множество: 

Ответ:

 (1) math 

 (2) math 

 (3) math 


Номер 2
Множества с эффективно неперечислимыми дополнениями: 

Ответ:

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

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

 (3) не существуют только для простых дополнений 


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

Ответ:

 (1) эффективно неперечислимо 

 (2) эффективно перечислимо 

 (3) совпадает с ним 




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