Разрешимость множества

[Иван_85]

Смотрю лекции НМУ "Вычислимость и логика". В первой лекции дается определение разрешимого множества:
$A$-разрешимо $\Leftrightarrow A \in \mathbb{N}_0 \wedge \exists алгоритм $\mathcal{A}$ такой, что:
1) $\forall x \in \mathbb{N}_0 \;\;\;\mathcal{A}(x)$ останавливается и выдает 0 или 1.
2) $\forall x \in \mathbb{N}_0 \;\;(x \in A \Leftrightarrow \mathcal{A}(x)=1).$

В качестве примера разрешимого множества приводится множество $\{n |\;\; \text{в числе }\pi\text{ есть }n\text{ девяток подряд}\}$.
Объяснение таково. Если в числе $\pi$ есть m девяток подряд то в нем есть и m-1 девятка подряд. Получается, что возможны два случая: данное множество конечно, либо оно равно $\mathbb{N}_0$. Но любое конечное подмножество множества $\mathbb{N}_0$ разрешимо. Также разрешимо и само $\mathbb{N}_0$. Отсюда следует, что данное множество разрешимо.

Но смотрите. Пускай данное множество конечно, то есть $\{n |\;\; \text{в числе }\pi\text{ есть }n\text{ девяток подряд}\} = \{0,1,2,3,4,..., m\}$.
Но тогда алгоритм $\mathcal{A}(m+1)$ никогда не закончится. А для разрешимости данного множества он обязан завершиться через конечное число шагов. Как быть?
Думаю, что $\mathcal{A}(x)$ - это простое вычисление числа $\pi$ до тех пор пока не обнаружатся x девяток подряд. Если возможен другой алгоритм для $\pi$ тогда давайте вместо него возьмем другое иррациональное число в котором будет невозможно предсказать "поведение" девяток - только прямым вычислением.

[Mysterious Light]

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

Я думаю, что имеется в виду следующее:
для любого $m$ существует алгоритм, разрешающий множество $\{1,2,3,\ldots,m\}$
кроме того, само $N_0$ разрешимо.
Утверждение $\exists m\;(\pi\textrm{ содержит не более m девяток подряд})$ может быть либо истинным, либо ложным. Конкретно мы не знаем истинность этого утверждения. Быть может, мы и не можем знать. Но мы знаем, что как в случае истинности (существует $m$ и $m$-элементное множество разрешимо), так и в противном случае (не сущ. $m$ и всё $N_0$ разрешимо) описанное множество будет разрешимо. Отсюда мы заключаем, что это множество разрешимо.
Мы как бы играем на том, что алгоритм вообще может не привязывать к содержанию описанного множества, то есть ему не зачем перебирать цифры, но опирается на "непостижимое" знание того, существует или нет $m$ и чему оно равно. Для меня такие рассуждения кажутся сверх-дикостью, особенно после рассказа Гейтинга, потому что пока мы не знаем истинность вышеописанного утверждения, мы не можем написать алгоритм, который бы мог разрешить множество. А что будет, если такое утверждение не доказуемо и не опровержимо? Мы никогда не сможем написать алгоритм? Но мы же утверждаем, что он существует.

[Maslov]

С формальной точки зрения определение разрешимости не требует предъявления алгоритма для вычисления характеристической функции, достаточно доказательства его существования. Более того, не требуется, чтобы этот алгоритм решал какую-то содержательную задачу, связанную с построением множества $A$ или проверкой принадлежности ему заданного натурального числа (в частности, определял цифры в десятичном разложении $\pi$).

Mysterious Light в сообщении #645048 писал(а):

пока мы не знаем истинность вышеописанного утверждения, мы не можем написать алгоритм, который бы мог разрешить множество. А что будет, если такое утверждение не доказуемо и не опровержимо? Мы никогда не сможем написать алгоритм? Но мы же утверждаем, что он существует.

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

$\mathcal{A}_k(n) = n \leq k~?~1 : 0, k \in \mathbb{N}_0$
$\mathcal{A}_\infty(n) = 1$

Другими словами, разрешающий алгоритм заведомо существует.

[Иван_85]

Maslov, все же я не понимаю.
Пусть $\{n |\;\; \text{в числе }\pi\text{ есть }n\text{ девяток подряд}\} = \{0,1,2,3,4,..., m\}$. Мы имеем право на такое предположение.
Как алгоритм $\mathcal{A}(m+1)$ может за конечное число шагов перебрать бесконечную последовательность цифр? Это же не возможно!

