2015-03-27
550
1. Показать, что функцию 
можно получить с помощью оператора минимизации.
Указание: 
.
2. Доказать, что функция от 
, равная расстоянию от до ближайшего слева точного квадрата примитивно рекурсивна.
Указание: 
. 
- искомая функция; напоминаем, что мы рассматриваем только целочисленные функции.
3. Доказать, что всякое конечное множество 
- примитивно рекурсивно.
Указание: 
, где 
- характеристическая функция множества 
.
4. Пусть 
десятичная запись числа 
. Пусть 
. Доказать, что функция 
примитивно рекурсивна.
Указание: Т.к. 
, 
, 
, …, то 
, 
, 
, 
, …, 
, …
5. Обозначим через 
функцию, полученную с помощью оператора минимизации из функции 
. Если - одноместная функция, то называют обратной функцией и обозначают 
. Значит по определению 
. Найти 
и 
.
6. Доказать, что операторы подстановки и примитивной рекурсии, применяемые к примитивно рекурсивным функциям дают снова примитивно рекурсивные функции.
7. Доказать, что всякая всюду определенная функция, равная натуральному числу 
везде за исключением конечного числа точек, является примитивно рекурсивной функцией.
|
|
|
8. Если значения примитивно рекурсивной или частично рекурсивной функции изменить лишь на конечном множестве точек, то новая функция будет снова примитивно рекурсивной или соответственно частично рекурсивной.
9. Показать, что совокупность чисел 
примитивно рекурсивна.
Указание: 
, т.е. 
.
10. Доказать, что множество чисел вида 
примитивно рекурсивно.
