Является ли функция примитивно рекурсивной?

[TypucT]

Простая иллюстрация для Nxx без "завуалированных аргументов":
Пусть функции $a(x)$ и $b(x)$ примитивно рекурсивные. Пусть функция $f(x)$ есть одна из $a(x)$ и $b(x)$ (любая). Тогда функция $f(x)$ примитивно рекурсивная.

Xaositect писал(а):

А если ночью 18.02.2009 Караганду переименуют, или вогоны сотрут с Землю с лица Галактики?

В этом случае высказывание "19.02.2009 в Караганде будет дождь" ложно

[Nxx]

Цитата:

Пусть функция $f(x)$ есть одна из $a(x)$ и $b(x)$ (любая).

Случайным образом? Или когда ей как нравится? Я четко видел в определении функции $f(x)$ слово "если" и фигурную скобку. Или мне показалось? Или это не было частью определения функции $f(x)$?

Если это не относилоcь к определению $f(x)$, а было чемто посторонним, то да.

Пусть функция f(x) дает вообще любой ответ, ни от чего не зависящий. f(x) - примитивно рекурсивная?

[AD]

$(f=a\Rightarrow f\in X)\&(f=b\Rightarrow f\in X)\to ((f=a\vee f=b)\Rightarrow f\in X)$

[Nxx]

Цитата:

$(f=a\Rightarrow f\in X)\&(f=b\Rightarrow f\in X)\to ((f=a\vee f=b)\Rightarrow f\in X)$

Что вы считаете $a$ и что - $b$?
Может быть, я прочитал неверно, и вместо

