Введение в схемы, автоматы и алгоритмы


Определение рекурсивных функций


Мы будем рассматривать частичные арифметические функции fn(x1, …, xn): Nn

N. Здесь верхний индекс n у имени функции f обозначает число ее аргументов ("арность"). Если арность ясна из контекста или несущественна, то этот индекс будем опускать. Определим вначале три оператора, позволяющих по одним функциям получать другие.

Определение 8.1. Суперпозиция. Пусть Fm и f1n,…, fmn

- арифметические функции. Скажем, что функция Gn получена из Fm , f1n, …, fmn с помощью оператора суперпозиции (обозначение: Gn=[Fm;f1n, …, fmn]), если для всех наборов аргументов (x1,…,xn)

G^n(x_1,\ldots,x_n)=F^m(f^n_1(x_1,\ldots,x_n),\ldots, f^n_m(x_1,\ldots,x_n)).

При этом для каждого набора аргументов (a1, …, an) функция Gn(a1, …, an)< ? (т.е. определена), если определены все значения f1n (a1, …, an)=b1,…, fmn (a1, …, an)=bm

и Fm(b1,…, bm) < ?.

Определение 8.2. Примитивная рекурсия. Скажем, что функция Fn+1(x1,… ,xn,y) получена с помощью оператора рекурсии из функций gn(x1,…, xn) и hn+2(x1, …, xn, y, z), если она может быть задана схемой примитивной рекурсии

\left \{ \aligned F^{n+1}&(x_1,\ldots,x_n,0) = g^n(x_1,\ldots,x_n) \\ F^{n+1}&(x_1,\ldots,x_n, y+1) =h^{n+2}(x_1,\ldots,x_n,y, F^{n+1} (x_1,\ldots,x_n,y)) \endaligned \right .

В этом случае будем писать Fn+1 = R(gn,hn+2).

При этом

F(a_1,\ldots, a_n,0)< \infty \ \Longleftrightarrow g^n(a_1,\ldots,a_n) <\infty
и для каждого b

F(a_1,\ldots, a_n,b+1)< \infty \ \Longleftrightarrow F(a_1,\ldots, a_n,b)=c <\infty
и
h^{n+2}(a_1,\ldots, a_n,b,c) < \infty.

В случае, когда n=0, т.е. F зависит от одного аргумента y, а аргументов x1,…,xn нет, схема примитивной рекурсии принимает вид

\left \{ \aligned F^1&(0) = a \\ F^1&(y+1) =h^2(y, F^1(y)), \endaligned \right .

где a

N.

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

Определение 8.3. Минимизация. Скажем, что функция Fn(x1,… ,xn) получена с помощью оператора минимизации(?-оператора) из функции gn+1(x1,…, xn,y), если Fn(x1,…,xn) определена и равна y тогда и только тогда, когда все значения gn+1(x1,…, xn,0),…,gn+1(x1,…, xn,y-1) определены и не равны 0, а gn+1(x1,…, xn,y)=0. В этом случае будем писать

\ F^n(x_1,\ldots, x_n) =\mu y[ g^{n+1}(x_1,\ldots, x_n,y)=0].

Определение 8.4. Простейшие функции. Функция называется простейшей, если она является одной из следующих функций:

  • o1(x)=0 - тождественный нуль;
  • s1(x)= x+1 - следующее число (плюс один);
  • функции выбора аргумента Imn (x1, … ,xn)=xm (1
    m
    n).




Начало    Вперед



Книжный магазин