I I i s

I C

Dg

Dg Dh

O S I

iim n i ₁... in

2. Если h (x_{j 1},..., x_{j r}) =

= f (g ₁(x _1,1,..., x _{1, m 1}),..., g _k(x _k,1,..., x _{k, m k})), то она представляется деревом:

C

D f Dg ₁ ... Dg _k

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

I

1 1 j

3. Пусть f (x ₁,..., x_{n+ 1}) получается из g (x ₁,..., x_n) и h (x ₁,..., x_n, x_{n+ 1}, x_{n+ 2}) с помощью операции примитивной рекурсии:

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

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

M

Пример. Построим дерево, представляющее функцию 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

Дата добавления: 2015-03-31