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

[Nxx]

Цитата:

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

Только если данная операция не входит в определение функции.

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

Кстати, вот еще аналогичный пример:

$f(x)=z+1$

f(x) - константа?

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

[AD]

Nxx писал(а):

$f(x)=z+1$

f(x) - константа?

Конечно!!

Понимаете, это, конечно, хорошо, что вы так всё на примерах излагаете, но в задаче under consideration совершенно однозначно заявлено, что $f:\mathbb{N}\to\mathbb{N}$. А когда вы говорите, что $f$ еще и от $z$ какого-то зависит, то выясняется, что, как минимум, $f:\mathbb{N}^2\to\mathbb{N}$ или что-то типа того. То есть надо уже писать $f(x,z)$ вместо $f(x)$, и вообще это другая планета совсем.

[Nxx]

Цитата:

Конечно!!

А если окажется, что z=2x?

AD писал(а):

То есть надо уже писать $f(x,z)$ вместо $f(x)$, и вообще это другая планета совсем.

Я об этом и говорю. Неявно вводится еще один аргумент функции, при этом в списке аргументов почему-то не перечисляется. Теперь представим, что z - невычислимое число. Будет ли f(x) вычислимой функцией?

[AD]

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

Неявно вводится еще один аргумент функции, при этом в списке аргументов почему-то не перечисляется.

Ну а понятие примитивно-рекурсивной функции вообще вводится ли для функций двух аргументов?

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

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

А если окажется, что z=2x?

А тогда надо было писать $z(x)$.

[TypucT]

Nxx, Dandan, ваши аргументы меня не убедили, однако я задумался.
Я не вижу способа показать, как эта функция может не быть примитивно рекурсивной.

(i)
Если гипотеза Гольдбаха неразрешима, то к ней не существует контрпримера и тогда она истинна. Значит, если ее неразрешимость доказана, то доказана ее истинность и тогда она разрешима. Значит, неразрешимость гипотезы Гольдбаха доказать невозможно.

(ii)
Предположим, что функция $h(x)$ не примитивно рекурсивная, тогда ее нельзя получить с помощью $0+1+1$ и нельзя получить с помощью $0+1$. Значит, проблема Гольдбаха неразрешима и, следовательно, истинна. Но тогда $h(x)\equiv 2$ и примитивно рекурсивна. absurd!
Т.е. невозможно доказать, что $h(x)$ не примитивно рекурсивная.

(iii)
Чтобы утверждать, что функция $h(x)$ примитивно рекурсивная, необходимо доказать, что ее можно получить из уже известных с помощью суперпозиции и рекурсии. Такое доказательство можно проводить двумя путями. Во-первых, продемонстрировать конкретный способ представления $h(x)$ (это пытался сказать Dandan). Во-вторых, доказать существование такого представления. Для функции $h(x)$ первый метод не подходит, а второй распадается на два случая: (1) проблема Гольдбаха разрешима и (2) проблема Гольдбаха не разрешима.
В случае (1) либо можно доказать $h(x)\equiv 1$, либо можно доказать $h(x)\equiv 2$, и, следовательно, можно доказать, что функция $h(x)$ примитивно рекурсивная. Более того, после проведения доказательства, станет ясно какая именно.
В случае (2) гипотеза Гольдбаха истинна, и $h(x)\equiv 2$, но доказать это невозможно. (Значит ли это, что в случае (2) мы никогда не узнаем, как именно получить $h(x)$, хотя она примитивно рекурсивна?)

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

AD писал(а):

Ну а понятие примитивно-рекурсивной функции вообще вводится ли для функций двух аргументов?

Конечно вводится!

http://www.nsu.ru/education/podzorov/Alg/Course.pdf стр. 51 -- 60 и стр. 112 -- 118, определение на стр. 52 -- 53.

P. S. Весь остальной маразм, угнездившийся в этой теме, даже не охота комментировать!

[Nxx]

Цитата:

Предположим, что функция $h(x)$ не примитивно рекурсивная, тогда ее нельзя получить с помощью $0+1+1$ и нельзя получить с помощью $0+1$. Значит, проблема Гольдбаха неразрешима и, следовательно, истинна.

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

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

Nxx писал(а):

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

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

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

Призываю модераторов перенести тему в дискуссионный раздел: там ей самое место. Все превдопроблемы, которые здесь обсуждаются уже на протяжении четырёх страниц, высосаны из пальца и проистекают из попытки смешения "французского с нижегородским". Автор темы старается нарочно не понимать очевидных вещей. разводя флейм на пустом месте. Очень походит на стиль Давидюка, не находите?

[Руст]

Понятие рекурсивности относится не сколько к функции, сколько к существованию алгоритма, вычисляющего её. Об этом я уж писал. Определения типа $h(x)=1$ если верна гипотеза (например континиума), иначе $h(x)=0$ не определяет алгоритма, а значит не может идти речи о её рекурсивности. В случае гипотезы континиума как выяснилось, оно не зависит от исходной системы аксиом $ZFS$ и может быть эта система аксиом расширена как принятием континиум гипотезы в качестве дополнительной аксиомы, так и принятием его отрицания. Что демонстрирует полную нелогичность принятия в качестве определения задание $h(x)$ вышеприведённым "определением".

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

