Как перечислить все кодовые строки перечисл. подмножеств?

[Alex_semenov]

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

Можно ли (и как) перечислить все кодовые строки всех перечислимых подмножеств $\mathbb{N}$?

Кодовая строка для подмножества $B\subseteq \mathbb{N}$ это бесконечная цепочка в бинарном алфавите $0$ и $1$, такая, что $n$-тый символ цепочки равен $1$, если $n\in B$ и $0$, если $n \notin B$. Например, кордовая строка подмножества простых чисел:

1 2 3 4 5 6 7 8 9 10 11 12 13 . . .
0 1 1 0 1 0 1 0 0 0 1 0 1 . . .

Надо предъявить алгоритм построения бесконечной вправо и вниз таблицы кодовых строк для всех перечислимых подмножеств. Так как не все перечислимые подмножества разрешимы, то в некоторых разрядах, разумеется, допускаются "пробелы" (обозначим _ ) означающие, что на данном $n$ полуразрешающая процедура не определена. Например:

. . . 0 1 _ 0 0 0 0 0 1 1 0 1 0 _ 0 0 1 . . .

Попытка решения.

Сначала идея решение для одной, некоторой кодовой строки. Допустим, у нас уже есть полуразрешающая процедура $P_{i}(x)$ для i-того подмножества $\mathbb{N}$, которая печатает все $1$ и некоторые $0$ (либо зацикливается). Тогда перечисляя $\mathbb{N}:0,1,2,3 . . . n . . . $ и подавая $n$ на вход $P_{i}(x) $, печатаем в $n$-ую позицию кодовой строки, ее выход. Те позиции $n$, в которых $P_{i}$ зациклилась, остаются "пока" ненапечатанным. Все программы (машины) запускаются в режиме разделения по шагам:

Первый цикл: делается первый шаг $P_{i}(0) $
Второй цикл: делаем второй шаг $P_{i}(0) $, перцевый шаг $P_{i}(1) $
Третий цикл: делаем третий шаг $P_{i}(0) $, второй шаг $P_{i}(1) $, первый $P_{i}(2) $
. . .
n-тый цикл (при условии что никакая из запущенных программ пока не остановилась):
делаем n-тый шаг $P_{i}(0)$, $n-1$ шаг $P_{i}(1) $, . . . , первый шаг $P_{i}(n) $.

Как теперь построить весь список?
В принципе так же циклически теперь и по строкам.
Но нужно эффективное перечисление программ (машин) указанного вида:

$P_{0}(x), P_{1}(x), P_{2}(x) . . .$

Просто так перечислять некоторые машины Тьюринга не получится. Нам нужно чтобы все они получив на вход $n$ печатали только $1$, $0$ или зацикливались.
Идея как это сделать.
Мы перечисляем все возможные машины Тьюринга, но с двумя фиксированными терминальными состояниями (на которой программа останавливается) : $q_{0}$ и $q_{1}$. Теперь, если любая взятая нами машина, получив на вход n, остановилась в состоянии $q_{1}$, мы считаем что $n\in B_{i}, B_{i}\subseteq \mathbb{N}$, если программа останавливается на $q_{0}$, то $n\notin B_{i}$. То же, что осталось на ленте (результат вычислений) - это нас не беспокоит. Это промежуточные данные.
Некоторые программы будут всюду определены, другие только зацикливаться, трети печатать только $1$ и зацикливаться, трети только $0$ и зацикливаться, но мы таким образом получим бесконечную таблицу где представлены все кодовые строки всех перечислимых подмножеств $\mathbb{N}$
Задача решена?

Если данное решение неверно то есть другое решение?
Может другое решение проще?
Спасибо!

[Alex_semenov]

Я прошу прощения. Ошибся в терминологии.
Термин "кодовая строка" здесь неверный "синоним" характеристической последовательности.
Цитата:

Мы знаем, что множество последовательностей нулей и единиц равномощно множеству подмножеств натурального ряда (каждому подмножеству соответствует его "характеристическая последовательность", у которой единица стоя на местах из этого подмножества).

стр. 31 Н.К. Верещагин, А. Шень. "Начала теории множеств" МЦНМО, 2002 г.

По-английски Characteristic sequence

[_hum_]

А что вы подразумеваете под перечислением? Обычное определение (перечислимое множество как множество значений некоторого алгоритма) не проходит, ведь ваши "кодовые последовательности" вроде ж не являются конструктивными объектами...

