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

[mihaild]

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

А разве может существовать биекция между неравномощными множествами? (или $A$ уже не собственное подмножество $\mathbb{N}$)

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

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

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

Почти. Только вам нужно множество чисел, а не пар чисел, какое оно получится?

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

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

Но о перечислимости $S''$ нам ничего неизвестно.

Да, перечислимость $S^{\prime\prime}$ эквивалентна разрешимости $D$. Но, разумеется, "ничего не известно" не является доказательством.

[AlexeyKh]

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

Почти. Только вам нужно множество чисел, а не пар чисел, какое оно получится?

Множество таких $y = x^t$, где $x$ печатается ровно за $t$ шагов. (разрешающий алгоритм - разбиваем $y$ на множители - должен получится один единственный $x$, запускаем перечисляющий алгоритм на $\log_x y$ шагов, если напечатался $x$ - разрешающй алгоритм выводит 1, иначе 0)

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

Таким образом, вопрос "для любого ли разрешимого $S$ множество $D$ разрешимо" эквивалентен вопросу "любое ли перечислимое множество простых чисел разрешимо".

Не понял как получился такой переход.

А можно сказать так: из разрешимости $S$ следует разрешимость $D$ тогда и только тогда, когда между ними есть биекция? В качестве примера того, что биекция будет не всегда можно привести несколько разных $S$, которым соответствует одно $D$ ($S_1=\left\lbrace 6 \right\rbrace , S_2 = \left\lbrace 4, 9 \right\rbrace, D=\left\lbrace 2, 3\right\rbrace$).

[mihaild]

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

Не понял как получился такой переход.

Вы показали, что для любого разрешимого $S$ получается перечислимое $D$, и что для любого перечислимого $D$ существует разрешимое $S$.
1) покажите, что если любое перечислимое множество простых чисел разрешимо, то для любого разрешимого $S$ получается разрешимое $D$
2) покажите, что если существует перечислимое неразрешимое множество простых чисел, то существует разрешимое $S$, для которого получается неразрешимое $D$

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

А можно сказать так: из разрешимости $S$ следует разрешимость $D$ тогда и только тогда, когда между ними есть биекция?

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

[AlexeyKh]

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

1) покажите, что если любое перечислимое множество простых чисел разрешимо, то для любого разрешимого $S$ получается разрешимое $D$

По моему, тут тавтология получилась: "Если любое перечислимое множество простых чисел разрешимо, то перечислимое множество простых чисел $D$ разрешимо".

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

2) покажите, что если существует перечислимое неразрешимое множество простых чисел, то существует разрешимое $S$, для которого получается неразрешимое $D$

Теперь я кажется понял схему доказательства: "Для любого перечислимого $D$ существует разрешимое $S$, а значит если существует перечислимое неразрешимое $D$, то и для него существует разрешимое $S$"
Остается доказать существование перечислимого неразрешимого множества простых чисел $D$. Я попробовал сделать это двумя способами:

1) Есть биекция между множеством натуральных и простых чисел $f$ и есть неразрешимое множество натуральных чисел $A$ (множество номеров самоприменимых программ).
Можно построить перечислимое неразрешимое множество простых чисел $D = f(A)$, если бы существовало перечислимое дополнение $D'$, то с его помощью можно было бы построить перечислимое дополнение для $A$: $f(D') = A'$. Следовательно перечислимого дополнения для $D$ не существует.

2) Построим перечислимое множество простых чисел $D$ такое, чтобы перечислимого множества всех простых чисел не входящих в $D$ не существовало.
Для этого поместим в $D$ по элементу из каждого бесконечного перечислимого множества простых чисел (принцип построения, как у простого множества Поста).
Допустим, дополнение такого $D$ перечислимо функцией $f$, тогда можно построит функцию $f'$ запускающую $f$ и печатающую только простые числа из вывода $f$. Такая функция напечатает все простые числа не входящие в $D$. Функции $f'$ не существует (по построению $D$), следовательно дополнение $D$ не перечислимо.

Получается, что для любого счетного множества существует неразрешимое подмножество?

[mihaild]

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

По моему, тут тавтология получилась: "Если любое перечислимое множество простых чисел разрешимо, то перечислимое множество простых чисел $D$ разрешимо".

Тут и предполагалось тривиальное утверждение.

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

Есть биекция между множеством натуральных и простых чисел $f$

Тут нужно потребовать вычислимости этой биекции (иначе у вас получится, что в любом счетном множестве есть перечеслимое неразрешимое подмножество, что неправда).
(а нужно ли требовать вычислимости $f^{-1}$?)

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

Для этого поместим в $D$ по элементу из каждого бесконечного перечислимого множества простых чисел (принцип построения, как у простого множества Поста).

Да, так тоже можно, но это из пушки по воробьям (вообще, после построения множество с каким-то свойством про вычислимость, другие множества с аналогичными свойствами обычно проще строить через вычислимые биекции)

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

Получается, что для любого счетного множества существует неразрешимое подмножество?

Это очевидно просто из мощностного аргумента (перечеслимых множеств счетно, а подмножеств счетного множества - несчетно).

В итоге, как выглядит $S$, для которого $D$ неперечислимо?

[AlexeyKh]

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

а нужно ли требовать вычислимости $f^{-1}$?

