2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Рекурсия
Сообщение16.02.2014, 23:03 
Заслуженный участник
Аватара пользователя


06/10/08
6422
MestnyBomzh в сообщении #827420 писал(а):
Я так понимаю, что тут дело в нуле в функции $ f(x_1,....x_n,0)$, а я вместо нуля туда единицу поставил.
Угу. Напишите, какие должны быть функции $g$ и $h$, чтобы получилось умножение.

MestnyBomzh в сообщении #827420 писал(а):
И как я понимаю, примитивная рекурсия обеспечивает нам индуктивность, так?
А индуктивность - это что еще такое? Это что-то из электродинамики.

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


17/10/13
790
Деревня
Так, ну очевидно, что $g=0$(функция, возвращающая ноль, так ведь она называется?), т.е. $f(x,0)=0$ Теперь $h$; $f(x,y+1)=h(x,y,f(x,y))$ Я думаю, что $h=f(x,y)+x$

-- 17.02.2014, 00:20 --

Xaositect в сообщении #827427 писал(а):
А индуктивность - это что еще такое? Это что-то из электродинамики.

Я имел в виду индукцию :D В физику лезть не смею

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


27/04/09
28128
MestnyBomzh в сообщении #827436 писал(а):
Я думаю, что $h=f(x,y)+x$
Такая запись неоднозначна. Вы ведь хотели сказать «$h(a,b,c) = c+a$»?

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


06/10/08
6422
У arseniiv правильное замечание.

А про индукцию не понимаю. индукция - это способ доказательства.

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


17/10/13
790
Деревня
То есть вот так: $h(x,y,f(x,y))=f(x,y)+x$ А база индукции в нашем случае это $f(x,0)=0$?

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


06/10/08
6422
MestnyBomzh в сообщении #827443 писал(а):
А база индукции в нашем случае это $f(x,0)=0$?
База индукции для доказательства чего?

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


17/10/13
790
Деревня
Для доказательства того, что функция примитивно-рекурсивна

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


06/10/08
6422
Вспоминаем определение примитивно-рекурсивной функции. Если функция $f$ получена из примитивно-рекурсивных $g$ и $h$ с помощью примитивной рекурсии, то она примитивно рекурсивна. Мы смогли получить умножение таким образом? Смогли. Значит, умножение примитивно рекурсивно.

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


17/10/13
790
Деревня
Понял, спасибо. А можно еще вопрос:чем отличаются примитивно-рекурсивная функция и рекурсивная функция?

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


06/10/08
6422
MestnyBomzh в сообщении #827482 писал(а):
Понял, спасибо. А можно еще вопрос:чем отличаются примитивно-рекурсивная функция и рекурсивная функция?
Определение примитивно рекурсивной функции Вы знаете. Найдите теперь определение рекурсивной функции и сравните, чем они отличаются.

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


06/04/10
3152
MestnyBomzh в сообщении #827482 писал(а):
вопрос:чем отличаются примитивно-рекурсивная функция и рекурсивная функция?

Содержательно - функция рекурсивна, если существует вычисляющий её алгоритм (и таких алгоритмов всегда - тьма :wink: ).
Примитивно-рекурсивные - те, что вычисляются алгоритмами некоторого узкого класса. В частности, эти алгоритмы всегда заканчивают работу.

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


17/10/13
790
Деревня
nikvic
Я тут поискал, нашел только примитивную и частичную рекурсии. Предположу, что рекурсия разбивается на два подраздела: примитивная рекурсия и частичная... То есть, если спрашивается:"Рекурсивна ли функция", то если она примитивно-рекурсивна или частично-рекурсивна=>она рекурсивна?

 Профиль  
                  
 
 Re: Рекурсия
Сообщение17.02.2014, 14:48 
Заслуженный участник


27/04/09
28128
Всякая примитивно рекурсивная частично рекурсивна, и это прямо по определению. Частично рекурсивная функция не обязана быть определённой не на всех значениях аргументов, это не противоречит определению.

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


17/10/13
790
Деревня
arseniiv
так я же ничего не говорил про неопределенность частично-рекурсивной функции

 Профиль  
                  
 
 Re: Рекурсия
Сообщение17.02.2014, 17:08 
Заслуженный участник


09/08/09
3438
С.Петербург
MestnyBomzh в сообщении #827678 писал(а):
Предположу, что рекурсия разбивается на два подраздела: примитивная рекурсия и частичная...
MestnyBomzh, английский оригинал названия "частичнорекурсивная функция" -- "partial recursive function", т. е. "частичная рекурсивная функция". Поэтому, строго говоря, это не рекурсия "частичная", а функция. Другими словами, рекурсивная функция, определенная, возможно, не всюду. Ну а "общерекурсивная функция" (general recursive function) - это всюду определенная рекурсивная функция.

По крайней мере, по Роджерсу так.
(Х. Роджерс. Теория рекурсивных функций и эффективная вычислимость)

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

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



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

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


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

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