2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3  След.
 
 Re: Рекурсия
Сообщение16.02.2014, 23:03 
Аватара пользователя
MestnyBomzh в сообщении #827420 писал(а):
Я так понимаю, что тут дело в нуле в функции $ f(x_1,....x_n,0)$, а я вместо нуля туда единицу поставил.
Угу. Напишите, какие должны быть функции $g$ и $h$, чтобы получилось умножение.

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

 
 
 
 Re: Рекурсия
Сообщение16.02.2014, 23:19 
Аватара пользователя
Так, ну очевидно, что $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 
MestnyBomzh в сообщении #827436 писал(а):
Я думаю, что $h=f(x,y)+x$
Такая запись неоднозначна. Вы ведь хотели сказать «$h(a,b,c) = c+a$»?

 
 
 
 Re: Рекурсия
Сообщение16.02.2014, 23:25 
Аватара пользователя
У arseniiv правильное замечание.

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

 
 
 
 Re: Рекурсия
Сообщение16.02.2014, 23:27 
Аватара пользователя
То есть вот так: $h(x,y,f(x,y))=f(x,y)+x$ А база индукции в нашем случае это $f(x,0)=0$?

 
 
 
 Re: Рекурсия
Сообщение16.02.2014, 23:53 
Аватара пользователя
MestnyBomzh в сообщении #827443 писал(а):
А база индукции в нашем случае это $f(x,0)=0$?
База индукции для доказательства чего?

 
 
 
 Re: Рекурсия
Сообщение17.02.2014, 00:00 
Аватара пользователя
Для доказательства того, что функция примитивно-рекурсивна

 
 
 
 Re: Рекурсия
Сообщение17.02.2014, 00:03 
Аватара пользователя
Вспоминаем определение примитивно-рекурсивной функции. Если функция $f$ получена из примитивно-рекурсивных $g$ и $h$ с помощью примитивной рекурсии, то она примитивно рекурсивна. Мы смогли получить умножение таким образом? Смогли. Значит, умножение примитивно рекурсивно.

 
 
 
 Re: Рекурсия
Сообщение17.02.2014, 00:22 
Аватара пользователя
Понял, спасибо. А можно еще вопрос:чем отличаются примитивно-рекурсивная функция и рекурсивная функция?

 
 
 
 Re: Рекурсия
Сообщение17.02.2014, 00:30 
Аватара пользователя
MestnyBomzh в сообщении #827482 писал(а):
Понял, спасибо. А можно еще вопрос:чем отличаются примитивно-рекурсивная функция и рекурсивная функция?
Определение примитивно рекурсивной функции Вы знаете. Найдите теперь определение рекурсивной функции и сравните, чем они отличаются.

 
 
 
 Re: Рекурсия
Сообщение17.02.2014, 14:21 
Аватара пользователя
MestnyBomzh в сообщении #827482 писал(а):
вопрос:чем отличаются примитивно-рекурсивная функция и рекурсивная функция?

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

 
 
 
 Re: Рекурсия
Сообщение17.02.2014, 14:33 
Аватара пользователя
nikvic
Я тут поискал, нашел только примитивную и частичную рекурсии. Предположу, что рекурсия разбивается на два подраздела: примитивная рекурсия и частичная... То есть, если спрашивается:"Рекурсивна ли функция", то если она примитивно-рекурсивна или частично-рекурсивна=>она рекурсивна?

 
 
 
 Re: Рекурсия
Сообщение17.02.2014, 14:48 
Всякая примитивно рекурсивная частично рекурсивна, и это прямо по определению. Частично рекурсивная функция не обязана быть определённой не на всех значениях аргументов, это не противоречит определению.

 
 
 
 Re: Рекурсия
Сообщение17.02.2014, 15:33 
Аватара пользователя
arseniiv
так я же ничего не говорил про неопределенность частично-рекурсивной функции

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

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

 
 
 [ Сообщений: 44 ]  На страницу Пред.  1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group