[Alex_semenov]

Первое попавшееся мне определение:

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

(ссылки здесь запрещены?)

Вы считаете что потенциально бесконечная строчка из нулей и единиц согласно этого определения неконструктивна? Скажем, характеристическая последовательность для множества четных чисел:

10101010101010. . . .

Существует достаточно простая даже не машина Тьюринга, а конечный автомат, который может печатать такую последовательность. Такой автомат вполне конструктивный объект, который имеет описание конечной длины. Я ведь не хочу актуально получить эту характеристическую строку. Но потенциально она существует в виде конкретной машины.
Я не вижу тут большой проблемы.

По идее, данная задача должна быть вполне банальной. И по идее не должна была вызывать затрудняй. Я сильно удивился, когда обнаружил что не все так просто (и я до сих пор подозреваю что все-таки есть решение куда проще! Например, просто брать последний символ на ленте и все).
В классическом доказательстве проблемы остановки вы точно так же перечисляете все вычислимые функции при всех возможны входах, когда строите доказательство диагональным методом. Вы ведь там подаете на вход универсальной машины номер машины $n$ и ее вход $m$:

$U(n,m) = M_{n}(m)$

Разумеется, никто актуально строит эту бесконечную вправо и вниз таблицу не будет. Максимум - пытаются (опять же только потенциально) построить анти-диагональ (которая тоже "малоконструктивна" если на то пошло), вводят разрешающую процедуру $ H (n, m) $ без которой эту анти-диагональ не построить (не получить алгоритм для ее построения) и приходят к противоречию из чего выводят что $ H(n, m) $ не существует.
Так же?
Но в процессе доказательства, по сути, конструируется программа (машина), которая МОЖЕТ построить (перечислить) ту самую бесконечную таблицу результатов вычислений ВСЕХ вычислимых функций. Вполне конструктивно строится! Все этапы построения такой машины вполне осуществимы кроме одного.
Мне нужно то же самое. Но с небольшой вариацией.
И в моем случае опять же, понадобится невозможна процедура $ H (n, m) $. Без нее никак. Но вместо выхода $M_{n}(m) $ на пересечении столбцов и строк мне нужно напечатать всего лишь "1" или "0". Всего -то!
Задача даже проще.
Разница задач мне сначала показалась чисто "косметической". Прямого примера ее решения я не нашел. Вытянул с десяток учебников (благо в сети их пруд пруди) но все они в основном повторяют друг друга. И это понятно. Показывается простейшее, наиболее конструктивное доказательство проблемы остановки. Без экзотики с какими-то характеристическими последовательностями.
Но мне желательно именно так.

В придуманном мною решении меня (пока) сильно смущает последний ход с попыткой занумеровать все возможные машины предикаты, снабжая каждую машину двумя терминальными состояния (не вступаю ли я тут в противоречие с теоремой Райса? Да нет вроде. Я же не сортирую полученные программы по какому-то нетривиальному признаку! Точно так же можно перечислить только примитивно рекурсивные программы, опираясь на их конструктивную особенность, отсутствие оператора минимизации)
Еще одно место для сомнений - способ считывания результата вычислений ("через зад", так сказать).
Если решение все же корректно, то получилось необычным (честно говоря мне нужно было именно обычное решение. Чем обычней, тем лучше. Но я нашел вот такое и нужна теперь верификация от профессионалов).

Обычно говорят что результат вычислений любой машины остается на ленте. Но ведь в большей части способов определении МТ оговаривается не одно, а множество конечных состояний. Более того, в учебниках попадаются примеры машин-предикатов именно такого типа. Предикат заканчивает работу (если заканчивает) в двух разных состояниях. Да-нет. Что на ленте- не важно.
Но насколько такой ход допустим здесь, когда мы эффективно перечисляем все возможные машины?
Для положительного ответа достаточно ли показать, что для всякой "нормальной" машины-предиката (с результатом на ленте) можно построит (продолжить, достроить ее до) машины с двумя терминальными состояниями?

До сих пор я думал что задача всего лишь необычная, но простая. Всего лишь оригинальный вариант вполне типичного доказательства. Я думал что профессионалы на форуме ее корректность либо быстро подтвердят, либо мне быстро укажут где я ошибся. Но вопрос вторые сутки тут "тонет" без вердикта.
Что меня новичка сильно смущает.
Я задал какой-то совсем уж глупый вопрос? Или очень сложный?

