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

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

Номер 1

Если U - главная универсальная функция, а X - множество натуральных чисел n, где U_n - нигде не определена, то U_n:

Ответ:

(1) неразрешимо

(2) разрешимо

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

Номер 2

Множество номеров нигде не определенной функции:

Ответ:

(1) неразрешимо

(2) неперечислимо

(3) разрешимо

Номер 3

Если дополнение неразрешимого множества перечислимо, то само множество:

Ответ:

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

(2) не перечислимо

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

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

Номер 1

Если Y - класс вычислимых одноместных функций, а , то множество :

Ответ:

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

(2) неразрешимо

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

Номер 2

Функция ,  где K  -перечислимое и неразрешимое, является:

Ответ:

(1) вычислимой

(2) невычислимой

(3) неопределенной

Номер 3

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

Ответ:

(1) можно построить алгоритмически

(2) нельзя построить алгоритмически

(3) можно описать математически, но не алгоритмически

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

Номер 1

В теореме Успенского - Райса утверждается, что в главной нумерации:

Ответ:

(1) множество номеров любой функции не разрешимо

(2) множество номеров любой функции бесконечно

(3) множество номеров любой функции счетно

Номер 2

В теореме Роджерса утверждается, что трансляторы, сводящие главные нумерации друг к другу выбираемы:

Ответ:

(1) взаимно обратным образом

(2) взаимно противоположным образом

(3) независимо друг от друга

Номер 3

Любые две нумерации перечислимых множеств:

Ответ:

(1) изоморфны

(2) гомеоморфны

(3) взаимообратны

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

Номер 1

Верно утверждение:

Ответ:

(1) нетривиальные свойства функций - не разрешимы

(2) нетривиальные свойства функций - разрешимы

(3) разрешимые функции имеют только нетривиальные свойства

Номер 2

Верно утверждение:

Ответ:

(1) некоторые свойства функций перечислимы

(2) все свойства функций перечислимы

(3) нет перечислимых свойств функции

Номер 3

Верно утверждение:

Ответ:

(1) образец - конечный список пар <аргумент, значение>

(2) образец - функция характеристическая

(3) образец - подмножество множества пар <смысл, значение>

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

Номер 1

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

Ответ:

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

(2) не перечислимо

(3) пусто

Номер 2

Любое перечислимое свойство:

Ответ:

(1) открыто

(2) замкнуто

(3) гомеоморфно другому

Номер 3

Образец - это:

Ответ:

(1) функция с натуральными аргументами

(2) множество из натуральных чисел

(3) свойство вычислимых функций

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

Номер 1

Образцом является:

Ответ:

(1) двоичное слово

(2) дельта - функция

(3) характеристическая функция

Номер 2

Образцом является:

Ответ:

(1) номера слов по порядку

(2) лексикографически упорядоченный список слов

(3) длины слов расположенные по их возрастанию

Номер 3

Образцом является (n - натуральное, x - вещественное число):

Ответ:

(1) sign(n)

(2)

(3) sin(x)

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

Номер 1

Образцом не является (n - натуральное, x - вещественное число):

Ответ:

(1) sign(n+n²)

(2)

(3) int(x)

Номер 2

Образец является:

Ответ:

(1) конструктивным объектом

(2) конструктивной функцией

(3) конструктивным множеством

Номер 3

Если X - класс вычислимых одноместных функции, а Y - его подмножество, то верно утверждение:

Ответ:

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

(2) вычислимое продолжение функции Y не принадлежит Y

(3) вычислимые композиции функций Y принадлежат Y

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

Номер 1

Если X - класс вычислимых одноместных функции, а Y - его подмножество, то верно утверждение:

Ответ:

(1) существует функция - образец из Y

(2) не существует функции - образца из Y

(3) все вычислимые суперпозиции Y имеют образцы

Номер 2

Если X - класс вычислимых одноместных функции, Y из X, Z - перечислимое неразрешимое множество, U - главная функция, то существует всюду определенная функция f со свойством:

Ответ:

(1)

(2)

(3)

Номер 3

Если X - класс вычислимых одноместных функции, Y из X, Z - перечислимое неразрешимое множество, U - главная функция, то существует всюду определенная функция f со свойством:

Ответ:

(1)

(2)

(3)

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