Примитивно-рекурсивные функции. Примеры решений
На этой странице вы найдете готовые примеры заданий по проверки примитивной рекурсивности функции.
Типовые задачи снабжены подробным решением, формулами, пояснениями. Используйте их, чтобы научиться решать подобные задачи или закажите решение своей работы нам.
Еще примеры: Конечные автоматы, машина Тьюринга, Нормальные алгоритмы
Задачи и решения о рекурсивных функциях
Задача 1. Пользуясь определением примитивно рекурсивной функции, показать что числовая функция $f(x)$ примитивно рекурсивна. $f(x)=x!$
Задача 2. Доказать примитивную рекурсивность следующей функции $f(x,y)=x\cdot y$.
Задача 3. Доказать, что заданная функция, определенная для натуральных аргументов и принимающая натуральные значения, является примитивно рекурсивной. $f(x,y)=x^y+x$.
Примитивно-рекурсивные функции
Введем базис простых операций:
- Константа 0
- Функция следования $x'=x+1$ (иногда обозначается $S(x)=x+1$)
- Функция проекции $I_m^n(x_1,x_2,....,x_n)=x_m$
Оператором суперпозиции (оператором подстановки) $S_m^n$ называется подстановка в функцию от $m$ переменных $m$ функций от $n$ одних и тех же переменных. Суперпозиция дает новую функцию от $n$ переменных.
Оператор примитивной рекурсии $R_n$ определяет $(n+1)$ – местную функцию $f$ через $n$ – местную функцию $g$ и $(n+2)$ – местную функцию $h$ так:
$$ f(x_1,...,x_n,0)=g(x_1,...,x_n),\\ f(x_1,...,x_n,y+1)=h(x_1,...,x_n, y, f(x_1,...,x_n,y). $$Эта пара равенств называется схемой примитивной рекурсии и обозначается, как
$$ f(x_1,...,x_n,y) = R_n(g,h). $$Данная схема определяет функцию $f$ рекурсивно не только через другие функции, но и через значения самой $f$ в предшествующих точках. Существенным в операторе примитивной рекурсии является то, что независимо от числа переменных в $f$ рекурсия ведется только по одной переменной $y$, а остальные $n$ переменных $x_1,...,x_n$ на момент применения схемы рекурсии зафиксированы и играют роль параметров.
Функция называется примитивно-рекурсивной, если она может быть получена из константы 0, функции $x'$ и функции $I_m^n$ с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.
Основные примитивно-рекурсивные функции: сложение $a+b$, умножение $ab$, возведение в степень $a^b$, симметрическая разность $|a-b|$.
