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

[TypucT]

Nxx писал(а):

TypucT писал(а):

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

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

Вы упомянули некую "формальную систему примитивно-рекурсивных функций". Где можно найти ее определение: (a) множество символов; (b) что в ней является формулой; (c) множество аксиом; (d) множество правил вывода?
Зная (a) и (b) мы сможем однозначно и без всяких споров определить, являются ли строки (2) и (3) формулами этой теории. Если ответ будет отрицательным, тогда вы правы и, действительно, в "формальной системе примитивно-рекурсивных функций" невозможно сформулировать (2) и (3).

Цитата:

если считать оба высказывания частью определения функции h(x)

Да, так и есть, выражения (1)-(5) есть определение функции $h(x)$, записанное более формально, чем в условии.

Кроме прочего, вас не смущает, что $\Gamma$ и утверждения содержащие $\Gamma$ вообще-то cформулировать несложно?

[Dandan]

TypucT писал(а):

Вы упомянули некую "формальную систему примитивно-рекурсивных функций". Где можно найти ее определение: (a) множество символов; (b) что в ней является формулой; (c) множество аксиом; (d) множество правил вывода?

В вашем же Мендельсоне перед определением примитивно рекурсивной функции целые 2 параграфа посвящены формализации арифметики (теория S). Как вы думаете зачем?
Если не понятно зачем, обратите внимание на Предложение 3.23 - всякая рекурсивная функция представима в S.

[TypucT]

Dandan писал(а):

[тут что-то было]всякая рекурсивная функция представима в S.

Да. И что же?

[Xaositect]

Dandan в сообщении #188816 писал(а):

всякая рекурсивная функция представима в S.

Ваша многострадальная функция представима в $S$. Только неизвестно, какой формулой, $y=S0$ или $y=SS0$.

[TypucT]

Xaositect писал(а):

Dandan в сообщении #188816 писал(а):

всякая рекурсивная функция представима в S.

Ваша многострадальная функция представима в $S$. Только неизвестно, какой формулой, $y=S0$ или $y=SS0$.

Хуже. Даже формула известна.
$R(x_1,x_2)$: $(\Gamma\to x_2=0'')\mathop{\&}(\overline\Gamma\to x_2=0')$.

[Nxx]

Xaositect писал(а):

Dandan в сообщении #188816 писал(а):

всякая рекурсивная функция представима в S.

Ваша многострадальная функция представима в $S$. Только неизвестно, какой формулой, $y=S0$ или $y=SS0$.

Это только если утверждения (2) и (3) не являются частью определения функции. Я это специально уточнил. Но

TypucT писал(а):

Цитата:

если считать оба высказывания частью определения функции h(x)

Да, так и есть, выражения (1)-(5) есть определение функции $h(x)$, записанное более формально, чем в условии.

Если определением функции является $y=S0$ или $y=SS0$, то проблем, разумеется, нет.

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

Цитата:

Где можно найти ее определение: (a) множество символов; (b) что в ней является формулой; (c) множество аксиом; (d) множество правил вывода?

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

[TypucT]

Nxx писал(а):

Цитата:

Где можно найти ее определение: (a) множество символов; (b) что в ней является формулой; (c) множество аксиом; (d) множество правил вывода?

Могу точно сказать, что символ $\Gamma$ не является символом, определенным в этой формальной системе.

Наконец-то, хоть какое-то определенное утверждение. $\Gamma$ - это формула (не символ), которую можно записать в формальной арифметике. Следовательно, ваша формальная система отлична от формальной арифметики. Можете ли вы рассказать о ней поподробнее, т.е. дать (a)-(d)?

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

[Nxx]

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

Функция выбора из неопределенного множества или по неопределенному индексу или по индексу, который не является ни аргументом функции или примитивно-рекурсиной функцией, в системе примитивно-рекурсивных функций невозможна.

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

Более формально:

►
1) Простейшие функции

$$ s(x)=x+1, O^{n}(x_1,x_2,...,x_n)=0, I^{nm} (x_1,x_2,...,x_n)=x_m $$

примитивно рекурсивны.
2) Если функция f получена из примитивно рекурсивных функций с
помощью оператора суперпозиции
$f(x_1,x_2,...,x_n)=h(g_1(x_1,x_2,...,x_n) ,g_2(x_1,x_2,...,x_n),...,g_m(x_1,x_2,...,x_n))$
или с помощью оператора
примитивной рекурсии
$f(x_1,x_2,...,x_n,0)= g(x_1,x_2,...,x_n),$
$ f(x_1,x_2,...,x_n, y+1)= h(x_1,x_2,...,x_n,y, f(x_1,x_2,...,x_n,y)),$
то функция f примитивно рекурсивна.
3) То, что функция f примитивно рекурсивна, устанавливается несколькими
применениями правил 1) и 2).

[TypucT]

Nxx писал(а):

1) Простейшие функции

$$ s(x)=x+1, O^{n}(x_1,x_2,...,x_n)=0, I^{nm} (x_1,x_2,...,x_n)=x_m $$

