Практическая работа № 11

«ПРИМИТИВНО РЕКУРСИВНЫЕ ФУНКЦИИ»

Цель работы: освоить приёмы работы с примитивно рекурсивными функциями.

 

Краткие теоретические сведения

 

Рекурсивные функции рассматриваются на множестве натуральных чисел и принимают натуральные значения.

Рекурсивные функции определены частично (не для всех значений аргументов).

Простейшими рекурсивными функциями являются:

1) S(x) = x + 1 (функция следования)

2) O(x) = 0 (нуль-функция)

3) I_mⁿ(x₁, x₂, …, x_n) = x_m (функции- проекторы), где m = 1, …, n.

В качестве операторов, с помощью которых будут строиться новые функции, выберем следующие три: операторы суперпозиции, примитивной рекурсии и минимизации.

n -местная функция j получена из m -местной функции f и n -местных функций g ₁,..., g_m с помощью оператора суперпозиции, если для всех х ₁,..., х _n справедливо равенство:

 

 

(n + 1)-местная функция j получена из n -местной функции f и (n + 2)-местной функции g с помощью оператора примитивной рекурсии, если для любых х ₁,..., х_n, у, справедливы равенства:

 

 

Пара этих равенств определяет схему примитивной рекурсии.

 

Образец выполнения

 

Вычислить значение функции с помощью оператора примитивной рекурсии

 

, . Найти        

 

Решение

Последовательно вычисляем

 

j(2, 0) = 2² + 1 = 5

 

j(2, 1) = 0*(2 + j(2, 0)) = 0*(2 + 5) = 0

 

j(2, 2) = 1*(2 + j(2, 1)) = 1*(2 + 0) = 2

 

j(2, 3) = 2*(2 + j(2, 2)) = 2*(2 + 2) = 8

 

 

Задания.

 

Вычислить значение функции с помощью оператора примитивной рекурсии

 

1) ,. Найти

 

2) ,. Найти    

 

3) ,. Найти

 

4) ,. Найти

 

5) ,. Найти

 

6) ,. Найти

7) ,. Найти

 

8) ,. Найти

 

9) ,. Найти

 

Контрольные вопросы

 

1. Какие функции относятся к простейшим рекурсивным

2. Как построить новые рекурсивные функции из простейших.

3. Что такое схема примитивной рекурсии.

 

Ход выполнения работы:

 

1. Изучить теоретический материал.

2. Получить задание у преподавателя.

3. Выполнить задание.

4. Ответить на контрольные вопросы.

5. Защитить выполненное задание.