Руст писал(а):

Понятие рекурсивности относится не сколько к функции, сколько к существованию алгоритма, вычисляющего её. Об этом я уж писал.

Существование алгоритма вычисления --- свойство функции! В чём проблема-то?

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

Руст писал(а):

Определения типа $h(x)=1$ если верна гипотеза (например континиума), иначе $h(x)=0$ не определяет алгоритма, а значит не может идти речи о её рекурсивности. В случае гипотезы континиума как выяснилось, оно не зависит от исходной системы аксиом $ZFS$ и может быть эта система аксиом расширена как принятием континиум гипотезы в качестве дополнительной аксиомы, так и принятием его отрицания. Что демонстрирует полную нелогичность принятия в качестве определения задание $h(x)$ вышеприведённым "определением".

Ну, Вы бы ещё сказали, что $h(x)=1$, если элементарная частица электрон всегда синего цвета, и $h(x)=0$, если какого-то другого. Такие "задания функции" как раз и есть бессмысленный набор слов. У элементарных частиц не бывает цвета, а про континуум-гипотезу бессмысленно говорить, верна она или нет. Мы же, если я не ошибаюсь, обсуждаем совершенно другой случай, когда значение функции зависит от истинности гипотезы Гольдбаха. А для неё мы признаём, что она либо истинна, либо ложна, и что третьего не дано. Всё-таки речь идёт о простом утверждении про натуральные числа, записываемом универсальной формулой в языке арифметики первого порядка. Так что привлечение континуум-гипотезы совершенно неуместно.

[Nxx]

Цитата:

Теперь я подкидываю монетку, и если выпадает орёл, то я выбираю шар с номером 1, а если решка, то шар с номером 2. Вопрос: какого цвета шар я выберу? Очевидно, что белого!

Если вы выбираете из двух функций

$$h(x)\equiv1$$

и

$$h(x)\equiv2$$

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

[TypucT]

Nxx писал(а):

Цитата:

Предположим, что функция $h(x)$ не примитивно рекурсивная, тогда ее нельзя получить с помощью $0+1+1$ и нельзя получить с помощью $0+1$. Значит, проблема Гольдбаха неразрешима и, следовательно, истинна.

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

Это место как раз верно. Вывод о неразрешимости проблемы Гольдбаха сделан на основании определения $h(x)$, а не на основании определения примитивной рекурсивности.
Там есть более слабые места. Например:

Цитата:

В случае (2) гипотеза Гольдбаха истинна, и $h(x)\equiv 2$, но доказать это невозможно.

Можно ли в этом случае говорить о примитивной рекурсивности $h(x)$? Не противоречит ли это определению?

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

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

Теперь я подкидываю монетку...

Пример не самый удачный. Если перевести на рассматриваемый случай: "Теперь я доказываю или опровергаю гипотезу Гольдбаха..."

[Nxx]

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

[TypucT]

Руст писал(а):

Понятие рекурсивности относится не сколько к функции, сколько к существованию алгоритма, вычисляющего её.

Есть определение этого понятия. Там написано что к чему относится и про алгоритм нет ни слова.

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

Nxx писал(а):

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

По этому поводу

В. Шекспир писал(а):

Набор слов почище всякого смысла!

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

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

TypucT писал(а):

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

Теперь я подкидываю монетку...

Пример не самый удачный. Если перевести на рассматриваемый случай: "Теперь я доказываю или опровергаю гипотезу Гольдбаха..."

Да нет, почему, удачный. Только я бы сказал не "доказываю или опровергаю гипотезу Гольдбаха", у неё ведь может и не быть ни доказательства, ни опровержения а сказал бы "устанавливаю истинность или ложность гипотезы Гольдбаха". Неважно как устанавливаю; например, при помощи божественного откровения. Вот даст мне Бог монетку, которая всегда падает орлом, если гипотеза Гольдбаха истинна, и решкой, если наоборот. А я эту монетку буду подкидывать

У нас есть некое указание на одну из констант: $1$ или $2$. Мы не можем установить, на какую точно, однако знаем, что одна из этих констант однозначна задана. Это может быть указание при помощи подбрасываемой монеты или при помощи гипотезы Гольдбаха --- не важно.

Допустим, мы раскрутили колесо рулетки. Пока рулетка крутилась, в казино неожиданно погас свет и стало темно. Мы знаем, что стрелка остановилась и что она указывает на какое-то число. Пока не включат свет, мы не сможем установить, на какое точно; не исключено, что свет не включат никогда и число, на которое указала стрелка, так и останется неизвестным. Однако несмотря на то, что мы не знаем точного значения этого числа, мы знаем про него очень много. Например, знаем то, что это натуральное число, лежащее в интервале от $0$ до $36$.

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

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

Вот ещё такой же "хитрый" вопрос

Допустим, я вычисляю функцию $f$ следующим образом. Если гипотеза Гольдбаха верна, то я для любого $x$ сложу $2$ и $2$, после чего выдам полученный результат $4$ в качестве значения $f(x)$. А если гипотеза Гольдбаха не верна, то я при любом $x$ умножу $2$ на $2$ и опять же выдам полученный результат $4$ в качестве значения $f(x)$. Верно ли, что функция $f(x) = 4$ примитивно рекурсивна?