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

[Nxx]

Цитата:

Нет в определении функции никакого "закона"!

Откройте любой учебник и прочитайте определение функции.

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

TypucT писал(а):

Профессор Снэйп писал(а):

TypucT писал(а):

Профессор Снэйп писал(а):

В классической логике можно, в конструктивистской нельзя И даже не совсем так: в классической логике можно доказать, что $h \in S$, а в конструктивистской нельзя даже доказать, что существует функция $h$, удовлетворяющая данному определению.

Докажите.

Что именно доказать: то, что в классической можно или то, что в конструктивистской нельзя?

Конечно же и то и другое.

Насчёт первого --- тривиально. В классической логике доказуемо $\Gamma \vee \neg \Gamma$. Далее, имеем гипотезы $\Gamma \rightarrow h \in S$ и $\neg \Gamma \rightarrow h \in S$. Из этих гипотез и $\Gamma \vee \neg \Gamma$ получаем (по соответствующей аксиоме, если исчисление, в котором мы работаем, гильбертовского типа, или правилу вывода, если секвенциального) $h \in S$.

Со вторым сложнее. Конструктивизм вообще относится к числу мало известных широкой публике вещей, и я с ним глобоко тоже не знаком. Почитайте статьи Маркова и Нагорного. Если интересно, на марковские статьи могу дать ссылки, а ссылки на статьи Нагорного есть в них. У Маркова всё больше общий трёп, а у Нагорного уже конкретика.

[Nxx]

Цитата:

Пусть для любого $x$ значение $f(x)$ равно $2+2$, если гипотеза Гольдбаха верна, и $f(x) = 2 \cdot 2$, если она не верна. Поскольку такое определение функции $f(x) \equiv 4$ содержит высказывание, которое, возможно, не доказуемо и не опровергаемо, то эта функция, возможно, алгоритмически не вычислима. Не так ли, уважаемый Nxx?

Зависит от того, допускает ли теория существование невычислимых выражений (которые, очевидно, функциями в любом случае, не являются). Но функция, если теория позволяет, может содержать невычислимое выражение, если от него не зависит результат функции.

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

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

Nxx писал(а):

Профессор Снэйп писал(а):

Где и в каком месте я говорил о функции, в которой есть "стрелка"? Процитируйте.

Пожалуйста:

Цитата:

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

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

Стрелка присутсвует в определении функции, а не в самой функции. В самой функции никаких "стрелок" нет.

У одной и той же функции может быть несколько определений. Например, я могу определить $f(x)$ как $1+1$, а могу сказать, что $f(x) = 5-3$ для любого $x$. Определения разные, функция одна и та же!

Если в одном из возможных определений какой-то функции присутствуют мистические "стрелки", то это не значит, что эти "стрелки" должны присутствовать в любом из её определений. Понимаете?!

[TypucT]

Ага, понял.
Если в теории $K$ выводимо $\Gamma\vee\overline\Gamma$, $\Gamma\to h(x) \in S$, $\Gamma\to h(x) \in S$, $((\Gamma\vee\overline\Gamma) \& (\Gamma\to h(x) \in S) \& (\Gamma\to h(x) \in S))\to (h(x)\in S)$, и действует правило modus ponens (или что-то похожее), то в $K$ выводимо $h(x)\in S$.
Профессор Снэйп, вам спасибо

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

Nxx писал(а):

Откройте любой учебник и прочитайте определение функции.

Выбросте свои учебники фтопку.

Лично я считаю г-на Nxx типичным глупым троллем и в дальнейшем собираюсь его игнорировать. К чему и всех остальных призываю.

[Nxx]

Цитата:

Стрелка присутсвует в определении функции, а не в самой функции.

Может быть, вы приведете эквивалентное определение, но без стрелки?

Цитата:

Выбросте свои учебники фтопку.

Фихтенгольца тоже?

Добавлено спустя 1 минуту 19 секунд:

Цитата:

Лично я считаю г-на Nxx типичным глупым троллем и в дальнейшем собираюсь его игнорировать. К чему и всех остальных призываю.

Сам глупый тролль.

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

TypucT писал(а):

Ага, понял.
Если в теории $K$ выводимо $\Gamma\vee\overline\Gamma$, $\Gamma\to h(x) \in S$, $\Gamma\to h(x) \in S$, $((\Gamma\vee\overline\Gamma) & (\Gamma\to h(x) \in S$) & ($\Gamma\to h(x) \in S))\to (h(x)\in S)$, и действует правило modus ponens, то в $K$ выводимо $h(x)\in S$.
Профессор Снэйп, вам спасибо

Ещё добавлю маленький штрих. Как Вы могли заметить, при Ваших гипотезах (справедливых в силу определения $S$) от теории $K$ ничего не зависит. Утверждение $h \in S$ доказывается средствами чистой логики, без привлечения гипотез из $K$

[TypucT]

Профессор Снэйп писал(а):

TypucT писал(а):

Ага, понял.
Если в теории $K$ выводимо $\Gamma\vee\overline\Gamma$, $\Gamma\to h(x) \in S$, $\Gamma\to h(x) \in S$, $((\Gamma\vee\overline\Gamma) & (\Gamma\to h(x) \in S$) & ($\Gamma\to h(x) \in S))\to (h(x)\in S)$, и действует правило modus ponens, то в $K$ выводимо $h(x)\in S$.
Профессор Снэйп, вам спасибо

