Математическая логика и теория алгоритмов. Сергиевская И.М. - 42 стр.

UptoLike

ВУЗ: 

ПГУТИ | Самара

Составители: 

Рубрика: 

47
Тогда функция ),,...,,(
21
1
yxxxf
n
n
+
получена с помощью оператора
примитивной рекурсии, что выражается обозначением
),(
21 ++
=
nn
n
n
Rf
ψϕ
.
Таким образом, сначала (при фиксированных значениях
n
xxx ,...,,
21
)
определяется значение функции
1+n
f при 0
=
y , а затем каждое следующее
значение функции (зависящее от 1
+
y ) выражается через предыдущее значение
(зависящее от
y ).
Пусть 0=
n . Тогда функция
0
ϕ
есть постоянная. Обозначим ее следующим
образом:
a=
0
ϕ
. Функция
2+n
ψ
зависит от двух переменных. Обозначим ее так:
),(),(
2
zyzy
ψ
ψ
= . Тогда
a
f
=)0(,
=+ )1(
y
f
))(,( y
f
y
ψ
.
Для произвольного
n получаем (обозначения
0
b ,
1
b ,
2
b , …,
y
b вводятся в
предположении, что набор
n
xxx ,...,,
21
фиксирован):
=
+
)0,,...,,(
21
1
n
n
xxxf
021
),...,,( bxxx
n
n
=
ϕ
,
=
+
)1,,...,,(
21
1
n
n
xxxf
1021
2
),0,,...,,( bbxxx
n
n
=
+
ψ
,
=
+
)2,,...,,(
21
1
n
n
xxxf
2121
2
),1,,...,,( bbxxx
n
n
=
+
ψ
,
. . . . . . . . . . . . . . . . . .
=+
+
)1,,...,,(
21
1
yxxxf
n
n
),,,...,,(
21
2
yn
n
byxxx
+
ψ
.
. . . . . . . . . . . . . . . . . .
Пример.
Даны функции
x
x
=
)(
ϕ
и
xz
zy
x
=
),,(
ψ
. Определим функцию
),(
y
x
f
, полученную из данных функций по схеме примитивной рекурсии.
Решение. Найдем значения функции ),( y
x
f
.
=)0,(
x
f
x
x
=)(
ϕ
,
=)1,(
x
f
=))0,(,0,(
x
f
x
ψ
2
),0,( xxxxx =⋅=
ψ
;
=)2,(
x
f
=))1,(,1,(
x
f
x
ψ
322
),0,( xxxxx =⋅=
ψ
;
=)3,(
x
f
=))2,(,2,(
x
f
x
ψ
433
),0,( xxxxx =⋅=
ψ
.
Можно предположить, что
=
),( y
x
f
1+y
x
.
Докажем последнюю формулу методом математической индукции по
переменной
y .
1.
Проверим формулу при 0=y .
=)0,(
x
f
10+
=
x
x
, то есть при 0=y формула верна.
2.
Допустим, что предположение индукции верно при ny
=
, то есть, верна формула
=),(
n
x
f
1+n
x
. 
              Тогда функция                 f n+1 ( x1 , x2 ,..., xn , y )   получена с помощью оператора
    примитивной рекурсии, что выражается обозначением f n+1 = Rn (ϕ n ,ψ n+ 2 ) .

         Таким         образом,         сначала         (при        фиксированных     значениях   x1 , x2 ,..., xn )
определяется значение функции f n +1 при y = 0 , а затем каждое следующее
значение функции (зависящее от y + 1 ) выражается через предыдущее значение
(зависящее от y ).
         Пусть n = 0 . Тогда функция ϕ 0 есть постоянная. Обозначим ее следующим
образом: ϕ 0 = a . Функция ψ n+ 2 зависит от двух переменных. Обозначим ее так:
ψ 2 ( y, z ) = ψ ( y, z ) . Тогда
 f ( 0) = a ,
 f ( y + 1) = ψ ( y, f ( y )) .

         Для произвольного n получаем (обозначения b0 , b1 , b2 , …, b y вводятся в
предположении, что набор x1 , x2 ,..., xn фиксирован):
 f n+1 ( x1 , x2 ,..., xn ,0) = ϕ n ( x1 , x2 ,..., xn ) = b0 ,
 f n+1 ( x1 , x2 ,..., xn ,1) = ψ n+ 2 ( x1 , x2 ,..., xn ,0, b0 ) = b1 ,
 f n+1 ( x1 , x2 ,..., xn ,2) = ψ n+ 2 ( x1 , x2 ,..., xn ,1, b1 ) = b2 ,
. . . . . . . . . . . . . . . . . .
 f n+1 ( x1 , x2 ,..., xn , y + 1) = ψ n+ 2 ( x1 , x2 ,..., xn , y, b y ) .
. . . . . . . . . . . . . . . . . .

         Пример. Даны функции ϕ ( x) = x и ψ ( x, y, z ) = xz . Определим функцию
 f ( x, y ) , полученную из данных функций по схеме примитивной рекурсии.
         Решение. Найдем значения функции f ( x, y ) .
 f ( x,0) = ϕ ( x) = x ,
 f ( x,1) = ψ ( x,0, f ( x,0)) = ψ ( x,0, x) = x ⋅ x = x 2 ;
 f ( x,2) = ψ ( x,1, f ( x,1)) = ψ ( x,0, x 2 ) = x ⋅ x 2 = x 3 ;
 f ( x,3) = ψ ( x,2, f ( x,2)) = ψ ( x,0, x 3 ) = x ⋅ x 3 = x 4 .
     Можно предположить, что f ( x, y ) = x y +1 .
     Докажем последнюю формулу методом математической индукции по
переменной y .
1. Проверим формулу при y = 0 .
 f ( x,0) = x = x 0+1 , то есть при y = 0 формула верна.
2. Допустим, что предположение индукции верно при y = n , то есть, верна формула
     f ( x, n) = x n +1 .



                                                                  47

Страницы