Математическая логика и теория алгоритмов. Стенюшкина В.А. - 58 стр.

где операция R - двуместная операция, определенная на множестве F всех час-
тичных функций. Если g, h определены всюду, то f определена всюду.

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

      Определение Функция f называется примитивно рекурсивной, если ее
можно получить из простейших функций s,o, Imn конечным числом операций
суперпозиции и примитивной рекурсии.
      Примечания
      1 Операции суперпозиции и примитивной рекурсии, будучи приме-
ненными к всюду определенным функциям, дают в результате всюду опреде-
ленные функции. Поэтому примитивно рекурсивные функции всюду опреде-
лены, а примитивно рекурсивные относительно G определены всюду, если фу-
нкции из G всюду определены.
      2 Операции суперпозиции и примитивной рекурсии, примененные к час-
тичным примитивно рекурсивным относительно G функциям дают в результа-
те примитивно рекурсивные относительно G функции.
      Примеры
      1 Функции s(x)=s1(x)=x+1, o(x)=o1(x)=0, Imn(x1,…,xn)=xm (m,n=1,2,…) при-
митивно рекурсивны по определению.
      2 Функция on(x1,…,xn)=0 примитивно рекурсивна.
      3 Произвольная n-местная постоянная функция допускает представление
в виде терма s(s(…s(on(x1,…,xn))…))=a.
      4Двуместные функции x+y, xy, xy являются примитивно рекурсивными,
как удовлетворяющие схемам соответственно:
      1) x+0=x=I'1(x), x+(y+1)=(x+y)+1=S(x+y) с начальными примитивно реку-
рсивными функциями g(x)=I'1(x), h(x, y, z)=z+1;
      2) x0=0(x), x(y+1)=xy+x с функциями g(x)=o(x), h(x, y, z)=z+x;
      3) x0=1, xy+1=xyx, т.е. g(x)=1, h(x, y, z)=zx;
                            0, x = 0,             1, x = 0,
      4) функции sg ( x) =               sg (x) =             ( sg x = 1 − sgx) удовлетво-
                             1, x > 0,            0 , x > 0 .
ряют      примитивно        рекурсивным         схемам          sg 0 = 0, sg ( x + 1) = 1, и
sg 0 = 1, sg ( x + 1) = 0, т.е. примитивно рекурсивны.
                                           x − y, x ≥ y,
       5) Усеченная разность x −& y =                    (всюду определенная) являет-
                                          0, x < y
ся примитивно рекурсивной. Действительно, функция x÷1 удовлетворяет при-
митивно рекурсивной схеме 0 ∸ 1 = 0 (x + 1) ∸1 = x с примитивно рекурсив-
ными начальными функциями o1 и I12 . Кроме того, для любых x, y имеем схе-
му x∸0 = x , x∸(y + 1) = (x∸ y) ∸1, т.е. x ∸ y возникает примитивной рекурсией
из I11 и h(x, y, z)=z∸1, что требовалось.