Помогите разобраться с примитивно рекурсивными функциями..

[Marischa]

Нужно доказать примитивную рекурсивность сложения.
вот кое что я накопала, только не пойму как это доказывает рекурсивность....
sum(x,0)=x;
sum(x,y+1)=sum(x,y)+1.

[epros]

Marischa в сообщении #349071 писал(а):

Нужно доказать примитивную рекурсивность сложения.
вот кое что я накопала, только не пойму как это доказывает рекурсивность....
sum(x,0)=x;
sum(x,y+1)=sum(x,y)+1.

Достаём определение примитивно-рекурсивной функции и по пунктам проверяем...

[Marischa]

ну она должна быть получена из 0 и n+1...путем каких то там подстановок....

[epros]

Marischa в сообщении #349076 писал(а):

ну она должна быть получена из 0 и n+1...путем каких то там подстановок....

Любая примитивно рекурсивная функция может быть получена из базовых функций с помощью операторов ... каких?

[Marischa]

не знаю..

[epros]

Marischa в сообщении #349080 писал(а):

не знаю..

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

[Marischa]

Да пять раз прочитала Р.Петера...бесполезно..

[epros]

Вам нужны три базовые примитивно рекурсивные функции:
1) Функция следования (инкремента) $S(x)$
2) Функция $I_1^1(x) = x$
3) Функция $I_3^3(x,y,z) = z$

Из них с помощью операторов подстановки и примитивной рекурсии нужно записать две указанных Вами аксиомы сложения.

[Marischa]

epros в сообщении #349091 писал(а):

2) Функция $I_1^1(x) = x$
3) Функция $I_3^3(x,y,z) = z$

откуда это взялось? Есть какая-то табличка, где эти функции написаны?

[epros]

Marischa в сообщении #349096 писал(а):

epros в сообщении #349091 писал(а):

2) Функция $I_1^1(x) = x$
3) Функция $I_3^3(x,y,z) = z$

откуда это взялось? Есть какая-то табличка, где эти функции написаны?

Из определения примитивно рекурсивной функции. "Базовыми" примитивно рекурсивными функциями являются:
a) тождественный нуль;
б) функция инкремента $S(x)$;
в) каждая функция проекции $I_n^k(x_1, ... , x_n) = x_k$.

[Marischa]

Спасибо, попробую все собрать в кучу и разобраться.

[maxmatem]

Воспользуйтесь определением операции примитивной рекурсии. Рассмотрите функцию $\[\sigma (x;y) = x + y\]$.
Шаг №1. (естественное задание)
$\[ \left\{ \begin{gathered} \sigma (x;0) = x + 0 = x \hfill \\ \sigma (x;y + 1) = x + y + 1 \hfill \\ \end{gathered} \right. \]$
Шаг №2.(Через определение операции примитивной рекурсии)
$\[ \left\{ \begin{gathered} \sigma (x;0) = g^1 (x) \hfill \\ \sigma (x;y + 1) = h^3 (x;y;z) \hfill \\ \end{gathered} \right. \] $
Шаг №3
Вам осталось подобрать функции$ \[g^1 (x)\]$ и$ \[h^3 (x;y;z)\]$
(это надо делать смотря на естественное задание )
эти функции надо задать через элементарные, и вам их уже написали.

[Marischa]

у меня вообще по заданию,доказать, руководствуясь определением примитивно рекурсивной функции. Может совсем это не так делать?!

[maxmatem]

Посмотрите в моём сообщении на шаг №2.( для того чтобы воспользоваться определением примит.рек.ф-ии, надо представить её ч\з элементарные, чтобы написать её примит.рек. описание)

[Marischa]

спасибо, попробую