Главная / Алгоритмы и дискретные структуры /
Основы теории вычислимых функций / Тест 2
Основы теории вычислимых функций - тест 2
Упражнение 1:
Номер 1
Функция U(n,m)
, - универсальна для класса вычислимых функций одного аргумента, если для каждого n
:
Ответ:
 
(1)  
 
(2)  
 
(3)  
Номер 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)  
 
(2)  
 
(3)  
Упражнение 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) универсальным