Примитивно-рекурсивные функции. Примеры решений

На этой странице вы найдете готовые примеры заданий по проверки примитивной рекурсивности функции.

Типовые задачи снабжены подробным решением, формулами, пояснениями. Используйте их, чтобы научиться решать подобные задачи или закажите решение своей работы нам.

Еще примеры: Конечные автоматы, машина Тьюринга, Нормальные алгоритмы


Полезная страница? Сохрани или расскажи друзьям

Задачи и решения о рекурсивных функциях

Задача 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|$.