 |
Частично рекурсивные функции и рекурсивные предикаты. Класс частично рекурсивных функций. Исходные функции.
|
|
|
|
1. Рекурсией называется …
+ способ задания функции, при котором значение определяемой функции для произвольных значений аргументов выражается известным образом через значения определяемой функции для меньших значений аргументов
– способ задания функции, при котором каждое значение определяемой функции для произвольных значений аргументов выражается через другие известные функции
– вычисление функции через базовые функции с помощью известных алгоритмов
– способ задания функции, при котором значения определяемой функции для произвольных значений аргументов на разных промежутках области определения выражается через различные известные функции
2. Отметьте все элементарные (исходные, базовые) функции для построения класса частично рекурсивных функций:
+ нуль-функция: O(x)=0;
+ функция следования: S(x)=x+1;
+ функция проецирования (выбора): Inm(x1,x2,...,xn)=xm, 1£m£n.
– функция – константа Cqn(x1,x2,...,xn)=q, nÎN, qÎ N
3. Укажите истинные высказывания:
+ множество частично рекурсивных функций – счетно
+ классы частично рекурсивных функций, функций вычислимых по Тьюрингу и по Маркову эквивалентны
– не существует нигде не определенной вычислимой функции
– множество функций счетно
4. Выберите истинное всказывание:
– класс примитивно-рекурсивных функций шире класса частично рекурсивных функций
+ класс частично рекурсивных функций включает класс примитивно-рекурсивных функций
– класс частично рекурсивных функций совпадает с классом примитивно-рекурсивных функций
– пересечение класса частично рекурсивных функций и класса примитивно-рекурсивных функций пусто
5. Функция f называется частично рекурсивной относительно множества простейших функций из базового набора, если она строится
|
|
|
+ из простейших вычислимых функций конечным числом применения операторов суперпозиции, примитивной рекурсии и минимизации
– из простейших вычислимых функций конечным числом применения оператора суперпозиции
– из простейших вычислимых функций конечным числом применения операторов суперпозиции и примитивной рекурсии
– из нуль-функции и функции следования конечным числом применения операторов суперпозиции, примитивной рекурсии и минимизации
6. Функция f называется примитивно-рекурсивной относительно множества простейших функций из базового набора, если она строится
– из простейших вычислимых функций конечным числом применения операторов суперпозиции, примитивной рекурсии и минимизации
– из простейших вычислимых функций конечным числом применения оператора примитивной рекурсии
+ из простейших вычислимых функций конечным числом применения операторов суперпозиции и примитивной рекурсии
– из нуль-функции и функции следования конечным числом применения операторов суперпозиции, примитивной рекурсии и минимизации
7. Выберите истинные всказывания:
+ всякая примитивно-рекурсивная функция всюду определена
+ если функция f получена из примитивно-рекурсивных функций с применением операций подстановки или примитивной рекурсии, то функция f является примитивно-рекурсивной функцией
+ все примитивно-рекурсивные функции интуитивно вычислимы
– все частично рекурсивные функции являются примитивно-рекурсивными
8. Возвратной рекурсией (рекурсией пробега) называется такая рекурсия, при которой
+ значение f(x1,...,xn, y+1) зависит от x1,..., xn, y, а также от некоторых и возможно всех f(x1,...,xn,u), где u£y
– значение f(x1,...,xn, y+1) зависит от x1,..., xn, y, а также от f(x1,...,xn, y)
– значение f(x1,...,xn, y+1) зависит от f(x1,...,xn, y)
– значение f(x1,...,xn, y+1) зависит от x1,..., xn, y, а также от некоторых и возможно всех f(x1,...,xn,u), где u³y
|
|
|
9. Функции f1n+1,...,fkn+1 определены с помощью совместной рекурсии, если для всех 1£i£k имеет место следующая система равенств:
– 
+ 
– 
– 
10. n-местным предикатом Pn, заданным на множестве M, называется …
– отображение Pn: Mn® N0
– отображение Pn:M ®{0,1}
– логическое высказывание
+ отображение Pn:Mn®{0,1}
11. Характеристической (представляющей) функцией предиката Pn называется такая функция c Pn что …
– cPn ( 
)=(if Pn( ) – истинно then 0 else Pn( ))
– c Pn ( )=(if Pn( )– истинно then 0 else не определено)
+ c Pn ( )=(if Pn( )– истинно then 0 else 1)
– c Pn ( )=(if Pn( )– истинно then Pn( ) else не определено)
12. Предикат Pn называется примитивно-рекурсивным, если …
+ его характеристическая функция примитивно-рекурсивна
– его характеристическая функция частично рекурсивна
– его характеристическая функция вычислима
– существует алгоритм его вычисляющий
|
|
|
