Верещагин, Шень "Вычислимые функции" решение задач

[AlexeyKh]

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

стр19 №23
Некоторое множество S натуральных чисел разрешимо. Разложим все числа из S на простые множители и составим множество D всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество D разрешимо?

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

[mihaild]

Посмотрите на теорему 3, и попробуйте переделать ее так, чтобы вместо проекции получалось указанное преобразование $S \to D$.

[AlexeyKh]

Получается, что дополнение D будет перечислимо, т.к. будет являться проекцией такого разрешимого множества $Q=\left\lbrace <x,y> \right\rbrace$, где $x \in S$, а y не является множителем x.

Следовательно, D разрешимо.

[mihaild]

AlexeyKh в сообщении #1116156 писал(а):

разрешимого множества $Q=\left\lbrace <x,y> \right\rbrace$, где $x \in S$, а y не является множителем x

Неправда. Из того, что $y$ не делит какое-то число из $S$, не следует, что оно не делит никакое числа из $S$.

[AlexeyKh]

Действительно, неправда.

И все-таки, не могу понять - будет D разрешимым или нет? Конструктивные доказательства перечислимости дополнения D разбиваются о то, что необходимо перебирать все числа из S. Как доказать неперечислимость, кроме противоречия диагональной функции, я вообще не знаю, а разрешающая функция для S и перечисляющая для D с диагональной функцией не связанны.

[mihaild]

Можете ли вы построить перечислимое неразрешимое множество, состоящее только из простых чисел?

[AlexeyKh]

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

[mihaild]

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

[AlexeyKh]

Не знаю как построить такую нумерацию. В теореме 6 приводится такое построение нумерации:
Запишем все программы, вычисляющие функции одного аргумента, в вычислимую последовательность p 0 , p 1 , . . . (например, в порядке возрастания их длины). Положим U (i, x) равным результату работы i-ой программы на входе x.
Будь у нас разрешающий алгоритм для самопременимых программ, можно было бы с его помощью определять: ставить программу на простое место, или нет. Но такого алгоритма не существует.

mihaild в сообщении #1116258 писал(а):

И дальше используйте конструкцию аналогичную теореме 3, только вместо построения пары по числу стройте число, которое делится на данное простое.

Вы имеете ввиду разрешимое множество $Q=\left\lbrace <x,y> \right\rbrace$, где $x \in S$, а y - простой делитель? Но проекциями этого множества будут S и D.

[mihaild]

AlexeyKh в сообщении #1116353 писал(а):

Будь у нас разрешающий алгоритм для самопременимых программ, можно было бы с его помощью определять: ставить программу на простое место, или нет.

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

AlexeyKh в сообщении #1116353 писал(а):

Вы имеете ввиду разрешимое множество $Q=\left\lbrace <x,y> \right\rbrace$, где $x \in S$, а y - простой делитель?

Теорема 3 позволяет из перечислимого множества $A$ сделать разрешимое множество $B$ такое что $x \in A \Leftrightarrow \exists y(\left<x, y\right> \in B)$.
Попробуйте аналогично из перечислимого множество $S$ простых чисел сделать разрешимое множество $D$ такое, что $x \in S \Leftrightarrow \exists y(y \in D \land x \vline y)$ (подсказка: при построении множества пар мы записывали в пару время работы; куда можно его записаь в данном случае?).

[AlexeyKh]

mihaild в сообщении #1116367 писал(а):

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

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

mihaild в сообщении #1116367 писал(а):

Теорема 3 позволяет из перечислимого множества $A$ сделать разрешимое множество $B$ такое что $x \in A \Leftrightarrow \exists y(\left<x, y\right> \in B)$.
Попробуйте аналогично из перечислимого множество $S$ простых чисел сделать разрешимое множество $D$ такое, что $x \in S \Leftrightarrow \exists y(y \in D \land x \vline y)$ (подсказка: при построении множества пар мы записывали в пару время работы; куда можно его записаь в данном случае?).