$A\subset \mathbb{N}$ - перечислимое неразрешимое множество, $f: \mathbb{N} \to B$ - инъекция.
Докажем, что дополнение множества $C = f(A)$ неперечислимо:
С помощью алгоритма перечисляющего $C'$ построим алгоритм перечисляющий $A'$. Для этого запустим параллельно перечисление $C'$ и прообразов $f$, раз в некоторое количество шагов будем проверят пересечение этих множеств, если пересечение не пусто, то $\exists n \in \mathbb{N} (f(n) \in B' \wedge n \in A')$. Печатаем такие $n$.

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

В итоге, как выглядит $S$, для которого $D$ неперечислимо?

Берем вычислимую инъекцию $f: \mathbb{N} \to P$ ($P$ - множество простых чисел). С помощью $f$ из перечислимого неразрешимого множества простых чисел (например множества номеров самоприменимых программ) строим перечислимое неразрешимое $D \subset P$. По $D$ строим разрешимое $S$: разрешающий алгоритм на входе $i$ разлагает $i$ на множители, если получился только один множитель $x$ (если больше - печатаем 0), запускаем алгоритм перечисляющий $D$ на $\log_x{i}$ шагов. Если за это время напечатался $x$ - печатаем 1, иначе - 0.

[AlexeyKh]

стр14 №8
Даны два пересекающихся перечислимых множества $X$ и $Y$ . Дока-
жите, что найдутся непересекающиеся перечислимые множества $X' \subset X$ и $Y' \subset Y$ , для которых $X' \cup Y' = X \cup Y$.

Первой наивной идеей было: $X' = X, Y' = Y \setminus (X \cap Y)$, но разность множеств может не быт перечислимой.

Вторая идея - в качестве $X'$ взять разрешимое подмножество $X \cup Y$. $Y' = (X \cup Y) \setminus X'$ ($Y'$ будет перечислимо, т.к. вычитаемое множество разрешимо).
Но, как задать $X'$? Пусть $X'$ состоит из одного единственного элемента из $X$ Разрешающий алгоритм $X'$ запускает перечисляющий алгоритм $X$ и сравнивает свой вход с первым числом, напечатанным перечисляющим алгоритмом. Но это не сработает, если $X$ - пустое множество.

[mihaild]

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

$Y' = (X \cup Y) \setminus X'$

Только тут $Y^\prime$ не обязательно будет подмножеством $Y$.

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

Но, как задать $X'$?

Т.к. вы требуете только $X^\prime \subseteq X$, то можно взять $X^\prime = \varnothing$, но это, естественно, не будет ответом в общем случае.

Подсказка: вообще говоря, $X^\prime$ должно зависеть от $Y$ (а $Y^\prime$ - от $X$). Как, например, можно выбросить часть элементов из $X$ так, чтобы все выброшенные точно принадлежали $Y$, и при этом оставшееся множество было перечислимым?

(Оффтоп)

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

[AlexeyKh]

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

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

$Y' = (X \cup Y) \setminus X'$

Только тут $Y^\prime$ не обязательно будет подмножеством $Y$.

Я неправильно написал, должно быть так: $X' = X, Y' = Y \setminus (X \cap Y)$

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

Подсказка: вообще говоря, $X^\prime$ должно зависеть от $Y$ (а $Y^\prime$ - от $X$). Как, например, можно выбросить часть элементов из $X$ так, чтобы все выброшенные точно принадлежали $Y$, и при этом оставшееся множество было перечислимым?

Единственный способ выбросить часть элементов из множества, который я знаю, это взять его пересечение с другим множеством. Чтобы все выброшенные элементы принадлежали $Y$, надо пересечь $X$ с некоторым подмножеством дополнения $Y$. Не знаю, как получить такое множество.

[mihaild]

AlexeyKh, про дополнения тут думать достаточно бесполезно (они могут быть неперечислимы).

В данном случае про перечислимые множества можно попробовать думать как про алгоритмы, которые работают и время от времени выдают числа. Каждый раз, когда один из алгоритмов выдает очередное число, вам нужно решить, куда его класть - в $X^\prime$ или в $Y^\prime$, если это число еще не было ранее записано ни в одно из множеств. Причем числа, которые алгоритм, перечисляющий $X$, не выдает, нужно класть в $Y^\prime$, которые не выдает $Y$ - в $X^\prime$, а те, которые выдает и тот, и другой - куда угодно (но только в какое-то одно). Как это можно было бы сделать?

Или, возможно, легче будет на примере? Скажем, $X$ - это машины, останавливающиеся на входе $0$, $Y$ - это машины, останавливающиеся на входе $1$. Как их можно было бы разбить перечислимым образом?

[AlexeyKh]

Получается так:
Перечисляющий алгоритм $X'$ запускает параллельно перечисляющие алгоритмы для $X$ и $Y$. Когда на шаге $i$ перечисляющий $X$ печатает число, ищем его среди напечатанных перечисляющим $Y$ за $<i$ шагов. Если не нашли - печатаем.
Для перечисляющего алгоритма $Y'$ поступаем аналогично, но просматриваем $X$ на $\leqslant i$ шагов (на случай, если перечисляющие алгоритмы $X$ и $Y$ напечатают одно и то же число одновременно).

Правильно?

[mihaild]

Да, всё так.