Рекурсивные функции

[Sverest]

В методичке есть пример:

Пусть функция $f(y,x)$ задана равенствами: (почему $y$ левее $x$?)

$\begin{cases} f(0,x)=x,\\ f(y+1,x)=f(y,x)+1.\\ \end{cases}$

(в оригинале фигурная скобка была справа)

Здесь функция $\phi(x)=x$, a $\psi (x,y,z)=y+1$ (как это определили?)

Вычислим значение функции $f(y,x)$ при $y=5$, $x=2$

Т.к. $f(0,2)=\phi(2)=2$, то из второго равенства последовательно имеем:

$\begin{cases} f( 1,2 )=\phi(0 ,2 ,2 )= 2 + 1 = 3 \\ f(2 ,2 )=\phi( 1, 3 , 2 )= 3 + 1 =4 \\ f( 3,2 )=\phi( 2, 4 , 2 )= 4 + 1 =5 \\ f( 4,2 )=\phi( 3, 5 , 2 )= 5 + 1 =6 \\ f( 5,2 )=\phi( 4, 6 , 2 )= 6 +1 =7 \\ \end{cases} $

Нетрудно показать, что $f(y,x)=y+x$

Действительно $f(y+z,x)=f(y,x)+z$.

Полагая в этом равенстве $y=0$ получим $f(z,x)=f(0,x)+z$ или $f(z,x)=x+z$

(как это сделали?)

[Sverest]

Эти функции как то подставляются одна в другую?

[Sverest]

здесь же $\phi(z,y,x)$ идет а не $\phi(x,y,z)$

[Sonic86]

Sverest в сообщении #516820 писал(а):

Здесь функция $\phi(x)=x$, a $\psi (x,y,z)=y+1$ (как это определили?)

Видимо, это определения $\phi$ и $\psi$.

Sverest в сообщении #516820 писал(а):

(почему $y$ левее $x$?)

Если для $x,y$ область значений одинаковая, то по идее имя буквы вообще роли не играет.

Sverest в сообщении #516820 писал(а):

Действительно $f(y+z,x)=f(y,x)+z$.
Полагая в этом равенстве $y=0$ получим $f(z,x)=f(0,x)+z$ или $f(z,x)=x+z$
(как это сделали?)

Сначала по индукции, а потом описанная подстановка.

[Sverest]

откуда $z$ появился его же не было в начале

[Sonic86]

Sverest в сообщении #527973 писал(а):

откуда $z$ появился его же не было в начале

да произвольная же переменная.
Нам дано $f(y+1,x)=f(y,x)+1$. Чему равно $f(y+2,x), f(y+3,x), ... , f(y+z,x)$?

[Sverest]

$f( 1,2 )=\phi(0 ,2 ,2 )$
откуда получили цифры $0,0,2$ ?

[Sverest]

то есть $\phi(0,2,2)$
$y=0$ это начальный?
$x=2$ задано
а почему $z=2$

[Sonic86]

Sverest в сообщении #528211 писал(а):

$f( 1,2 )=\phi(0 ,2 ,2 )$
откуда получили цифры $0,0,2$ ?

Ну не цифры, а числа. А у Вас $\phi$ в 1-м посте объявлена как $\phi (x)=x$, т.е. символ $\phi(0,2,2)$ некорректен. От 3-х переменных была функция $\psi$. Для нее соотношение неверно?

[Sverest]

Да $\psi$
меня интересует по какому алгоритму получаются $(0,2,2)$ из $(1,2)$

[Sonic86]

Похоже на то, что контекст где-то потерян. Естественно $(2,1)$ из $(0,2,2)$ однозначно не вычисляется.

[Sverest]

Sonic86 в сообщении #528411 писал(а):

Похоже на то, что контекст где-то потерян. Естественно $(2,1)$ из $(0,2,2)$ однозначно не вычисляется.

вот здесь мне непонятно откуда взялись$ (0 ,2 ,2 )$ эти числа
$f( 1,2 )=\psi(0 ,2 ,2 )= 2 + 1 = 3 $

[Sonic86]

Ну я понял, что Вам непонятно. Мне тоже непонятно. Вполне возможно, что они даже отфонарны - без контекста так трудно сказать.

[Sverest]

В начале темы же контекст есть

[cyb12]

Здесь же функция $f(y,x)=g(x,y)$ задается по определению операции примитивной рекурсии, то есть:
$g(x,0) = \varphi(x),$ $g(x,y+1) = \psi(x,y,g(x,y)),$
где функции $\varphi$ и $\psi$ должны быть примитивно-рекурсивными.

$y$ левее $x$ - почему бы и нет))

Если у нас задана система, которую Вы привели, то легко доказать примитивную рекурсивность $g$ , сказав, что $\varphi(x)=x,$ $\psi(x,y,z)=z+1$

Как найти тогда $f(1,2) = g(2,1)$? Так же, как уже сказали, то есть взять $g(2,0+1)=\psi(2,0,g(2,0))=\psi(2,0,2)=3.$ С точностью до перепутывания порядка переменных все вроде ок...