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

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

Упражнение 1:
Номер 1
Функция U(n,m), math - универсальна для класса вычислимых функций одного аргумента, если для каждого n:

Ответ:

 (1) math 

 (2) math 

 (3) math 


Номер 2
Вычислимая функция двух аргументов, являющаяся универсальной функцией для класса вычислимых функций одного аргумента:

Ответ:

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

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

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


Номер 3
Множество X из N×N - универсальное, если:

Ответ:

 (1) все сечения принадлежит этому классу 

 (2) других множеств в классе нет 

 (3) все сечения из этого класса и других множеств в классе нет 


Упражнение 2:
Номер 1
Вычислимая всюду определенная функция двух аргументов, универсальная для класса всех вычислимых функций одного аргумента:

Ответ:

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

 (2) существует, если всюду определена 

 (3) существует 


Номер 2
Вычислимая функция, не имеющая всюду определенного вычислимого продолжения:

Ответ:

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

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

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


Номер 3
Перечислимое неразрешимое множество;

Ответ:

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

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

 (3) существует, если перечислимо его дополнение 


Упражнение 3:
Номер 1
Вычислимая функция со значением {0,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
Равенство f(n)=d(n) может означать, что:

Ответ:

 (1) значения f(n) и d(n) не определены 

 (2) значения f(n) и d(n) определены и равны 

 (3) f(n) и d(n) тождественны на D(f) и на D(d) 


Номер 3
Равенство f(n)=U(n,n) определяет:

Ответ:

 (1) диагональную функцию 

 (2) диаметр множества N 

 (3) декартово произведение 


Упражнение 6:
Номер 1
Перечислимое множество с неперечислимым дополнением:

Ответ:

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

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

 (3) простое 


Номер 2
Проблема остановки состоит в выяснении того, что:

Ответ:

 (1) программа остановится на данном входе 

 (2) программа зацикливается на данном входе 

 (3) программа устойчива 


Номер 3
Непересекающиеся множества X и Y отделяются множеством Z, если:

Ответ:

 (1) math 

 (2) math 

 (3) math 


Упражнение 7:
Номер 1
Если d - вычислимая функция, E(d)={0,1} и не имеет всюду определенного вычислимого продолжения, то:

Ответ:

 (1) X={x: d(x)=1} - не перечислимо 

 (2) X={x: d(x)=1} - перечислимо 

 (3) E(d) - перечислимо 


Номер 2
Если d - вычислимая функция, E(d)={0,1} и не имеет всюду определенного вычислимого продолжения, то:

Ответ:

 (1) X={x: d(x)=0} - не перечислимо 

 (2) X={x: d(x)=0} - перечислимо 

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


Номер 3
Если два множества неотделимы разрешимыми множествами, то:

Ответ:

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

 (2) каждая из них разрешима 

 (3) либо оба разрешимы, либо оба неразрешимы 


Упражнение 8:
Номер 1
Счетное число непересекающихся перечислимых множеств попарно неотделимых разрешимым множеством:

Ответ:

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

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

 (3) счетно 


Номер 2
Бесконечное множество, не содержащее бесконечных разрешимых подмножеств является:

Ответ:

 (1) иммунным 

 (2) несчетным 

 (3) счетным 


Номер 3
Перечислимое множество, для которого прямой пересчет его дополнения неограничен сверху вычислимой функцией является:

Ответ:

 (1) определенным 

 (2) простым 

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




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