ФУНКЦИЙ

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

Для этого полное определение произвольной частично- рекурсивной функции представляется в виде специального нагруженного дерева.

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

Будем считать, что для обозначения переменных функций используются только следующие символы: x₁, . . . , x_i, . . .

При разметке вершин деревьев используются следующие символы:

1)C, P, M -для обозначения операций суперпозиции, примитивной рекурсии и минимизации;

2) 1-для записи индексов переменных в унарной системе;

3) I, S, O - для обозначения простейших функций.

Определим деревья, представляющие схемы определения частично-рекурсивных функций, с помощью следующих правил:

1. Функции O(x_i), S(x_i) и (x_i1, ... , x_in) представляются следующими деревьями:

O S I

iim n i₁ . . . in

= f(g₁(x_1,1, . . . , x_1,m1), . . . , g_k(x_k,1, . . . , x_k,mk)), то она представляется деревом:

C

D f Dg₁ . . . Dg_k

Здесь Df, Dg₁, ... , Dg_k - это деревья, представляющие функции, входящие в суперпозицию. В частности, если g_i = x_j, то есть представляет собой переменную, то соответствующее дерево имеет вид:

I

1 1 j

f(x₁, . . . , x_n, 0) = g(x₁, . . . , x_n);

f(x₁, . . . , x_n, y+1) = h(x₁, . . . , x_n, y, f(x₁, . . . , x_n, y)).

Тогда f представляется деревом:

P

Dg Dh

4. Если f(x₁, . . . , x_n+1) = m t(g(x₁, . . . , x_n, t) = x_n+1), то дерево, представляющее f, имеет вид:

M

Dg

Пример.Построим дерево, представляющее функцию f(x₁, x₂) = x₁+ x₂.

Эта функция была определена ранее с помощью следующей схемы примитивной рекурсии:

f(x₁, 0) = (x₁);

f(x₁, x₂ + 1)= (x₁, x₂, S(f(x₁, x₂)).

Здесь определения функций g и h, из схемы примитивной рекурсии, даны в полном виде с указанием всех переменных (в том числе и несущественных) этих функций в определении схемы примитивной рекурсии.

Поэтому дерево определения f имеет вид, приведенный на рис. 8.1:

P

I C