[Mysterious Light]

В указанных Вами предположениях алгоритм, предложенный ЗУ, сделает 2 действия: проверит, что $m+1>m$ и возвратит 0.

(Оффтоп)

P.S. как же бесит, когда мы утверждаем, что что-то существует, но совершенно не можем ничего сказать об этом алгоритме. Мы его даже на числе 100 запустить не можем!
Впрочем, теория построена и она работает. Впоминаются слова: «Работает — не трогай»

[Иван_85]

Mysterious Light, так ладно, другой вопрос.
В этой же лекции говорится, что любое конечное множество $A \in \mathbb{N}_0$ разрешимо. И поясняется, что пусть, например, $A=\{x_1,x_2, ...x_n\}$. Тогда существует простой алгоритм, который перебирает по порядку все натуральные числа для каждого элемента множества $A.$ Но для этого мы должны явно знать это множество, так сказать, поэлементно.
А теперь вопрос: Пусть $B \in \mathbb{N}_0$ и $B$-конечно.
Можно ли считать его разрешимым? Ведь мы не сможем предоставить алгоритм не определяя конкретно множество $B.$

[Mysterious Light]

Общество говорит: можно.

Мы действительно не можем написать алгоритм, если не будем знать множество. По-другому: умение написать алгоритм (в данном случае) полностью соответствует умению записать множество поэлементно. Не знаем, какие элементы в множестве, то не можем записать алгоритм. Однако, множество-то существует, и мы предполагаем его конечным. Значит, существует и алгоритм.

В этом и заключается мой диссонанс: алгоритм существует, а записать его мы не можем.

P.S. Множество $B$ мы всё-таки определяем конкретно. Иное дело, что у нас может не быть эффективного способа определить истинность $x\in B$ для конкретного $x$.

[Maslov]

Иван_85 в сообщении #645095 писал(а):

А теперь вопрос: Пусть $B \in \mathbb{N}_0$ и $B$-конечно.
Можно ли считать его разрешимым? Ведь мы не сможем предоставить алгоритм не определяя конкретно множество $B.$

Еще раз: от нас не требуется представить конкретный алгоритм, от нас требуется доказать, что множество всех алгоритмов содержит, в том числе, такой, который возвращает 1 для натуральных чисел, принадлежащих $B$, и 0 для всех натуральных чисел, не принадлежащих $B$.

Рассмотрим, например, все одноэлементные множества: $\{0\}, \{1\}, \{2\}, ..., \{k\}, ...$
Очевидно, что множество всех алгоритмов содержит, в том числе, такие:
$F_0(n): $ if n = 0 then 1 else 0
$F_1(n): $ if n = 1 then 1 else 0
$F_2(n): $ if n = 2 then 1 else 0
...
$F_k(n): $ if n = k then 1 else 0
...
Таким образом, для любого одноэлементного множества существует алгоритм, вычисляющий его характеристическую функцию, и нам не надо указывать конкретное множество, чтобы быть уверенным в существовании для него такого алгоритма, а следовательно -- в его разрешимости; все одноэлементные множества разрешимы.

Ровно такая же ситуация с другими конечными подмножествами натурального ряда.

Кстати, Вы почему-то не различаете знаки принадлежности и подмножества, обозначая все $\in$
$x \in B$ означает "элемент $x$ принадлежит множеству $B$"
$B \subset \mathbb N$ означает "множество $B$ является подмножеством $\mathbb N$".

[VAL]

Иван_85 в сообщении #644997 писал(а):

Смотрю лекции НМУ "Вычислимость и логика". В первой лекции дается определение разрешимого множества:
$A$-разрешимо $\Leftrightarrow A \in \mathbb{N}_0 \ \dots$

Т.е. $A$ является целым неотрицательным числом?! Не верю!

[Иван_85]

VAL, имелось ввиду $A\subset \mathbb{N}_0.$

[VAL]

Иван_85 в сообщении #645277 писал(а):

VAL, имелось ввиду $A\subset \mathbb{N}_0.$

Теперь верю

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Мат. логика, основания математики, теория алгоритмов»

[nikvic]

Maslov в сообщении #645072 писал(а):

Другими словами, разрешающий алгоритм заведомо существует.

Здесь проходит редут между "классиками" и "конструктивистами". Последние говорят не может не существовать, но отказываются снять двойное отрицание.