Можно хотя бы это узнать?


А о конструктивности "характеристической последовательности" - я думаю ответ: "как посмотреть". Если вас смущает бесконечность этой последовательности (как объекта конструктивного построения), то считайте что мы строим таблицу в которой перечисляются единицы и нули. Однобуквенные слова "1" и "0" - без тени сомнения конструктивные объекты.
То что это двумерная таблица, а не строка - это непринципиально. Для перечисления некого перечислимого множества ведь по сути строится машина, которая будет (может) бесконечно перечислять натуральные числа (образ, прообраз, график), объекты куда более громоздкие чем "1" и "0".
Может я перемудрил с формулировкой задачи?

[_hum_]

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

На всякий случай:
для всякого конечного алфавита $\mathbb{A}$ обозначим через $\mathbb{A}^*$ множество всех конечных цепочек, составленных из символов этого алфавита.
Множество $M\subset \mathbb{A}^*$ называется перечислимым, если существует такой алгоритм $\mathcal{A}:\mathbb{N} \rightarrow \mathbb{A}^*$, что
1) для всякого $n \in \mathbb{N}$, к которому применим этот алгоритм, выполняется $\mathcal{A}(n)\in M $
2) для всякого $s\in M$ существует $ n \in \mathbb{N}$, такой что $\mathcal{A}(n) = s$.

Можете аналогичным образом привести формулировку вашего понимания перечислимости "кодовых последовательностей"?

[Alex_semenov]

_hum_ в сообщении #557656 писал(а):

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

Разумеется. Иначе и быть не может.
Я предлагаю (как мне кажется) простейший способ меня понять.
Возьмите классическое диагональное доказательство проблемы остановки, только вместо некоторой вычислимой функции (машины) $M_{n}(x)$ которая зацикливается или печатает на выход некоторое натуральное $y=f(x)$, здесь должна быть программа-предикат $P_{n}(x)$ который печатает или 1 или 0 или зацикливается.
Вот и все.

Цитата:

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

Не совсем. Вообще говоря меня на самом деле не интересует перечисление именно всех характеристических последовательностей. Меня интересует перечисление одно неперечислимой. Вернее невозможность ее перечислить.

Цитата:

На всякий случай:
для всякого конечного алфавита $\mathbb{A}$ обозначим через $\mathbb{A}^*$ множество всех конечных цепочек, составленных из символов этого алфавита.
Множество $M\subset \mathbb{A}^*$ называется перечислимым, если существует такой алгоритм $\mathcal{A}:\mathbb{N} \rightarrow \mathbb{A}^*$, что
1) для всякого $n \in \mathbb{N}$, к которому применим этот алгоритм, выполняется $\mathcal{A}(n)\in M $
2) для всякого $s\in M$ существует $ n \in \mathbb{N}$, такой что $\mathcal{A}(n) = s$.

Да, это, кажется и есть определение вычислимой функции.
1 Если функция вычислима, ее прообраз перечислим.
2 Если функция вычислима, ее образ перечислим.
Единственное, ваша функция есть некоторое отображение множества натуральных чисел на множество слов в некотором алфавите. Конструктивных объектов в конструктивные.

Цитата:

Можете аналогичным образом привести формулировку вашего понимания перечислимости "кодовых последовательностей"?

Я выше давал определение характеристической последовательности из Верещагина и Шеня. Но я четко понимаю, что это термин теории множеств. То есть определить это не значит вычислить.
В терминах теории множеств для каждого подмножества $\mathbb{N}$ существует характеристическая последовательность из $0$ и $1$. Существует в математическом смысле. Общеизвестный факт что их континуум. И только счетное подмножество таких цепочек "вычислимо" (взял в кавычки потому что процесс вычисления, именно построения любой такой последовательности будет бесконечным, "незаконным", хотя вычисление отдельных позиций этой последовательности - вполне законный вычислительный процесс).
Что значит вычислимая характеристическая последовательность (назовем это так)?
Это значит что для множества $X\subseteq \mathbb{N}$ существует вычислимый предикат $P(x)$:

$P(x)=\left\{\begin{matrix} 1,& & \mathbf{if} x\in X \\ 0, & & \mathbf{if} \notin X \\ \square, & & \mathbf{if} x= \square \end{matrix}\right\ }\ $

