2015-06-28
375
I. Какие функции получаются из g и h с помощью схемы примитивной рекурсии
1. 
, 
2. , 
3. 
, 
4. ,
5. , 
6. 
,
7. ,
8. , 
9. , 
10. , 
II. Доказать примитивную рекурсивность функции
1. 
2. 
3. 
4. 
5.
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 
14. 
15. 
16. 
17. 
18. 
19. 
20. 
(сумма по модулю 2)
III. Применив операцию минимизации к подходящей примитивно рекурсивной функции, доказать, что функция f является частично рекурсивной.
1. Нигде не определенная функция f, т.е. функция f с пустой областью определения
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
Вопросы для самоконтроля
1 Дайте определение операции суперпозиции.
2 Какие функции называются числовыми функциями?
3 Какие функции называются частично-числовыми?
4 Какие функции называются простейшими?
5 Дайте определение операции примитивной рекурсии.
6 Дайте определение операции минимизации.
7 Какие функции называются примитивно-рекурсивными?
8 Какие функции называются частично-рекурсивными?
Литература
1 Яблонский, С.В. Введение в дискретную математику [Текст]: учебное пособие для вузов по специальности «Прикладная математика»/ С.В.Яблонский. – М.: Наука, 1979. – 272 с.
Тема 9
