Вычисление характеристической функции

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

Пусть $m > 0$ --- натуральное число и $A \subseteq \mathbb{N}$. Для определённости давайте считать, что натуральный ряд начинается с нуля, хотя в данной задаче это не важно.

Для $x \in \mathbb{N}$ через $A(x)$ обозначаем значение характеристической функции множества $A$ на элементе $x$. Другими словами, $A(x) = 0$, если $x \not\in A$, и $A(x) = 1$ при $x \in A$.

Нам дана $f$ --- вычислимая функция из $\mathbb{N}^m$ в $\{ 0, 1, \ldots, m \}$, такая что $f(x_1, \ldots, x_m) \neq A(x_1) + \ldots + A(x_m)$ для любого набора $x_1, \ldots, x_m$ натуральных чисел длины $m$. Вычислимость можно понимать так, что есть написанная кем-то программа, которая вычисляет $f$ и которой можно пользоваться, хотя код этой программы очень сложен и практически не поддаётся расшифровке.

Надо доказать, что существует алгоритм вычисления $A(x)$.

[Руст]

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

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

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

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

Почему Вы решили, что там что-то задано некорректно? Для данной функции $f$ множество $A$ существует по условию задачи. А если Вы считаете, что может существовать несколько множеств $A$, удовлетворяющих условию $f(x_1, \ldots, x_m) \neq A(x_1) + \ldots + A(x_m)$, то приведите пример! Что там и где недоказуемо, я не понял! И фраза о том, что множества $A$ не существует в случае, когда $A(x) \equiv 0$, выглядит как полный бред: очевидно, что если $A(x) \equiv 0$, то $A = \varnothing$.

Кстати, если $m=1$, то решение очевидно, так как $A(x) = 1 - f(x)$. В случае $m>1$ уже надо думать

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

[Руст]

Пусть функция $f\equiv m$. Тогда в качестве A подходит любое множество с меньшим чем m элементами. Т.е. уже при m=2 любое одноэлементное множество.

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

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

Пусть функция $f\equiv m$. Тогда в качестве A подходит любое множество с меньшим чем m элементами. Т.е. уже при m=2 любое одноэлементное множество.

Если $f \equiv m$, то подходит только $A = \varnothing$, так как для $x \in A$ не может быть $f(x, x, \ldots, x) = m$. Ваш пример не годится!

И, кстати, даже если для какой-то $f$ существует несколько множеств $A$, то это не страшно. Главное, чтобы для каждого из таких $A$ существовал алгоритм вычисления $A(x)$.

Например, если $f(x_1, \ldots, x_m) = m$ в случае, если в наборе $x_1, \ldots, x_m$ встречаются разные числа и $f(x, x, \ldots, x)=1$, то $A$ может быть любым одноэлементным либо пустым множеством. Для каждого из таких множеств существует алгоритм вычисления $A(x)$, так что для такой $f$ задача решается и в условии всё задано корректно.

Давайте я ещё раз переформулирую. Даны конкретные $f$ и $A$, связанные указанным свойством. Требуется доказать, что существует алгоритм вычисления $A(x)$.

[Руст]

Хорошо, чуть исправим $f(x,x,..,x)\equiv 1$ (когда все аргументы равны), иначе m.

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

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

Хорошо, чуть исправим $f(x,x,..,x)\equiv 0$ (когда все аргументы равны), иначе m.

Плохо исправили! Если $f(x, x, \ldots, x) = 0$ для всех $x$, то годится только $A = \mathbb{N}$

А вообще смотрите, что я выше добавил, в предыдущем посте. Там всё объясняется.

[Руст]

Я тоже немного исправил. Для простоты $m=2$. Если аргументы равны $f\equiv 1$ иначе $f(x_1,x_2)=2,x_1\not =x_2$. Любое одноэлементное множество подходит.

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

Можете начать решение задачи следующим образом:

Если $A$ конечно, то, очевидно, существует алгоритм вычисления $A(x)$. Так что будем предполагать, что $A$ бесконечно...

Контрпример в данном случае может выглядеть только так: приводится пример нерекурсивного множества $A$ и рекурсивной функции $f$, которые связаны свойством из условия задачи!

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

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

Я тоже немного исправил. Для простоты $m=2$. Если аргументы равны $f\equiv 1$ иначе $f(x_1,x_2)=2,x_1\not =x_2$. Любое одноэлементное множество подходит.

Так ведь для любого одноэлементного множества $A$ существует алгоритм вычисления $A(x)$, так что здесь всё нормально. Ещё раз внимательно прочитайте мои комментарии к условию!!!

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

