Викия

Математика

Примитивно рекурсивная функция

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


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

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

Примитивно рекурсивная функциявычислимая функция нескольких натуральных переменных, частный случай рекурсивной функции.


ОпределениеПравить

Определение понятия примитивно рекурсивной функции является индуктивным. Оно состоит из указания класса исходных примитивно рекурсивных функций и двух операторов (подстановки и примитивной рекурсии), позволяющих строить новые примитивно рекурсивные функции на основе уже имеющихся.

К числу исходных примитивно рекурсивных функций относятся функции следующих трёх видов:

  • Нулевая функция O одного переменного, сопоставляющая любому натуральному числу значение 0.
  • Функция следования S одного переменного, сопоставляющая любому натуральному числу x непосредственно следующее за ним натуральное число x+1.
  • Функции I_n^m, где 0<m\leqslant n, от n переменных, сопоставляющие любому упорядоченному набору x_1,... x_n натуральных чисел число x_m из этого набора.

Операторы подстановки и примитивной рекурсии определяются следующим образом:

  • Пусть f — примитивно рекурсивная функция от m переменных, а g1,... gm — упорядоченный набор примитивно рекурсивных функций от n переменных каждая. Тогда результатом подстановки функций gk в функцию f называется функция h от n переменных, сопоставляющая любому упорядоченному набору x_1,... x_n натуральных чисел число
h(x_1,\ldots\,x_n)=f(g_1(x_1,\ldots\,x_n),\ldots\,g_m(x_1,\ldots\,x_n)).
  • Пусть f — примитивно рекурсивная функция от n переменных, а g — примитивно рекурсивная функция от n+2 переменных. Тогда результатом применения оператора примитивной рекурсии к паре функций f и g называется функция h от n+1 переменной вида
h(x_1,\ldots\,x_n,0)=f(x_1,\ldots\,x_n);
h(x_1,\ldots\,x_n,y+1)=g(x_1,\ldots\,x_n,y,h(x_1,\ldots x_n,y)).

ПримерыПравить

Укажем на ряд широко известных арифметических функций, допускающих рассмотрение в качестве примитивно рекурсивных.

  • Сложение двух натуральных чисел может быть рассмотрено в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения оператора примитивной рекурсии к функциям I_1^1 и f, вторая из которых получается подстановкой основной функции I_3^3 в основную функцию S:
+(x,0)=x;
+(x,y+1)=f(x,y,+(x,y));
f(x,y,z)=S(I_3^3(x,y,z)).
  • Умножение двух натуральных чисел может быть рассмотрено в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения оператора примитивной рекурсии к функциям O и f, вторая из которых получается подстановкой основных функций I_3^1 и I_3^3 в функцию сложения:
\times(x,0)=O(x);
\times(x,y+1)=f(x,y,\times(x,y));
f(x,y,z)=+(I_3^1(x,y,z),I_3^3(x,y,z)).
  • Симметрическая разность (абсолютная величина разности) двух натуральных чисел может быть рассмотрена в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения следующих подстановок и примитивных рекурсий:
-(x,y)=+({-}_1(x,y),{-}_2(x,y));
{-}_2(x,y)={-}_1(I_2^2(x,y),I_2^1(x,y));
\left\{\begin{array}{l}{-}_1(x,0)=I_1^1(x)\\
{-}_1(x,y+1)=f(x,y,{-}_1(x,y))\end{array}\right.;
f(x,y,z)=p(I_3^3(x,y,z));
\left\{\begin{array}{l}p(0)=0\\
p(y+1)=I_2^1(y,p(y))\end{array}\right.;

Границы понятияПравить

Любая примитивно рекурсивная функция является общерекурсивной, т. е. принимающей некоторое значение на любом отвечающем числу аргументов функции наборе натуральных чисел. Соответственно, рекурсивные функции, не являющиеся общерекурсивными, заведомо не относятся к числу примитивно рекурсивных функций. Известны также и общерекурсивные функции, не являющиеся примитивно рекурсивными. Стандартным примером здесь является функция Аккермана.

Следует, однако, заметить, что произвольная рекурсивная функция от n  переменных может быть получена из примитивно рекурсивной функции от n+1 переменной применением оператора минимизации.

ЛитератураПравить

Викия-сеть

Случайная вики