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

[Nxx]

Цитата:

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

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

Скажите, по вашему мнению, такая функция:

$$ h(x) = \left\{ \begin{array}{сl} 2, & $с вероятностью 1/2$,\\ 1, & $с вероятностью 1/2$. \end{array} \right. $$

тоже примитивно-рекурсивна?

[TypucT]

Предлагаю избавиться от «божественного откровения» и длинных слов с помощью следующей постановки.

Пусть функция $f(x)\in S$, если $f(x)\equiv 1$ либо $f(x)\equiv 2$.
Пусть гипотеза Гольдбаха $\Gamma$ недоказуема в теории $K$.
Определим функцию

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

Можно ли средствами теории $K$ доказать, что функция $h(x)\in S$?

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

Nxx писал(а):

...

По моему, уважаемый Nxx, Вы несёте какой-то не поддающийся осмыслению бред. Я не знаю, как на него реагировать!

[Nxx]

TypucT писал(а):

Предлагаю избавиться от «божественного откровения» и длинных слов с помощью следующей постановки.

Пусть функция $f(x)\in S$, если $f(x)\equiv 1$ либо $f(x)\equiv 2$.
Пусть гипотеза Гольдбаха $\Gamma$ недоказуема в теории $K$.
Определим функцию

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

Можно ли средствами теории $K$ доказать, что функция $h(x)\in S$?

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

Цитата:

По моему, уважаемый Nxx, Вы несёте какой-то не поддающийся осмыслению бред.

По-моему, вы просто намеренно делаете вид, что не понимаете.

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

TypucT писал(а):

Пусть функция $f(x)\in S$, если $f(x)\equiv 1$ либо $f(x)\equiv 2$.
Пусть гипотеза Гольдбаха $\Gamma$ недоказуема в теории $K$.
Определим функцию

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

Можно ли средствами теории $K$ доказать, что функция $h(x)\in S$?

А вот здесь уместно спросить, что Вы считаете "доказательством". Ответ зависит от того, какую логику, какие правила вывода Вы выбираете!

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

Про конструктивистов Вам ещё на первой странице говорили.

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

Nxx писал(а):

По-моему, вы просто намеренно делаете вид, что не понимаете.

Я действительно не понимаю Вашу галиматью. Вы говорите ни о чём.

Ещё раз возвращаюсь к заданному Вам вопросу, на который жду ответа. Что значит "функция содержит внутри себя операцию выбора"? Дайте соответствующие определения.

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

[Nxx]

Цитата:

Ещё раз возвращаюсь к заданному Вам вопросу, на который жду ответа. Что значит "функция содержит внутри себя операцию выбора"? Дайте соответствующие определения.

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

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

вы подменяете двумя функциями-константами и делаете из этого какие-то выводы.

[TypucT]

Nxx писал(а):

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

Докажите.

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

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

Докажите.

Цитата:

Про конструктивистов Вам ещё на первой странице говорили.

Сказать я тоже могу. Вы мне поверите на слово?

[маткиб]

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

У элементарных частиц не бывает цвета, а про континуум-гипотезу бессмысленно говорить, верна она или нет.

Вопрос.
А где можно прочитать обоснование того, что это говорить бессмысленно? Или хотя бы доказательство принципиальной неразрешимости, т.е. не только независимости с ZFC, но и с другими аксиоматиками, получающимися добавлением к ZFC, например, интуитивно очевидных высших аксиом бесконечности? И почему из принципиальной неразрешимости делается вывод о бессмысленности?

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

Nxx писал(а):

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

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

[Jnrty]

Jnrty:

Переношу из раздела "Помогите решить / разобраться" в раздел "Дискуссионные темы (М)".

[Nxx]

TypucT писал(а):

Nxx писал(а):

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

Докажите.

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

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

TypucT писал(а):

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

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

Докажите.

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

[Nxx]

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

Nxx писал(а):

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

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

Пожалуйста:

Цитата:

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

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

[TypucT]

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

TypucT писал(а):

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

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

Докажите.

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

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

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

Nxx писал(а):

TypucT писал(а):

Nxx писал(а):

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

Докажите.

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

Я один так думаю, или это уже что-то дельное?

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

Nxx писал(а):

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

Очередная порция бреда.

Да будет Вам известно, что функцией из $A$ в $B$ называется произвольное подмножество $A \times B$, обладающее следующим свойством: для любого $a \in A$ существует единственное $b \in B$, такое что пара $\langle a,b \rangle$ ему принадлежит.

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

В теории "законы" не указываются: теория содержит "утверждения" (более точно --- формулы некоторого языка, например, языка исчисления предикатов, не содержащие свободных переменных), а ещё все "утверждения" (то есть формулы) делятся на доказуемые и не доказуемые из данной теории. Фраза "в теории невозможно указать закон" является бессмысленным набором слов и ничем более! Как и всё, что пишет Nxx, увы

Вот Вам пример для мучительных раздумий. Я его уже писал, но Вы, возможно, не обратили на него внимание.

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