Короче, надо немного переписать первый пост, чтобы не было проблем с пониманием условия.

[Руст]

Тогда я не понимаю вопроса. Характеристические функции множеств $A_1=\{x_1\},A_2=\{x_2\}$ не равны, следовательно (согласно моей логике) функция $A(x)$ не определена.
Я не понимаю вашу логику, и поэтому больше не буду спорит.

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

Логику мою понять несложно. Требуется доказать существование алгоритма вычисления $A(x)$ для данного конкретного $A$, если известно, что $f$ вычислима и связана с $A$ свойством $f(x_1, \ldots, x_m) \neq A(x_1) + \ldots + A(x_m)$. Что тут непонятного?

Если $f$ вдруг оказалась такой, что любое одноэлементное (и только одноэлементное) множество $A$ может удовлетворять условиям, то всё нормально. Для каждого одноэлементного $A$ алгоритм вычисления $A(x)$ существует! Вас смущает, что мы не можем вывести этот алгоритм из функции $f$?! Не беда, не можем, и ладно, в задаче этого не требуется. Надо лишь доказать, что алгоритм вычисления $A(x)$ существует, а уж какой он именно --- дело десятое!!!

Вот Вы приводите примеры: $A = \{ x_1 \}$ и $A = \{ x_2 \}$ при $x_1 \neq x_2$ и функцию $f$, которая годится для обоих множеств. Так ну и что из этого? Нам $A$ дано в условии! Мы не знаем, какое оно именно, но, рассуждая логически, пришли к выводу, что либо такое, либо такое. Но ведь в обоих случаях $A(x)$ вычислима! Отсюда вывод: $A(x)$ действительно вычислима. Как именно мы будем вычислять $A(x)$, сказать, имея перед собой только функцию $f$, невозможно. Но в обоих случаях мы как-то будем это делать и этого достаточно. В задаче требуется доказать существование алгоритма, вычисляющего $A(x)$, а не найти этот алгоритм.

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

Вот похожая задача из физики. Тело кинули горизонтально с высоты $h$, найти время падения. Мы не знаем ни направления, в котором кинули тело, ни его начальную горизонтальную скорость. Мы не можем из условий задачи вывести, куда упало тело, но нам этого и не требуется. А для вычисления времени падения условий задачи достаточно!

Здесь та же ситуация.

[Dandan]

Еще раз сформулирую вопрос Руста. Для фиксированной f может быть некоторое множество различных A, для которых выполняется свойство f (пример был приведен). Что нужно показать? Что в этом множестве любое A вычислимо или что найдется некоторое A, которое вычислимо? Или нам по условию дано, что существует ровно одно такое A?

[Руст]

На самом деле здесь кроме неопределённости из-за неоднозначности определения есть ещё другая сторона - не вычислимости из-за того, что для вычисления значения A(x) требуется определение значений f(x1,...,xm) по сути по всему множеству, а мы не можем определит даже, что оно определено во всем множестве. Это подобно тому, что обсуждалось о примитивно рекурсивных функциях, значение которых равно 1, если верна некоторая гипотеза и 0 иначе. Я такие определения функций не принимаю как рекурсивные. Уже хотя бы по этой причине не хочу принимать участие в бессмысленных спорах.

[Dandan]

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

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

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

На самом деле здесь кроме неопределённости из-за неоднозначности определения есть ещё другая сторона - не вычислимости из-за того, что для вычисления значения A(x) требуется определение значений f(x1,...,xm) по сути по всему множеству, а мы не можем определит даже, что оно определено во всем множестве. Это подобно тому, что обсуждалось о примитивно рекурсивных функциях, значение которых равно 1, если верна некоторая гипотеза и 0 иначе. Я такие определения функций не принимаю как рекурсивные. Уже хотя бы по этой причине не хочу принимать участие в бессмысленных спорах.

не ну тут всё-таки немного другая ситуация. Если поставить вопрос, что для вычислимой f всегда существует вычислимое A, то по-моему всё довольно корректно.

[Руст]

Dandan писал(а):

не ну тут всё-таки немного другая ситуация. Если поставить вопрос, что для вычислимой f всегда существует вычислимое A, то по-моему всё довольно корректно.

Первоначапьный вопрос включает и такую ситуацию. Например, вычислимая функция определяется таким образом. $f(x_1,x_2)=0$ если вывод с номером (все выводы можно нумеровать) $x_2$ не доказывает гипотезу Римана, иначе $f(x_1,x_2)=1+x_2%2$. Тогда для определения возможных вариантов A(x) фактический надо знать верна ли гипотеза Римана или выводима ли она из используемых систем аксиом.