"квадрат" означает "не определен" (не знаю как правильно это обозначить). Вообще говоря, если $x$ для предиката не определен, то $x\notin X$. Но теперь мы не можем на этом месте поставить $0$, потому что предикат на этом месте зацикливается (и мы не знаем это он так долго считает $P(x)$ или это действительно навсегда). Если бы проблема остановки решалась то мы поставили бы $0$. Но не судьба.

Яркий пример. Множество всех доказуемых высказываний формальной теории чисел (в некоторой конкретной формализации). Мы можем перечислить все такие высказывания (на геделевом номере всех теорем поставить 1). Мы можем приписать к каждой теореме тильду (не) и напротив геделева номера такой антитеоремы поставить 0. Еще надо поставить 0 напротив бессмысленных слов в алфавите данной теории. Это все - механические процессы. Но еще останутся неопределенные номера. Верно?
То есть для такого подмножества $\mathbb{N}$ существует вычислимая характеристическая строчка примерно такого вида:

0100101010 ... 0_0001... 0_10...

Я собираюсь перечислять все подобные строчки.

У меня вот какая идея возникла тут по ходу. Смотрите. Мы берем классическую процедуру из диагонального доказательства проблемы остановки с универсальной функцией $U(n,x)$ (сдираем все рассуждения под чистую!) и продолжаем ее таким образом:

$P_{i}(x)=\left\{\begin{matrix} 0, & & \mathbf{if}\: U(i,x)=0\\ 1, & & \mathbf{if}\: U(i,x)>0\\ \square, & & \mathbf{if}\: U(i,x)=\square \end{matrix}\right\ }\ $

Что мы в итоге получим? Можно ли будет сказать что перебрав все номера машин на бесконечности так построенной бесконечной таблице из 0 и 1 будут представлены все вычислимые характеристические последовательности? (строка таблицы - одна какая-то последовательность). Там где-то будет последовательность для простых числе (вообще бесконечное число раз). Но это случай всюду определенной последовательности. Но мы перечисляем все последовательности без разбора поэтому многие где-то зациклятся. Где-то должна быть последовательность множества теорем той самой формализации теории чисел.
И в любой момент времени мы конечно не можем знать на какой позиции какой предикат зациклился. Мы видим что какая-то машина в какой-то ячейке таблицы не остановилась, но остановятся она когда-нибудь, мы механически выяснить не можем за конечное число шагов.
Поэтому не можем построить и анти-диагональ, которая бы представляла бы собой характеристическую последовательность некого неперечислимого подмножества.

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

[_hum_]

Извините, не осилил понять весь написанный текст. Можно вас попросить записать коротко и ясно, что, по-вашему, означает высказывание "множество кодовых последовательностей перечислимо", в формате
"будем говорить, что множество $B\subset\{0,1\}^*$ "кодовых последовательностей" перечислимо, если [окончание формулировки].

[Alex_semenov]

Я не говорил того, что множество всех "кодовых строк" (для всех подмножеств натурального ряда) перечислимо.

(пусть будут "кодовые строки". "Характеристическая последовательность" - название, о которое постоянно спотыкаешься, если быстро произносить).

Множество таких кодовых строк как раз не то что не перечислимо каким-то образом. Оно вообще несчетно. Их континуум.
Я спрашивал (цитата):

Можно ли (и как) перечислить все кодовые строки всех перечислимых подмножеств?

То есть в множестве таких строк (которых континуум) есть строки для перечислимых подмножеств. Именно о перечислении всех таких строк и ставился вопрос.

-- 09.04.2012, 07:43 --

Похожий вопрос попроще:

Можно ли (и как) перечислить все перечислимые подмножеста $\mathbb{N}$?

[_hum_]

Цитата:

Я не говорил того, что множество всех "кодовых строк" (для всех подмножеств натурального ряда) перечислимо.

Я тоже не говорил, что $B\subset\{0,1\}^*$ - это множество всех кодовых строк.

Ладно, давайте в более подробном варианте:
"будем говорить, что множество $B\subset\{0,1\}^*$ кодовых строк перечислимых множеств натуральных чисел перечислимо, если [ваше окончание формулировки]."

(Я пытаюсь от вас услышать определение перечислимости для множества, состоящего из бесконечных цепочек.)

[Alex_semenov]