Возьмем множество $Q=\left\lbrace<x,y>\right\rbrace$, где $x\in S$ и x появляется за время $y/x$. D будет проекцией Q, а значит - D перечислимо. Для разрешимости D построим разрешающий алгоритм $d(y)=\left\{ \begin{array}{rcl} &1 , \exists x(<x,y> \in Q \wedge x\mid y)& \\ &0 , \neg (\exists x(<x,y> \in Q \wedge x\mid y))& \\ \end{array} \right.$
Построить бы по аналогии обратное преобразование (от D к S), но не получится: d(y) всегда будет останавливаться т.к. множество делителей y конечно, а множество чисел делимых на данное бесконечно.

[mihaild]

AlexeyKh в сообщении #1116688 писал(а):

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

Конструкция Поста - это про множество, дополнение которых не содержит бесконечных подмножеств? Нет, она тут не нужна.

Пусть у вас есть вычислимая инъекция $f: \mathbb{N} \to A \subset \mathbb{N}$. Как соотносятся разрешимость/перечислимость $B$ и $f(B)$?

AlexeyKh в сообщении #1116688 писал(а):

Возьмем множество $Q=\left\lbrace<x,y>\right\rbrace$, где $x\in S$ и x появляется за время $y/x$. D будет проекцией Q

Нет, так не получится. Представьте, что $S = \{3\}$ и тройка появляется за $2$ шага. Тогда ваше $D$ будет включать $6$, хотя $2|6$ и $2 \notin S$.

[AlexeyKh]

mihaild в сообщении #1116698 писал(а):

Пусть у вас есть вычислимая инъекция $f: \mathbb{N} \to A \subset \mathbb{N}$. Как соотносятся разрешимость/перечислимость $B$ и $f(B)$?

$B$ перечислимо $\Rightarrow f(B)$ перечислимо (перечисляющий алгоритм $f(B)$ запускает перечисляющий алгоритм $B$ и для каждого напечатанного им числа $x$ печатает $f(x)$ исключая повторяющиеся)
$f(B)$ перечислимо $\Rightarrow B$ перечислимо (запускаем алгоритм перечисляющий $f(B)$, для каждого напечатанного числа $x$ запускаем перебор всех натуральных чисел, печатаем те, для которых $\exists n(n \in \mathbb{N} \wedge f(n) = x)$)
$B$ вычислимо $\Leftrightarrow f(B)$ вычислимо (для доказательства по разрешающему алгоритму строим перечисляющие само множество и его дополнение)

mihaild в сообщении #1116698 писал(а):

Нет, так не получится. Представьте, что $S = \{3\}$ и тройка появляется за $2$ шага. Тогда ваше $D$ будет включать $6$, хотя $2|6$ и $2 \notin S$.

Не понял, что из себя должно представлять $D$. Оно должно включать все числа, делимые на числа из $S$ и только на них?
Тогда представим в общем виде: $Q = <x,y> (x \in S \wedge x|y)$ и $y$ делится на все числа напечатанные перечисляющим алгоритмом $S$ за время $f(x,y)$ и только на них. Но могут быть такие $y$, у которого все делители в $S$, но время печати одного из них больше $f(x,y)$(в не зависимости от того, как зададим эту функцию). В таком случае, проекция $Q$ будет содержат не все числа, делимые на числа из $S$ и только на них.

[mihaild]

AlexeyKh в сообщении #1116969 писал(а):

$B$ вычислимо $\Leftrightarrow f(B)$ вычислимо (для доказательства по разрешающему алгоритму строим перечисляющие само множество и его дополнение)

И как же вы будете вычислять дополнение $B$? Впрочем, я сформулировал немного не ту задачу, что хотел (эта уже почти эквивалентна исходной получилась).
Правильно так: $A$ разрешимо, $f$ - вычислимая биекция между $\mathbb{N}$ и $A$. Как соотносятся перечислимость/разрешимость $B$ и $f(B)$?

AlexeyKh в сообщении #1116969 писал(а):

Не понял, что из себя должно представлять $D$.

$D$ должно быть таким, чтобы множество делителей входящих в него чисел, совпадало с $S$.

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

[AlexeyKh]

mihaild в сообщении #1116973 писал(а):

И как же вы будете вычислять дополнение $B$?

Вы правы, никак. Выходит, что у меня ошибочка и с $f(B)$перечислимо $\Rightarrow B$перечислимо (в случае $f(x) \in f(B), x \notin B $ может напечататься $x$).

mihaild в сообщении #1116973 писал(а):

Правильно так: $A$ разрешимо, $f$ - вычислимая биекция между $\mathbb{N}$ и $A$. Как соотносятся перечислимость/разрешимость $B$ и $f(B)$?

С биекцией все проще:
$B$ перечислимо/разрешимо $\Leftrightarrow f(B)$ перечислимо/разрешимо.
А разве может существовать биекция между неравномощными множествами? (или $A$ уже не собственное подмножество $\mathbb{N}$)

mihaild в сообщении #1116973 писал(а):

Попробуйте аналогично построить из множества $S$ множество чисел такое, чтобы для каждого числа $x$ из $S$ в $D$ было ровно одно число, делящееся на $x$ - и чтобы при этом можно было проверять принадлежность чисел $D$ (т.к. для этого нужно будет запускать перечисление $S$, то нужно каким-то образом в элементах $D$ закодировать не только сами элементы $S$, но и время их перечисления).

$Q=<x,y>$ - $x$ появляется за ровно $t=\log_{x}{y}$ шагов (т.е. $y = x^t$)


У меня появилось такое рассуждение(далее названия классов из исходного условия):
Надо выделить подмножество дополнения $S$: $S''\subseteq S'$ в которое будут входит все числа не имеющие общих простых делителей с числами из $S$.
$S''$ перечислимо $\Leftrightarrow D'$ перечислимо.
Но о перечислимости $S''$ нам ничего неизвестно. Получается, что в общем случае нельзя сказать, что $D$ разрешимо или нет.