примитивно рекурсивны.
2) Если функция f получена из примитивно рекурсивных функций с
помощью оператора суперпозиции
$f(x_1,x_2,...,x_n)=h(g_1(x_1,x_2,...,x_n) ,g_2(x_1,x_2,...,x_n),...,g_m(x_1,x_2,...,x_n))$
или с помощью оператора
примитивной рекурсии
$f(x_1,x_2,...,x_n,0)= g(x_1,x_2,...,x_n),$
$ f(x_1,x_2,...,x_n, y+1)= h(x_1,x_2,...,x_n,y, f(x_1,x_2,...,x_n,y)),$
то функция f примитивно рекурсивна.
3) То, что функция f примитивно рекурсивна, устанавливается несколькими
применениями правил 1) и 2).

Отлично! Уже почти виден набор символов вашей формальной теории. Дело за малым: скажите, что у вас является формулой?

[TypucT]

TypucT писал(а):

Xaositect писал(а):

Dandan в сообщении #188816 писал(а):

всякая рекурсивная функция представима в S.

Ваша многострадальная функция представима в $S$. Только неизвестно, какой формулой, $y=S0$ или $y=SS0$.

Хуже. Даже формула известна.
$R(x_1,x_2)$: $(\Gamma\to x_2=0'')\mathop{\&}(\overline\Gamma\to x_2=0')$.

Поторопился. Не получается доказать.

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

Nxx писал(а):

...
Это только если утверждения (2) и (3) не являются частью определения функции. Я это специально уточнил.
...
Если определением функции является $y=S0$ или $y=SS0$, то проблем, разумеется, нет.

и т. п.

$$ \exists_1 x_2 ((P\to x_2 = G_1(x_1)) \& (\neg P\to x_2 = G_2(x_1))) \equiv (P \to \exists_1 x_2 (x_2=G_1(x_1))) \& (\neg P \to \exists_1 x_2 (x_2=G_2(x_1))), $$

следовательно

$$ f(x) = \left\{ \begin{array}{сl} g_1(x), & $если $ R $ истинно$,\\ g_2(x), & $если $ R $ ложно$. \end{array} \right. $$

то же самое, что и

$$ $Если $R$ истинно, то $f(x)\equiv g_1(x)$. Если $R$ ложно, то $f(x)\equiv g_2(x)$.$ $$

[Nxx]

Дело в том, что $g_1(x)$ и $g_2(x)$ вы можете задать в системе примитивно-рекурсивных функций, а всю фразу

$$ $Если $R$ истинно, то $f(x)\equiv g_1(x)$. Если $R$ ложно, то $f(x)\equiv g_2(x)$.$ $$

- нет. Точнее, эта фраза может быть задана в системе примитивно-рекурсивных функций только если R - аргумент функции f. Завязать примитивно-рекурсивную функцию на какую-то внешнюю, неизвестную константу, не передавая ее в качестве аргумента в функцию, в формальном языке примитивно-рикурсивных функций невозможно.

[TypucT]

Nxx писал(а):

в формальном языке примитивно-рикурсивных функций невозможно.

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

Например, реально вы могли дать такое возражение: по определению выразимого отношения все еще нельзя доказать, что в принятой аксиоматике формальной арифметики есть формула, с помощью которой выражалось бы отношение $\Gamma$. Тут мне нечем было бы крыть, а пришлось бы наложить заплатку, мол, для доказательства я использовал такое расширение формальной арифметики, в которой формула, выражающая $\Gamma$, разрешима. Вообще, утверждая, что формула $P$ некоторой формальной теории $K$ выражает отношение $R$, мы тем самым предполагаем ее разрешимость в $K$. А что если она неразрешима в $K$? Нет проблем - добавим к аксиомам теории $K$ новую аксиому $P$ или $\neg P$ и все станет на свои места в новой теории $K'$.

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

TypucT писал(а):

Вообще, утверждая, что формула $P$ некоторой формальной теории $K$ выражает отношение $R$, мы тем самым предполагаем ее разрешимость в $K$.

Что Вы понимаете под "разрешимостью формулы в теории"?

[TypucT]

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

TypucT писал(а):

Вообще, утверждая, что формула $P$ некоторой формальной теории $K$ выражает отношение $R$, мы тем самым предполагаем ее разрешимость в $K$.

Что Вы понимаете под "разрешимостью формулы в теории"?

Формула $P$ разрешима в теории $K$, если $\vdash_K P$ либо $\vdash_K \neg P$. Т.е. $P$ можно доказать либо опровергнуть в $K$.

Утверждение касалось замкнутых формул. Для незамкнутой формулы $A(x_1, ..., x_n)$, выражающей отношение $R(x_1, ..., x_n)$, необходима разрешимость формулы $A(k_1, ..., k_n)$ для всякого набора цифр $k_1, ..., k_n$. Здесь цифра - это терм $0$ с применением операции "прибавление единицы" нужное количество раз.

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

TypucT писал(а):

Формула $P$ разрешима в теории $K$, если $\vdash_K P$ либо $\vdash_K \neg P$. Т.е. $P$ можно доказать либо опровергнуть в $K$.

Первый раз встречаю термин "разрешимость" в таком смысле. Обычно сами теории на предмет разрешимости изучают...