Рекурсивная функция

[maxmatem]

надо доказать, что функция $\[f(x;y) = {x^{y + 1}}\]$ -является рекурсивной функцией.
т.е надо доказать два факта:
1. $f(x;y)$ является частично рекурсивной функцией(ЧРФ).
2. $f(x;y)$ является всюду определенной.

рассмотрим первый пункт. для этого представим $f(x;y)$ в следующем виде
$\[f(x;y) = S({x^y};I_1^2(x;y),S(s;I_2^2(x;y)))\]$
Запишем частично рекурсивное описание функции $f(x;y)$ относительно совокупности$ \[\{ {x^y}\} \]$ а именно $\[{x^y},I_1^2,I_2^2,s,S(s;I_2^2),S({x^y};I_1^2,S(s;I_2^2))\]$ значит $f(x;y)$-ЧРФ относительно $ \[\{ {x^y}\} \]$.
и воспользуемся свойством, что если $f(x;y)$-ЧРФ относ. $ \[\{ {x^y}\} \]$
и каждая функция ЧРО, есть ЧРФ, то и $f(x;y)$-ЧРФ.
а как доказать что данная функция всюду определена? интуитивно то ясно что она везде определена(под "везде " понимается $\[\mathbb{N}\]$), но как это доказать строго?

$S$-оператор подстановки
$s$-оператор следования
ЧРФ-частично рекурсивная функция
ЧРО-частично рекурсивное описание

-- Пн мар 15, 2010 01:50:00 --

Я по-мойму додумался, т.к. функция - ПРФ, то она рекурсивная функция т.к. всякая ПРФ, есть ЧРФ и ПРФ всюду определена, значит функция рекурсивная. А как можно по другому???

[Профессор Снэйп]

$f_+(x,y) = x + y$, $f_\times(x,y) = x \cdot y$, $f_p(x,y) = x^y$, $s(x) = x+1$, $o(x) = 0$, $I^n_k(x_1,\ldots,x_k) = x_n$.

Если

$$ f(x_1, \ldots, x_k) = g(h_1(x_1, \ldots, x_k), \ldots, h_n(x_1, \ldots, x_k)), $$

то пишем $f = \mathcal{S}(g; h_1, \ldots, h_n)$. Если

