Рекурсия

[Xaositect]

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

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

Угу. Напишите, какие должны быть функции $g$ и $h$, чтобы получилось умножение.

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

И как я понимаю, примитивная рекурсия обеспечивает нам индуктивность, так?

А индуктивность - это что еще такое? Это что-то из электродинамики.

[MestnyBomzh]

Так, ну очевидно, что $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 писал(а):

А индуктивность - это что еще такое? Это что-то из электродинамики.

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

[arseniiv]

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

Я думаю, что $h=f(x,y)+x$

Такая запись неоднозначна. Вы ведь хотели сказать «$h(a,b,c) = c+a$»?

[Xaositect]

У arseniiv правильное замечание.

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

[MestnyBomzh]

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

[Xaositect]

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

А база индукции в нашем случае это $f(x,0)=0$?

База индукции для доказательства чего?

[MestnyBomzh]

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

[Xaositect]

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

[MestnyBomzh]

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

[Xaositect]

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

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

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

[nikvic]

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

вопрос:чем отличаются примитивно-рекурсивная функция и рекурсивная функция?

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

[MestnyBomzh]

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

[arseniiv]

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

[MestnyBomzh]

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

[Maslov]

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

Предположу, что рекурсия разбивается на два подраздела: примитивная рекурсия и частичная...

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

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