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

[TypucT]

Упражнение из "Введения в мат. логику" Мендельсона 1971 г., с. 143. (несущественно изменено).

Пусть при каждом $x$

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

Является ли $h(x)$ примитивно рекурсивной функцией?

Мои рассуждения:
В условиях в правой части стоит высказывание и его отрицание, характеристическая функция любого высказывания (как отношения без аргументов) - константа $0$, если высказывание истинно, $1$ - если ложно. Значит, примитивно рекурсивны и функции $C_1$ и $C_2$, соответствующие высказываниям в правой части (хотя мы и не знаем, какая из них является константой $0$, а какая $1$). Тогда и функция $h(x) = 2\cdot \overline{sg}(C_1) + 1\cdot \overline{sg}(C_2)$ примитивно рекурсивна как полученная подстановкой примитивно рекурсивных функций.

Смущает то, что функции $C_1$ и $C_2$ неизвестны. Можно ли так рассуждать?

UPD:
Вот более простые рассуждения, но вопрос остается в силе.
Очевидно, либо $h(x)=2$ для всякого $x$, либо $h(x)=1$ для всякого $x$. В любом случае $h(x)$ константа и, следовательно, примитивно рекурсивна.

[маткиб]

TypucT писал(а):

Смущает то, что функции $C_1$ и $C_2$ неизвестны. Можно ли так рассуждать?

Можно (пока конструктивисты не прибежали)

[Nxx]

$C_1$ и $C_2$ могут оказаться выводимыми из аксиом, а могут и не выводимыми. Это зависит от того, доказума ли гипотеза Гольдбаха. А как мы знаем, в математике есть недоказуемые теоремы.

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

Это означает, что приведенный вами пример не является примитивно-рекурсивной функцией.

[Xaositect]

TypucT в сообщении #187243 писал(а):

Смущает то, что функции $C_1$ и $C_2$ неизвестны. Можно ли так рассуждать?

По этому поводу был(или еще есть) большой спор в дискусионном разделе.

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

$C_1$ и $C_2$ могут оказаться выводимыми из аксиом, а могут и не выводимыми.

Вы так английский термин definable переводите?

[TypucT]

Nxx писал(а):

$C_1$ и $C_2$ могут оказаться выводимыми из аксиом, а могут и не выводимыми. Это зависит от того, доказума ли гипотеза Гольдбаха. А как мы знаем, в математике есть недоказуемые теоремы.

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

Это означает, что приведенный вами пример не является примитивно-рекурсивной функцией.

Но в определении примитивной рекурсивности нет связи с выводимостью.

[маткиб]

Nxx писал(а):

$C_1$ и $C_2$ могут оказаться выводимыми из аксиом, а могут и не выводимыми.

Конструктивисты прибежали

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

TypucT в сообщении #187320 писал(а):

Но в определении примитивной рекурсивности нет связи с выводимостью.

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

[Nxx]

Еще раз прочитайте определение и составьте h(x) из того, из чего состоят все примитивно-рекурсивные функции.

[Dandan]

маткиб, не стоит в борьбе с конструктивистами скатываться до абсурда. h(x) конечно же не примитивно рекурсивна.

[Руст]

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

[маткиб]

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

маткиб, не стоит в борьбе с конструктивистами скатываться до абсурда. h(x) конечно же не примитивно рекурсивна.

Это с каких это пор константы не являются примитивно рекурсивными?

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

Руст в сообщении #187347 писал(а):

Так как вы не дали способ вычисления, то ваша функция не рекурсивна.

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

Поэтому функция в первом посте примитивно рекурсивна, и это факт! Даже не смотря на то, что автор не выписал в явном виде её определение через нужные операции.

[Nxx]

Цитата:

Это с каких это пор константы не являются примитивно рекурсивными?

В примитивно рекурсивных функциях можно использовать только те элементы, которые получаются из нуля с помощью

- Прибавления единицы
- Операции выбора из конечного числа элементов элемента с определенным номером
- Суперпозиции
- Рекурсии

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

[маткиб]

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

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

Это только конструктивисты могут из своей немощности делать вывод о том, что функция не является примитивно рекурсивной

[Nxx]

Цитата:

Это только конструктивисты могут из своей немощности делать вывод о том, что функция не является примитивно рекурсивной

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

[маткиб]

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

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

А Вы попробуйте $2^{2^{10000000000}}$ на досуге выписать в виде палочек на заборе.

[Nxx]

Цитата:

А Вы попробуйте $2^{2^{10000000000}}$ на досуге выписать в виде палочек на заборе.

Какие-то низкокачественные аргументы пошли, я смотрю.

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

Подведу итог:

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

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