Ещё добавлю маленький штрих. Как вы могли заметить, при Ваших гипотезах (справедливых в силу определения $S$) от теории $K$ ничего не зависит. Утверждение $h \in S$ доказывается средствами чистой логики, без привлечения гипотез из $K$

Действительно, гипотезы верны, потому что иначе $h(x)$ не было бы определением функции. Правда, в их записи используется внелогический предикат $\in$, но если выводимо что-то вроде $A\vee A\to A$, тогда действительно, от теории ничего не зависит.

[Nxx]

TypucT, Профессор Снэйп использует нетривиальное определение понятия функции, которое как правило, не используется в курсе матана. По сути, определение, которое он привел является очень широким обобщением традиционнного понятия функции.

[MaximKat]

Nxx
а причем тут вообще матан?

[TypucT]

Nss, прежде, чем что-либо доказывать, нужно договориться о формальной системе, в которой будет проводиться доказательство. Можно придумать много систем, для которых условие задачи некорректно. Например, в какой-нибудь трехзначной логике, где выводимо $\Gamma’$, функция

$$ g(x) = \left\{ \begin{array}{сl} 2, & $если $ \Gamma,\\ 1, & $если $ \overline\Gamma,\\ ?, & $если $ \Gamma’. \end{array} \right $$

недоопределена. Аналогично, функция $h(x)$ может оказаться некорректно определенной в некоторых принятых формальных системах. Поэтому, перед тем как приступить к решению задачи в конкретной системе, правомерно задать вопрос о корректности определения $h(x)$, иначе задача не имеет смысла в этой системе. Ниже я попытался описать, почему в классической логике задача корректна и имеет решение.

Рассмотрим класс формальных систем $K_h$, в которых условие задачи корректно. Каким условиям необходимо удовлетворяет $K\in K_h$? Исходя из интуитивного понимания определения $h(x)$ на русском языке, в $K$ истинно следующее. (Более точно: принятие следующих гипотез не должно приводить к противоречию.)
Определение функции $h(x)$:
(1) $\Gamma\vee \overline\Gamma$ --- функция определена для всех возможных истинностных значений $\Gamma$,
(2) $\Gamma\to h(x)\equiv 2$ --- значение первой альтернативы,
(3) $\overline\Gamma\to h(x)\equiv 1$ --- значение второй альтернативы,
(4) $\Gamma\to \overline{\overline\Gamma}$ --- однозначность первой альтернативы,
(5) $\overline \Gamma\to \overline\Gamma$ --- однозначность второй альтернативы.
Еще потребуется определение $\in$:
(6) $h(x)\equiv 2\to h(x)\in S$,
(7) $h(x)\equiv 1\to h(x)\in S$,
(8) $h(x)\in S\vee \overline{h(x)\in S}$,
(9) $h(x)\in S\to \overline{\overline{h(x)\in S}}$,
(10) $\overline{h(x)\in S}\to \overline{h(x)\in S}$.
И определение $\equiv$:
(12) $h(x)\equiv 1\to \overline{h(x)\equiv 2}$,
(13) $h(x)\equiv 2\to \overline{h(x)\equiv 1}$.
Кроме того, чтобы задача была разрешима в $K$, необходимо, чтобы в $K$ из (1)-(13) было выводимо $h(x)\in S$ или $\overline{h(x)\in S}$.

Классическая логика удовлетворяет условиям (1)-(13), и, кроме того, проблема в ней легко решается.

В какой формальной системе и что именно вы пытаетесь доказать?

PS
Раз уж тема перенесена в дискусионные

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

TypucT писал(а):

В какой формальной системе и что именно вы пытаетесь доказать?

Боюсь, что он этого сам не знает.

Насчёт однозначности альтернатив я что-то не совсем понял. Пункт $(5)$ так вообще смешно выглядит Если уж говорить про однозначность, я бы $(4)$ и $(5)$ вместе заменил на что-то вроде $\neg(\Gamma \mathop{\&} \neg\Gamma)$.

В пункте $(3)$ Вы забыли на $\Gamma$ отрицание навесить. В пункте $(11)$ опечатка: знак дизъюнкции вместо знака отрицания. И ещё: это, конечно, не принципиально, но большой буквой $\Gamma$ принято обозначать множество формул, а не отдельную формулу. Просто традиция такая.

[TypucT]

Профессор Снэйп писал(а):

Насчёт однозначности альтернатив я что-то не совсем понял. Пункт $(5)$ так вообще смешно выглядит Если уж говорить про однозначность, я бы $(4)$ и $(5)$ вместе заменил на что-то вроде $\neg(\Gamma \mathop{\&} \neg\Gamma)$.

(4) означает, что первая альтернатива исключает вторую, (5) - вторая исключает первую. Чтобы доказать (5) в классической логике немножко постараться надо
Ваш вариант лаконичнее говорит о том же.

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

Да, и относительно исходной задачи: у Мендельсона, по крайней мере в этом упражнении, подразумевалась именно классическая логика.

[Nxx]

TypucT писал(а):

(2) $\Gamma\to h(x)\equiv 2$ --- значение первой альтернативы,
(3) $\overline\Gamma\to h(x)\equiv 1$ --- значение второй альтернативы,

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