_hum_ в сообщении #558280 писал(а):

Цитата:

Я не говорил того, что множество всех "кодовых строк" (для всех подмножеств натурального ряда) перечислимо.

Я тоже не говорил, что $B\subset\{0,1\}^*$ - это множество всех кодовых строк.

Стоп. Я здесь тормознул, вовремя не сообразил, и поэтому эскалация взаимного непонимания продолжается. Вот эта фраза $B\subset\{0,1\}^*$ в вашей заготовке для меня ОДНОЗНАЧНО означает, что $B$ есть некоторое подмножество такого множества:

0,1, 10, 11, 100, 101, 110, 111, 100 . . . 101010110001010101 . . . .

То есть. Множества конечных слов в алфавите 0,1. Но я с самого начала говорил о бесконечных характеристических последовательностях. Коль вы перешли от бесконечных к конечным цепочкам, то мы тут совсем друг друга перестали понимать.

Цитата:

Ладно, давайте в более подробном варианте:
"будем говорить, что множество $B\subset\{0,1\}^*$ кодовых строк перечислимых множеств натуральных чисел перечислимо, если [ваше окончание формулировки]."

(Я пытаюсь от вас услышать определение перечислимости для множества, состоящего из бесконечных цепочек.)

Да я понимаю, что нужно для начала разобраться с базой. Но вы не туда вообще пошли.

Блин, неужели все так сильно запущено (у меня, разумеется)?

Я прошелся по вашим ответам выше еще раз и пытаясь понять где корень непонимания. Вот правильная догадка с вашей стороны, которую я ЗЛОСТНО "пропустил мимо ушей":

_hum_ в сообщении #557656 писал(а):

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

Да, все верно на самом деле. Я не намекаю, я утверждаю. Я говорю, что любая такая бесконечная последовательность - это перечисляющий алгоритм.
Именно перечисляющий. Не какой-то там вообще алгоритм.
Что такое перечисляющий алгоритм?
Это специальным образом зацикленный алгоритм. Внутри его вычисляется вполне "обычная" программа, которая, получая на вход $x$, выдает $y$ если данная вычислимая функция определена на этом $x$. Когда это происходит, $y$ можно выдать, как очередной член перечисления.

Цитата:

то тогда в чем проблема - перечисление всех "кодовых цепочек" в таком случае равносильно перечислению всех алгоритмов.

Вот об этом и был вопрос. Как это надо делать?
Просто так перечислить все подряд алгоритмы?
Прекрасно!
Давайте пробовать!
Когда мы перечисляем в лексикографическом порядке описания всех возможных машин Тьюринга, мы перечисляем все программы вычисляющие некий натуральный $y$ от некоторого натурального $x$.
Это не совсем то что нам нужно. Но ладно. Пускай алфавит ленты 0 и 1.
Что дальше?
Конечно, мы можем "тупо" взять все "обычные" машины Тьюринга, тупо подать каждой на вход пустой $x$ и смотреть что получится. Одни поработают и остановятся. Некоторые зациклятся и будут бесконечно что-то выдавать на ленту. Но это вообще говоря будет промежуточная суета. Для любой произвольно взятой машины, пока она не перешла в конечное состояние, никакая последовательность на ленте не может интерпретироваться нами как результат вычислений. Даже если алфавит ленты те самые 0 и 1, любая строчка на ленте не о чем не говорит. Как отделить промежуточные данные от результата?
Никак!
В чем засада?
Перечисляющие алгоритмы тоже зациклены, но они специальным образом зациклены и мы знаем, что там есть такой этап вычислений (состояние машины), что очередной член перечисляемого множества (если это перечисление некого множества) уже готов. Вычислен. Его нужно допечатать к уже частично готовому результату.
Например, мы перечисляем простые числа и уже перечислили первые 7 членов этого множества.

2, 3, 5, 7, 11, 13, 17

мы подали на вход некому внутреннему "простому" алгоритму число 8 и ждем пока этот внутренний алгоритм остановится. Смотрим ответ. 19. Допечатываем в конец:

2, 3, 5, 7, 11, 13, 17, 19

и так бесконечное число раз.
Вот это то, что нам надо!
Простейший случай, конечно. Но суть такая.
Получаем перечисление некого множества. Потенциально бесконечный объект. Но вполне конструктивный. Потому что есть конечный алгоритм его строящий. Притом зацикленный.
Но не все зацикленные алгоритмы что-то там перечисляют. Они вообще могут на своей ленте сначала напечатать длиннющее слово, а потом стереть чуть ли не до конца, и так может происходить хаотично и бесконечно.

