2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Рекурсия
Сообщение16.02.2014, 14:40 
Аватара пользователя


17/10/13
726
Деревня
Можно ли утверждать, что умножение примитивно рекурсивно, потому что $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)$?(подразумевается, что уже доказано, что сложение примитивно рекурсивно)

 Профиль  
                  
 
 Re: Рекурсия
Сообщение16.02.2014, 18:26 
Супермодератор
Аватара пользователя


20/11/12
5698
 i  Приведите попытки решения, укажите конкретные затруднения

 Профиль  
                  
 
 Re: Рекурсия
Сообщение16.02.2014, 18:32 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение16.02.2014, 18:48 
Супермодератор
Аватара пользователя


20/11/12
5698
MestnyBomzh в сообщении #827277 писал(а):
Задача была такой:докажите, что умножение примитивно рекурсивно

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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение16.02.2014, 18:50 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение16.02.2014, 18:58 
Заслуженный участник
Аватара пользователя


20/07/09
3883
МФТИ ФУПМ
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)$

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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение16.02.2014, 19:33 
Аватара пользователя


17/10/13
726
Деревня
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)$ прибавляется тот самый икс, который я определил выше

 Профиль  
                  
 
 Re: Рекурсия
Сообщение16.02.2014, 19:36 
Заслуженный участник
Аватара пользователя


20/07/09
3883
МФТИ ФУПМ
MestnyBomzh в сообщении #827311 писал(а):
Это чтобы определить $x$;
Мда.
MestnyBomzh в сообщении #827311 писал(а):
К $f_\times (x,y)$ прибавляется тот самый икс, который я определил выше
Определение схемы примитивной рекурсии запишите.

 Профиль  
                  
 
 Re: Рекурсия
Сообщение16.02.2014, 19:36 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение16.02.2014, 19:53 
Аватара пользователя


17/10/13
726
Деревня
Xaositect в сообщении #827313 писал(а):
Запишите, пожалуйста, определение примитивно-рекурсивной функции

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

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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение16.02.2014, 19:54 
Заслуженный участник
Аватара пользователя


20/07/09
3883
МФТИ ФУПМ
MestnyBomzh в сообщении #827328 писал(а):
такие функции, которые могут быть выражены через 1)константы 2)переменные 3)$x+1$ 4)$I^m_n$

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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение16.02.2014, 19:57 
Аватара пользователя


17/10/13
726
Деревня
Nemiroff в сообщении #827330 писал(а):
Что тогда значит "могут быть выражены"?

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

 Профиль  
                  
 
 Re: Рекурсия
Сообщение16.02.2014, 19:58 
Заслуженный участник
Аватара пользователя


06/10/08
6027
MestnyBomzh в сообщении #827334 писал(а):
Если при помощи суперпозиции этих базисных опций можем выразить функцию, то есть, установить равенство, то она примитивно-рекурсивная
Неверно. Ищите определение в учебнике. Там не только суперпозиция, а еще и вышеупомянутая схема примитивной рекурсии.

 Профиль  
                  
 
 Re: Рекурсия
Сообщение16.02.2014, 20:01 
Заслуженный участник
Аватара пользователя


20/07/09
3883
МФТИ ФУПМ
MestnyBomzh в сообщении #827334 писал(а):
Если при помощи суперпозиции этих базисных опций можем выразить функцию, то есть, установить равенство, то она примитивно-рекурсивная
Во-первых, это неверно.
Во-вторых, пусть это верно — тогда вы ничего не доказали. У вас ваша суперпозиция для разных аргументов разная. А кроме суперпозиции вы сами сказали, что ничего использовать нельзя.

 Профиль  
                  
 
 Re: Рекурсия
Сообщение16.02.2014, 22:57 
Аватара пользователя


17/10/13
726
Деревня
Функция называется примитивно-рекурсивной, если она может быть получена из константы $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)$, а я вместо нуля туда единицу поставил. И как я понимаю, примитивная рекурсия обеспечивает нам индуктивность, так?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 44 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group