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

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

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

Номер 1

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

Ответ:

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

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

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

Номер 2

Множество  m-сводится к , если существует:

Ответ:

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

(2)

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

Номер 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) совпадает с ним

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