Вот как теперь все-таки перечислить все перечисляющие алгоритмы?
Оставьте пока в покое эти бинарные бесконечные цепочки. Не до их пока! Давайте разберемся с более простым случаем. Промежуточным.
Я вам предлагаю еще раз такую простую задачу:

Как перечислить все алгоритмы, которые перечисляют все перечислимые подмножества натурального ряда?

Эта задача точно имеет решение. Даже такой тупица как я знает ответ. Вы его знаете?

Я вас опять загрузил "кашей"?
Неужели я несу настолько уж несусветную чушь?
"Ни одной знакомой буквы"?

Или у меня слишком много букв?


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

[_hum_]

Alex_semenov, дико извиняюсь, это я ступил. Конечно же, имелось в виду не множество конечных цепочек $\{0,1\}^*$, а множество бесконечных цепочек $\{0,1\}^{\infty}$. Можете теперь, чтобы быстрее достичь понимания (а то очень сложно большие ваши тексты воспринимать) сформулировать:
"будем говорить, что множество $B\subset\{0,1\}^{\infty}$ кодовых строк перечислимых множеств натуральных чисел перечислимо, если [ваше окончание формулировки]".

-- Пн апр 09, 2012 19:57:18 --

Alex_semenov в сообщении #558401 писал(а):

Как перечислить все алгоритмы, которые перечисляют все перечислимые подмножества натурального ряда?

Опираемся на
множество $M\subset \mathbb{N}$ называется перечислимым, если существует такой алгоритм $\mathcal{A}:\mathbb{N} \rightarrow \mathbb{N}$, что
1) для всякого $n \in \mathbb{N}$, к которому применим этот алгоритм, выполняется $\mathcal{A}(n)\in M $
2) для всякого $s\in M$ существует $ n \in \mathbb{N}$, такой что $\mathcal{A}(n) = s$.
Отсюда вытекает, что всякий алгоритм $\mathcal{A}:\mathbb{N} \rightarrow \mathbb{N} $ можно рассматривать как перечисляющий множество своих значений! Таким образом, множество перечисляющих (подмножества в $\mathbb{N}$) алгоритмов в точности совпадает с множеством всех возможных алгоритмов ($\mathbb{N}$ в $\mathbb{N}$)!

[Alex_semenov]

Вариант определения 1:

будем говорить, что множество $B\subset \left \{0,1\right \}^{\infty }$ характеристических последовательностей перечислимых подмножеств натуральных чисел перечислимо, если для каждого $b\in B$ существует множество $X \subseteq \mathbb{N}$ и алгоритм $\mathcal{A}: \mathbb{N}\rightarrow \left \{ 0,1 \right \}$, такой что если $x \in X$, то $\mathcal{A}(x)=1$, если $x\notin X$, то $\mathcal{A}(x)=0$ или не определен.

Обратите внимание. Можно дать вариант определения 2 слабее, заменив выделенное жирным на:

. . . если $x\notin X$, то $\mathcal{A}(x)$ не определен.

То есть в варианте 2 печатаются только единицы. Тогда решение очевидно. Берем любую машину и на том $x$, где она останавливается, печатаем "1". А "0" нигде не печатаем.
Но вопрос как получить вариант 1 с нулями везде где это возможно?

Цитата:

Можете теперь, чтобы быстрее достичь понимания (а то очень сложно большие ваши тексты воспринимать) сформулировать:

Я догадываюсь что сложно. Я пытаюсь. :)

[Alex_semenov]

_hum_ в сообщении #558418 писал(а):

Опираемся на
множество $M\subset \mathbb{N}$ называется перечислимым, если существует такой алгоритм $\mathcal{A}:\mathbb{N} \rightarrow \mathbb{N}$, что
1) для всякого $n \in \mathbb{N}$, к которому применим этот алгоритм, выполняется $\mathcal{A}(n)\in M $
2) для всякого $s\in M$ существует $ n \in \mathbb{N}$, такой что $\mathcal{A}(n) = s$.
Отсюда вытекает, что всякий алгоритм $\mathcal{A}:\mathbb{N} \rightarrow \mathbb{N} $ можно рассматривать как перечисляющий множество своих значений! Таким образом, множество перечисляющих (подмножества в $\mathbb{N}$) алгоритмов в точности совпадает с множеством всех возможных алгоритмов ($\mathbb{N}$ в $\mathbb{N}$)!

