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

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

f(x)=x+1, z(x)=0, Jⁿ_m(x₁,…, x_n)=x_m

Конечным числом операторов (операций) суперпозиции (подстановок) Sⁿ_m, и примитивной рекурсии R_n называется примитивно-рекурсивной (ПРФ).

Базисную функцию f(x)=x+1 принято называть функцией следования (эту функцию иногда обозначают х` и называют функцией прибавления единицы), z(x)=0 – нуль функцией, Jⁿ_m(x₁,…, x_n)=x_m – функцией тождества (или введения фиктивных переменных), где nm.

Def. Оператором суперпозиции Sⁿ_m называется операция подстановки в функцию от m переменных m функций от n переменных. (одних и тех же).

Пример. Функция f(x₁,…, x_n) возникает из функций h(x₁,…, x_m), g₁(x₁,…, x_n), …g_m(x₁,…, x_n) суперпозицией, если

f(x₁,…, x_n)= Sⁿ_m(h, g₁,…, g_m) = h(g₁(x₁,…, x_n), …, g_m (x₁,…, x_n)).

Если заданы функции Jⁿ_m и операторы Sⁿ_m, то можно считать заданными всевозможные операторы подстановки функции в функцию, а также переименования, перестановки и отождествления переменных.

Так, если f(x₁, x₂)= h(g₁(x₁, x₂), g₂(x₁)), то ее стандартный вид следующий: f(x₁, x₂)= S²₂(h(x₁, x₂), g₁ (x₁, x₂), S¹₂ (J²₁(x₁, x₂), g₂(x₁), g₃(x₁))), где g₃ – любая функция от х₁. Если же имеем f(x₂, x₁, х₃, …, x_n) и f(x₁, x_1, x₃,…, x_n), то пишем:

f(x₂, x₁, х₃, …, x_n) = f(J²₂(x₁, x₂), J²₁(x₁, x₂), х₃, …, x_n),

f(x₁, x_1, x₃,…, x_n)= f(J²₁(x₁, x₂), J²₁(x₁, x₂), х₃, …, x_n).

Def. Оператором примитивной рекурсии R_n называется процесс определения функфии f (n+1) переменных через n-местную функцию g и (n+2)- местную функцию h в следующем виде:

f(x₁, x_2, …, x_n, 0)= g(x₁, x₂,…, x_n)

f(x₁, x_2, …, x_n, y+1)=h(x₁, x₂,…, x_n, y, f(x₁, x_2, …, x_n, y)),

где g и h – две различные функции соответственно n и n+2 аргументов.

Эта пара равенств называется схемой примитивной рекурсии. Тот факт, что функция f определена схемой примитивной рекурсии выражается равенством f(x₁, x_2, …, x_n, y)=R_n(g, h). В случае, когда n=0, то есть определяемая функция f является одноместной, схема примитивной рекурсии принимает более простой вид:

f(0)=с, f(у+1)=h(y, f(y)), где с – константа.

Схема примитивной рекурсии определяет f рекурсивно не только через другие функции g и h, но и через значения f в предшествующих точках: значение функции f в точке у+1 зависит от значения функции f в точке у. Очевидно, что для вычисления f(x₁,…, x_n, k) понадобиться k+1 вычислений по схеме примитивной рекурсии – для у=0, k.

Замечания:

1. Существенным в операторе примитивной рекурсии R_n является то, что независимо от числа переменных в f рекурсия ведется только по одной переменной у (остальные n переменных x₁, x_2, …, x_n на момент применения схемы примитивной рекурсии зафиксированы и играют роль параметров).

2. Формальное индуктивное определение примитивно-рекурсивной функции следующее:

• функции 0, х`, Jⁿ_m для всех натуральных n, m, где nm являются примитивно-рекурсивными;

• если g₁(x₁,…, x_n), …g_m(x₁,…, x_n), h(x₁,…, x_m) - примитивно-рекурсивные функции, то Sⁿ_m(h, g₁,…, g_m) - примитивно-рекурсивные функции для любых натуральных n, m;

• если g(x₁,…, x_n) и h(x₁,…, x_m, у, z) - примитивно-рекурсивные функции, то R_n(g, h) – примитивно-рекурсивная функция;

• других примитивно-рекурсивных функций нет.

3. Схемной интерпретацией примитивной рекурсии может быть схема:

Эта схема состоит из элемента, вычисляющего за один такт функцию h от двух переменных и элемента задержки на один такт. По каналам схемы могут передаваться натуральные числа. Время t считается дискретным, то есть t=0, 1, 2, 3…. Схема имеет один вход х и один выход f. Выход f зависит не только от х, но и от момента t, в котором он рассматривается. В начальный момент t=0 второй вход h является константой с, зависящей от начального состояния схемы: f(x, 0)=h(x, c)=g(x). В момент t=1: f(x, 1)=h(x, f(x, 0)); в общем случае f(x, t+1)=h(x, f(x,t)). Нетрудно убедиться, например, что если h выполняет умножение, а с=1, то f(x, t)=x^t+1.

4. Поскольку исходные (базисные) функции являются вычислимыми, а операторы суперпозиции и примитивной рекурсии вычислимость сохраняют, то множество всех примитивно-рекурсивных функций есть подкласс класса всех вычислимых функций;

5. Класс всех примитивно-рекурсивных функций счетен, поскольку каждая такая функция задается описанием ее построения из исходных функций.

6. Практически все арифметические функции, употребляемые в математике по конкретным поводам, являются примитивно-рекурсивными функциями, например: х+у, х*у, х^у и т.д.