Рекурсия

[MestnyBomzh]

Можно ли утверждать, что умножение примитивно рекурсивно, потому что $f_\times (x,0)=0,f_\times (x,1)=x=I^1_1x$ и $f_\times (x,y+1)=f_\times (x,y)+x=f_+(f_\times (x,y),I^1_1)$?(подразумевается, что уже доказано, что сложение примитивно рекурсивно)

[Deggial]

Приведите попытки решения, укажите конкретные затруднения

[MestnyBomzh]

Deggial
Задача была такой:докажите, что умножение примитивно рекурсивно, я привел свое решение, но не уверен в нем

[Deggial]

MestnyBomzh в сообщении #827277 писал(а):

Задача была такой:докажите, что умножение примитивно рекурсивно

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

[Xaositect]

Идея правильная, но равенства у Вас очень странно записаны.

[Nemiroff]

Deggial в сообщении #827289 писал(а):

Доказательство - это последовательность логических рассуждений, выводов из посылок. У Вас явных рассуждений нет, т.е. доказательства нет.

Я бы сказал, что в некоторых случаях (от строгости проверки зависит) это может сойти за доказательство.
MestnyBomzh, вам ещё должно быть известно, что функция, возвращающая нуль — примитивно рекурсивная.
$f_\times (x,1)=x=I^1_1x$ — вот этот кусок зачем?

MestnyBomzh в сообщении #827169 писал(а):

$f_\times (x,y+1)=f_\times (x,y)+x=f_+(f_\times (x,y),I^1_1)$

Запишите-ка схему примитивной рекурсии.

[MestnyBomzh]

Nemiroff в сообщении #827296 писал(а):

$f_\times (x,1)=x=I^1_1x$ — вот этот кусок зачем?

Это чтобы определить $x$;

Nemiroff в сообщении #827296 писал(а):

MestnyBomzh в сообщении #827169
писал(а):
$f_\times (x,y+1)=f_\times (x,y)+x=f_+(f_\times (x,y),I^1_1)$
Запишите-ка схему примитивной рекурсии.

К $f_\times (x,y)$ прибавляется тот самый икс, который я определил выше

[Nemiroff]

MestnyBomzh в сообщении #827311 писал(а):

Это чтобы определить $x$;

Мда.

MestnyBomzh в сообщении #827311 писал(а):

К $f_\times (x,y)$ прибавляется тот самый икс, который я определил выше

Определение схемы примитивной рекурсии запишите.

[Xaositect]

А вот теперь похоже, что Вы не понимаете, как доказывать прим-рекурсивность.

Запишите, пожалуйста, определение примитивно-рекурсивной функции.

[MestnyBomzh]

Xaositect в сообщении #827313 писал(а):

Запишите, пожалуйста, определение примитивно-рекурсивной функции

такие функции, которые могут быть выражены через 1)константы 2)переменные 3)$x+1$ 4)$I^m_n$, ставящая в соответствие $x_m$ для каждого из наборов $x_1....x_n$

Nemiroff в сообщении #827312 писал(а):

Определение схемы примитивной рекурсии запишите

А вот что это такое я не знаю

[Nemiroff]

MestnyBomzh в сообщении #827328 писал(а):

такие функции, которые могут быть выражены через 1)константы 2)переменные 3)$x+1$ 4)$I^m_n$

Что тогда значит "могут быть выражены"?

[MestnyBomzh]

Nemiroff в сообщении #827330 писал(а):

Что тогда значит "могут быть выражены"?

Если при помощи суперпозиции этих базисных опций можем выразить функцию, то есть, установить равенство, то она примитивно-рекурсивная

[Xaositect]

MestnyBomzh в сообщении #827334 писал(а):

Если при помощи суперпозиции этих базисных опций можем выразить функцию, то есть, установить равенство, то она примитивно-рекурсивная

Неверно. Ищите определение в учебнике. Там не только суперпозиция, а еще и вышеупомянутая схема примитивной рекурсии.

[Nemiroff]

MestnyBomzh в сообщении #827334 писал(а):

Если при помощи суперпозиции этих базисных опций можем выразить функцию, то есть, установить равенство, то она примитивно-рекурсивная

Во-первых, это неверно.
Во-вторых, пусть это верно — тогда вы ничего не доказали. У вас ваша суперпозиция для разных аргументов разная. А кроме суперпозиции вы сами сказали, что ничего использовать нельзя.

[MestnyBomzh]

Функция называется примитивно-рекурсивной, если она может быть получена из константы $0$, функции $x'$ и функций $I^n_m$ с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии (та самая схема рекурсии). Теперь схема рекурсии: оператор примитивной рекурсии $R_n$ определяет $n+1$-местную функцию $f$ через $n$-местную функцию $g$ и $n+2$-местную функцию $h$ следующим образом:

$$\begin{cases} f(x_1,....x_n,0)=g(x_1,....x_n);\\ f(x_1,....x_n,y+1)=h(x_1,.....,x_n,y,f(x_1,....x_n,y)). \end{cases}$$

Я так понимаю, что тут дело в нуле в функции $ f(x_1,....x_n,0)$, а я вместо нуля туда единицу поставил. И как я понимаю, примитивная рекурсия обеспечивает нам индуктивность, так?