Согласен. Спасибо. Это как раз то что я хотел. Из этого легко получить вариант перечисления 2 (см. выше). К примеру, если алгоритм перечисляет:

1, 123343, 2, 45, 32, 671, 1234556663, 5 . . .

то это ведь номера позиции единиц в бинарной цепочке от ее начала. Но как бы еще и с нулями разобраться? Ведь есть разрешимые множества. Если множество разрешимо, значит можно перечислить для его характеристической последовательности не только "1" но и все "0" (следует из теоремы Поста).
Но все множества разрешимы. Есть перечислимые, но неразрешимые. Допустим это некое множество $S$. Его дополнением $ \overline{S}= \mathbb{N}\setminus S$ будет даже не перечислимым (нет перечисляющего алгоритма). Но в самом этом не перечислимом подмножестве $\overline{S}$ может быть некое перечислимое подмножество $ \overline{S}^{ }' \subset \overline{S}$, для которого алгоритм перечисления есть и тогда в характеристической последовательности для $S$ можно поставить не все, но некоторые "0".

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

Alex_semenov в сообщении #557638 писал(а):

ссылки здесь запрещены?

Если не рекламного характера, а по существу вопроса, то разрешены

Alex_semenov в сообщении #558582 писал(а):

Но все множества разрешимы. Есть перечислимые, но неразрешимые.

Совершенно верно! В каких трёх соснах Вы тут запутались?

[_hum_]

Alex_semenov в сообщении #558568 писал(а):

Вариант определения 1:

будем говорить, что множество $B\subset \left \{0,1\right \}^{\infty }$ характеристических последовательностей перечислимых подмножеств натуральных чисел перечислимо, если для каждого $b\in B$ существует множество $X \subseteq \mathbb{N}$ и алгоритм $\mathcal{A}: \mathbb{N}\rightarrow \left \{ 0,1 \right \}$, такой что если $x \in X$, то $\mathcal{A}(x)=1$, если $x\notin X$, то $\mathcal{A}(x)=0$ или не определен.

С вашим определением явно что-то не то - оно фактически является тавтологией.
Наверное вы хотели сказать следующее:
будем говорить, что множество $B\subset \left \{0,1\right \}^{\infty }$ характеристических последовательностей перечислимых подмножеств натуральных чисел перечислимо, если перечислимо множество всех алгоритмов $\mathcal{A}: \mathbb{N}\rightarrow \left \{ 0,1 \right \}$, которые полуразрешают множества, соответствующие характеристическим последовательностям $b\in B$, а именно,
для всякого $m\in \mathbb{N}$ из области применимости алгоритма выполняется $\mathcal{A}(m) = 1\, \Leftrightarrow \, b_m = 1, b \in B$.

Alex_semenov в сообщении #558568 писал(а):

Берем любую машину и на том $x$, где она останавливается, печатаем "1". А "0" нигде не печатаем.
Но вопрос как получить вариант 1 с нулями везде где это возможно?

Alex_semenov в сообщении #558582 писал(а):

Но как бы еще и с нулями разобраться? Ведь есть разрешимые множества. Если множество разрешимо, значит можно перечислить для его характеристической последовательности не только "1" но и все "0"

Тогда лучше поступать несколько по-другому. Опять начать перечислять все возможные алгоритмы $ \mathcal{A}: \mathbb{N}\rightarrow \left \mathbb{N}$, но все их преобразовывать к алгоритму вида $\mathcal{A}': \mathbb{N}\rightarrow \left \{0,1\}$, например, так: $\mathcal{A}'(m) = \min\{1, \mathcal{A}(m)\}$. Тем самым вы перечислите все возможные алгоритмы вида $\mathcal{A}: \mathbb{N}\rightarrow \left \{0,1\}$. А значит, среди них будут и те, что дают нули "там где это только можно":) Только большого смысла в том не вижу, ибо в общем случае для одной и той же характеристической последовательности может быть много таких алгоритмов, ни один из которых не лучше другого (для верности обратного нужно, чтобы во всяком перечислимом множестве содержалось максимальное по включению разрешимое подмножество, а это наверняка неверно).