$$ h(x) \equiv \left\{ \begin{array}{сl} 2, & $если гипотеза Гольдбаха истинна$,\\ 1, & $если гипотеза Гольдбаха ложна$. \end{array} \right. $$

там было

$$ \begin{array}{сl}$если гипотеза Гольдбаха истинна$, & h(x) \equiv 1,\\$если гипотеза Гольдбаха ложна$, & h(x)\equiv 2. \end{array} \right? $$

Условие "если" является частью определения функции или нет? Если является, то $h(x)$ - не обязательно примитивно-рекурсивная, если не является, то $h(x)$ не имеет отношения к гипотезе Гольдбаха.

[AD]

$a$ - тождественная единица, $b$ - тождественная двойка. В условии, фактически, сказано, что $f=a \vee f=b$. Я это так понимаю. То есть не является частью определения, и тогда всё понятно.

Хотя давайте я все-таки лучше послушаю - не стоит мне лезть в то, что не знаю

[Nxx]

AD писал(а):

$a$ - тождественная единица, $b$ - тождественная двойка. В условии, фактически, сказано, что $f=a \vee f=b$. Я это так понимаю. То есть не является частью определения, и тогда всё понятно.

А, ну если тут такая обманка, и нижеприведенное выражение не является определением функции,

$$ h(x) = \left\{ \begin{array}{сl} 2, & $если гипотеза Гольдбаха истинна$,\\ 1, & $если гипотеза Гольдбаха ложна$. \end{array} \right. $$

то да, $h(x)$ - примитивно-рекурсивная, так как никаких проверок условий и вычислений гипотез Гольдбаха не содержит. Она просто либо 1, либо 2. Только надо понимать, что в этом случае вышеприведенное выражение не является определением такой функции.

Добавлено спустя 5 минут 43 секунды:

$$ y(x) = \left\{ \begin{array}{сl} 1, & $ если x>0$,\\ 0, & $ если x\le 0$. \end{array} \right. $$

$$ \text{если } z>0, \text{то } y(x) \equiv 1, \text{если } z\le 0, \text{то } y(x) \equiv 0 $$

Чувствуете разницу? Во втором случае, y - константа, в первом - нет.

[AD]

Nxx в сообщении #187527 писал(а):

Чувствуете разницу? Во втором случае, y - константа, в первом - нет.

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

[Dandan]

маткиб писал(а):

Рекурсивность - это свойство именно функции, а не описания. И не нужно это путать с программистским понятием рекурсивности (где функция - это фрагмент программы, а рекурсивная - это которая содержит вызов себя). По крайней мере, у программистов такого понятия как "примитивная рекурсивность" просто нет.

Я ничего не путаю, я вам пытаюсь объяснить суть понятия рекурсивности функции. Следует понимать так, что рекурсивно описание функции. И если функция имеет как минимум одно конкретное рекурсивное описание - тогда она рекурсивна. Вы, конечно, можете настаивать на своём, но это не соответствует действительности.

[TypucT]

Nxx писал(а):

Цитата:

Пусть функция $f(x)$ есть одна из $a(x)$ и $b(x)$ (любая).

Случайным образом? Или когда ей как нравится?

Да, именно так. Слово "любая" означает любая, какая угодно, выбранная произвольным образом. Акт выбора одного произвольного элемента из двух данных нетривиальная операция?

Nxx писал(а):

Я четко видел в определении функции $f(x)$ слово "если" и фигурную скобку. Или мне показалось? Или это не было частью определения функции $f(x)$?
Если это не относилоcь к определению $f(x)$, а было чемто посторонним, то да.

Условие приведено как есть у Мендельсона. Дополнительных указаний или уточнений там нет.

Nxx, выражайтесь, пожалуйста, точнее. В частности, неясно, что такое "функция дает ответ", "функции нравится", "функция не имеет отношения к", "функция ничего не знает про", "функция не сможет вычислить", "передать в качестве аргумента в функцию", "в функцию вводится параметр" и т.п.

PS
Завтра функция $r(x)$ MaximKat станет примитивно рекурсивной!

[Nxx]

Цитата:

Да, именно так. Слово "любая" означает любая, какая угодно, выбранная произвольным образом. Акт выбора одного произвольного элемента из двух данных нетривиальная операция?

Понимаете ли, функция выбора, разрешенная для примитивно-рекурсивных функций выглядит так: $I_n^m(x_1,...,x_n)=x_m$. В данном случае $n=2, x_1=1,x_2=2$. А вот m неизвестно. Если m вычисляется внутри функции, то она вероятно, не примитивно-рекурсивная. Если m передается в функцию h(x) в качестве пераметра, то она, очевидно, примитивно-рекурсивная. Операция случайного выбора или "выбора произвольным образом" или "выбора когда ей как нравится" не является разрешенным элементом для примитивно-рекурсивных функций.

[AD]

Nxx, давайте по-человечески. Вы предлагаете формулировку задачи, не соответствующую моему пониманию - ну так сформулируйте, пожалуйста, эту формулировку!

Укажите область определения функции для начала.

[TypucT]

Nxx писал(а):

Операция случайного выбора или "выбора произвольным образом" или "выбора когда ей как нравится" не является разрешенным элементом для примитивно-рекурсивных функций.

Извините, не знал что Nxx примитивно рекурсивная функция

[Nxx]

TypucT писал(а):

Nxx писал(а):

Операция случайного выбора или "выбора произвольным образом" или "выбора когда ей как нравится" не является разрешенным элементом для примитивно-рекурсивных функций.

Извините, не знал что Nxx примитивно рекурсивная функция

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

[TypucT]

Повторюсь: операция выбора может быть любой (в том числе - нерекурсивной). Свойства выбираемого элемента от этого не изменяются.

Вы смешиваете доказательство с тем, что мы доказываем.

И еще одно. Для определения примитивной рекурсивности не обязательно вычислять значение функции. Вот простой пример: Пусть функция $f(x)$ примитивно рекурсивная. Значит, $f(x)$ примитивно рекурсивная функция.

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

Существует столько интересных задач про примитивно рекурсивные функции, а тут какую-то х..ню обсуждают! Обидно