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

        6) Из примитивной рекурсивности функций “+” и “– “следует примитив-
ная рекурсивность функции / x-y /=(x∸y)+(y∸x).
                                      2.1.3 Нумерация n-ок чисел

     Определение Канторовское расположение двоек (пар) (x,y) чисел из N
имеет вид
     (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), (0,3),...                                                            (2.4)
       1                    2              3                 4                 5                   6                7 …
(пары расположены по возрастанию суммы элементов, а в сумме - по возрас-
танию первого элемента).
     Функции n=c(x,y), x= l(n), y=r(n), где n-номер пары (x,y), называются кан-
торовскими нумерационными функциями.
     Лемма 1 Канторовские нумерационные функции являются примитивно
рекурсивными.
     Лемма 2 Функция Геделя /1/ Г(x,y)=rest(l(x),1+(y+1)r(x)) примитивно ре-
курсивна.
       Канторовское расположение n-ок чисел из N определяется равенствами:
       c 3 ( x1 , x2 , x3 ) = c(c( x1 , x2 ), x3 ); c n+1 ( x1 ,..., xn +1 ) = c n (c( x1 , x2 ), x3 ,..., xn +1 ).
     Число c n ( x1 ,..., x n ) называется канторовским номером n-ки ( x1 ,..., x n ) .

         2.1.4 Операция минимизации. Частично рекурсивные функции
      Пусть f - n-местная частичная числовая функция, и известен механизм ее
вычисления (в интуитивном смысле), причем механизм работает бесконечно
тогда и только тогда, когда значение функции не определено.
      Рассмотрим относительно y уравнение f(x1,...,xn-1,y)=xn Будем давать пе-
ременной y значения 0,1,2,... последовательно и вычислять значения функции f
соответственно (при фиксированных x1,...,xn). Определим частичную функцию
Mf аргументов x1,...,xn следующим образом. Положим ее значение y=a, если
выполнены условия:
      1) значение f(x1,...,xn-1 ,y) определено для y=0,1,...,a-1, и f(x1,...,xn-1 ,y)≠xn ;
      2) f(x1,...,xn-1 ,a)=xn.
       Если для набора (x1,...,xn) числа a , удовлетворяющего указанным услови-
ям, не существует, значение y будем считать неопределенным.
      Определение Оператор M, переводящий функцию f в функцию Mf, назы-
вается оператором минимизации. Если заданная функция f одноместна то фу-
нкция Mf называется обратной функцией для f и обозначается f-1.
      Примеры
      1 Для функций sg и s обратными будут функции
                 x, x = 0, 1                         x − 1, x > 0
      sg −1 x =                       ; s −1 ( x) =                          .
                не существует, x > 1                не существует, x = 0