$$ \left[ \begin{array}{lcl} f(x_1, \ldots, x_k, 0) &=& g(x_1, \ldots, x_k) \\ f(x_1, \ldots, x_k,t+1) &=& h(f(x_1, \ldots, x_k,t), t, x_1, \ldots, x_k) \end{array} \right. $$

то пишем $f = \mathcal{P}(g,h)$. Для решения задачи надо всего лишь осознать следующие факты:

$$ \begin{array}{lcl} f_+ &=& \mathcal{P}(I^1_1, \mathcal{S}(s; I^1_3)) \\ f_\times &=& \mathcal{P}(o, \mathcal{S}(f_+; I^1_3, I^3_3)) \\ f_p &=& \mathcal{P}(\mathcal{S}(s; o), \mathcal{S}(f_\times; I^1_3, I^3_3)) \\ f &=& \mathcal{S}(f_p; I^1_2, \mathcal{S}(s; I^2_2)) \end{array} $$

[Профессор Снэйп]

Или вместо последних двух строчек напрямую $f = \mathcal{P}(I_1^1, \mathcal{S}(f_\times; I_3^1, I_3^3))$.

[maxmatem]

Я определения эти знаю ! я спросил как всюду определенность доказать! один способ я придумал(но он работает только потому что данная функция ПРФ, а значит везде определенная), а если бы она была просто ЧРФ, и ПРФ-не является, то как доказать её всюду определенность?

[Xaositect]

maxmatem в сообщении #298013 писал(а):

если бы она была просто ЧРФ, и ПРФ-не является, то как доказать её всюду определенность?

Надо для каждого $\mu$-оператора в описании функции доказать, что его значение всегда определено.

[maxmatem]

спасибо!

[Профессор Снэйп]

Учитывая, что ни одного $\mu$-оператора в определении функции не присутствует, замечание более чем ценное

Вы уж определитесь, что вам нужно.

[Xaositect]

Профессор Снэйп в сообщении #298162 писал(а):

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

Вопрос был про общий случай.

[Профессор Снэйп]

Да я понял про общий случай

Согласитесь, топегстартер ведёт себя довольно странно. Понятно, что список очевидных свойств какой-нибудь данной функции зависит от того, в каком виде эта функция задана. Может и можно (если сильно исхитриться) как-нибудь придумать задачу, в которой бы функция задавалась через $\mu$-оператор, а выяснить бы требовалось, является эта функция частичной или тотальной. Но обычно всё происходит наоборот. Чаще всего функции дают в таком виде, что их область определения сразу ясна, а потом требуют выразить эти функции через базисные с помощью суперпозиций, примитивных рекурсий и минимизацией. А тут очень-очень редко встречающийся и даже не сформулированный "общий случай" Если бы дело было на экзамене, я бы первым моментом заподозрил, что человек в предмете просто ни бум-бум и даже не понимает, о чём речь.

Не, ну в самом деле, то, что $f(x,y) = x^{y+1}$ выражается суперпозициями и примитивными рекурсиями из басисных автору очевидно. А то, что $f(x,y)$ определено при всех $x,y \in \mathbb{N}$, очевидным почему-то не является. Фантастика! Это как же, интересно, всюду определённость таких функций надо доказывать?

[maxmatem]

Профессор Снейп!
я прекрасно понимаю, что данная функция всюду определена т.е на $\[\mathbb{N}\]$. я задал вопрос только лишь ,потому что не зря же в определении рекурсивной функции, имеется пункт о том что функция должна быть всюду определенной!(вот и задумался как доказать!)

P.S. честно говоря ваше высказывание о моём понимании предмета, очень обидное и несправедливое!

[Xaositect]

maxmatem в сообщении #298378 писал(а):

P.S. честно говоря ваше высказывание о моём понимании предмета, очень обидное и несправедливое!

У меня вот сложилось представление не такое, что Вы чего-то не понимаете, а такое, что Вы зачем-то пытаетесь все представить слишком формально. Скажем, после того, как написано $\begin{cases}x\cdot 0 = 0\\ x\cdot(y+1) = x\cdot y + x\end{cases}$ абсолютно не обязательно писать длинную строчку для описания функции $\cdot$ через базовые функции и операторы - и так понятно, что она прим.-рек. А если это требования преподавателя, то могу Вам только посочувствовать.

[maxmatem]

да вы правы! спасибо что правильно поняли меня! всё теперь по данной задаче у меня вопросов нет!

[Профессор Снэйп]

maxmatem в сообщении #298378 писал(а):

прекрасно понимаю, что данная функция всюду определена

Мне остаётся лишь процитировать Ваше же сообщение.

maxmatem в сообщении #298013 писал(а):

я спросил как всюду определенность доказать!

-- Ср мар 17, 2010 10:21:01 --

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

А если это требования преподавателя, то могу Вам только посочувствовать.

Ну это Вы зря

Я вот когда веду семинары по этому предмету, то на большинстве семинаров удовлетворяюсь "неформальным" заданием в духе приведённого Вами выше. Но пару семинаров в семестре посвящаю именно формальной записи различных функций через базисные и операторы. Чтоб родилось понимание. А то ведь потом на экзамене... Спросишь, что такое примитивно рекурсивная функция, он оттарабанит: "Функция называется примитивно рекурсивной, если она получается из базисных суперпозициями и примитивными рекурсиями". Спросишь, является ли умножение примитивно рекурсивной функцией, скажет, что да. Потом спрашиваешь, из каких именно базисных функций и какими операторами получается умножение и всё, ступор

Если формальную запись вообще выкинуть из рассмотрения или всего лишь всколзь упомянуть на лекции, то народ даже не понимает, зачем в число базисных включают проекции $I_k^n$. Они ведь в неформальной записи никогда не используются!

[Xaositect]

У нас про это было просто сказано несколько минут на лекции с простыми примерами расписанными, то же умножение, вроде, не помню уже конкретно.

[Профессор Снэйп]

Xaositect, поймёте, когда сами начнёте преподавать теорию вычислимости. Особенно первокурсникам... Им надо это дело со всех сторон обсасывать, и формально, и неформально, поскольку просто так они не врубаются. Слишком далеко от привычной им школьной математики.