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

[Alex_semenov]

Профессор Снэйп в сообщении #558607 писал(а):

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

Я об этом подозревал. Но мало ли как с этим у математиков? Вдруг все так же строго формально?

Цитата:

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

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

Если мы перечислим все машины c номером $z$ ($y=M_{z}(x)$, где $x,y,z \in \mathbb{N} $), подадим на вход им всем все $x$ и при этом как угодно (не важно как) все те $y$, на которых машины остановились, отобразим на множество {$0,1$}, то мы неизбежно получим перечисление всех перечислимых характеристических последовательностей. При этом для каждого разрешимого подмножества найдется и всюду определенная характеристическая последовательность (ни на каком 0 она не зациклится).

Интуитивно кажется: а что же еще?
Но вот обосновать эту интуицию я не могу.
Если она не верна, тогда возникает вопрос, как перечислить все такие последовательности по-другому?

Многословное уточнение.

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

Начнем от хорошо известного.
Я перечисляю все машины Тьюринга в лексикографическом порядке, располагая их "в столбик". Каждой подаю на вход натуральные число: 0, 1, 2, 3. . . То есть каждую еще "клонирую" бесконечное число раз, располагая их по ячейкам вдоль строки и подавая каждой на вход натуральное число. Утрируя, я имею (вернее строю) бесконечную вправо и вниз таблицу, в каждой ячейки которой "находится" некая машина $M_{z}$ получившая на вход номер своего столбца $x$ и вычисляющая $y=M_{z}(x)$. Здесь $x$ - это натуральный вход данной машины и он же номер столбца. Номер строки $z$ - номер машины. Возможно, все это нестрого, но зато наглядно.
Какие-то машины останавливаются, какие-то нет. Те что остановились, выдают "в свою ячейку таблицы" некий натуральный результат $y$.
Все это - классическая схема из учебника.
Теперь смотрим вот на какие нюансы. Все ячейки с некоторым вычислимым $y$ в одной строке таблицы - это перечисление некого натурального множества $Y$ которое есть область значения данной вычислимой функции (которую вычисляет машины с номером $z$). Это просто следует из определения (одного из определений) вычислимой функции.
Давайте чуть изменим алгоритм построения таблицы.
Те ячейки, где программа остановилась, записываем не $y$, а $1$.
Теперь можно сказать, что единицы указывают на номера своих столбцов, вся совокупность которых (номеров) есть результат перечисления нескорого другого перечислимого множества $X$ (теперь это область определения данной вычислимой функции). Это следует из другого определения вычислимой функции.
И смотрите. Мы уже "ненароком" построили и характеристическую последовательность для каждого перечислимого множества.
Но в таком перечислении нет нулей. Только $1$. Все $0$ - это зацикленные машины.
Назовем этот надежный способ добиться цели - первым способом.

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

Давайте сделаем так. Строим таблицу но по мере появления остановившихся машин берем результат $y$ и теперь применяем к нему некоторое всюду определенное отображение $ P:\mathbb{N} \rightarrow \left \{ 1,0 \right \} $. Не важно как оно задано. Главное - чтобы оно был для всех машин во всех ячейках одно и то же и всюду определено.
Например, если выход остановившейся машины четный, то пишем в ячейку гипотетической таблицы $0$, если нечетное то $1$.
Что теперь мы видим, "глядя" на таблицу?
Чисто формально, опять же какие-то характеристические последовательности (а что же еще?), но как-то по-другому расположенные и теперь в них есть некоторые $0$ явно.
В некоторых строчках определены все нули!
Но что такая таблица из себя представляет теперь? В первом случае мы четко знали, что там представлены все перечислимые подмножества. То есть все характеристически последовательности, которые можно вычислить. А здесь?

Гипотеза:
Я предполагаю, что и в этом случае каждая строка этой таблицы - характеристическая последовательность для некоторого перечислимого подмножества $\mathbb{N}$. А вся эта таблица - тоже исчерпывающее перечисление всех таких последовательностей. То есть, то же самое что мы получили первым способом, но только теперь мы уточнили некоторые нули и расположили все последовательности в другом порядке.

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

Еще раз простите за многословность.
Среди математиков чувствую себя дебилом. Мне нужно было бы назваться здесь не под своим именем, а "Чарли, мойщик полов" из "Цветы для Элджерона" Дэниела Киза. Чарли, застрявший в вечной стадии дебила, ибо таблеток от доктора Штрауса "чтобы стать умным" у него нет.


-- 11.04.2012, 11:04 --

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

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

Не уловил где у меня получилась тавтология. Но ваше определение лучше.
Я явно зря ввел "существует $X$…" Это излишне.
Далее, моя формулировка:

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

явно хуже вашей: ". . . перечислимо, если перечислимо множество всех алгоритмов. . ."
Сразу смутило, что вы не уточнили в окончании формулировки про нули, но подумав я понял что этого не надо делать, если вы определили алгоритм так: $\mathcal{A}: \mathbb{N}\rightarrow \left \{ 0,1 \right \}$. Этого достаточно.
Вы под тавтологией понимали излишние уточнения?
Но в любом случае, мы кажется поняли друг друга.

Цитата:

Тогда лучше поступать несколько по-другому. Опять начать перечислять все возможные алгоритмы $ \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\}$. А значит, среди них будут и те, что дают нули "там где это только можно":)

Вот! Мы, кажется, достигли полного понимания. Но почему это так? Вы считаете это очевидным? Доказываемым "в один шаг"?
Тогда это доказательство и есть те три сонны, где, как сказал Профессор Снэйп , я запутался.

Цитата:

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

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

Мой интерес именно к перечислению бесконечных строчек из 1 и 0 скорей эстетический. Ведь каждая такая строка является не только характеристической последовательностью некого подмножества $\mathbb{N}$, но и неким действительным числом на интервале $[0,1]$. Одна и та же задача в зависимости от интерпретации говорит о разных математических объектах. "Мойщику полов Чарли" этот изоморфизм кажется притягательно-забавным.

[_hum_]

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

Не уловил где у меня получилась тавтология.

Смотрим на ваше первоначальное определение

сообщении #558651 писал(а):

будем говорить, что множество $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 }$ характеристических последовательностей перечислимых подмножеств натуральных чисел перечислимо, если каждое $b\in B$ есть характеристическая последовательность некоторого перечислимого множества натуральных чисел.
"Масло масляное".

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

Сразу смутило, что вы не уточнили в окончании формулировки про нули, но подумав я понял что этого не надо делать, если вы определили алгоритм так: $\mathcal{A}: \mathbb{N}\rightarrow \left \{ 0,1 \right \}$. Этого достаточно.

Обратите еще раз внимание (чтобы опять не возникло недопонимания) - в этом варианте формулировки

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

будем говорить, что множество $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$.

алгоритм $\mathcal{A}: \mathbb{N}\rightarrow \left \{ 0,1 \right \}$ - полуразрешающий, то есть, гарантирующий 1 только в случае принадлежности числа множеству! Нули он не обязан давать (может дать, а может и зависнуть)!
Если вас такое определение перечислимости множества характеристических последовательностей перечислимых подмножеств устраивает (адекватно вашему пониманию), то тогда берем его за базовое. Соответственно, считаем мой вопрос (о формализации перечислимости характеристических последовательностей) закрытым.

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

Цитата:
Тогда лучше поступать несколько по-другому. Опять начать перечислять все возможные алгоритмы $ \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\}$. А значит, среди них будут и те, что дают нули "там где это только можно":)

Вот! Мы, кажется, достигли полного понимания. Но почему это так? Вы считаете это очевидным? Доказываемым "в один шаг"?
Тогда это доказательство и есть те три сонны, где, как сказал Профессор Снэйп , я запутался.

Где что непонятно?
Пусть $\mathcal{Q}:\mathbb{N} \rightarrow \mathfrak{L}$ - алгоритм, перечисляющий программы всех алгоритмов $\mathcal{A}: \mathbb{N}\rightarrow \mathbb{N}$, записанных на языке $\mathfrak{L}$.
И пусть $\mathcal{T}:\mathfrak{L}\rightarrow \mathfrak{L}$ алгоритм, который действует так: в поданную на вход программу $p\in \mathfrak{L}$ алгоритма дописывает строки: "если результат работы больше единицы, то заменить его единицей".
Тогда $\mathcal{R}(m) = \mathcal{T}\big(\mathcal{Q}(m)\big)$ будет алгоритмом, перечисляющим все алгоритмы $\mathcal{A}: \mathbb{N}\rightarrow \left \{0,1\}$. А значит, по принятому выше определению, перечисляющим множество всех характеристических последовательностей перечислимых подмножеств натуральных чисел.

[Alex_semenov]

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

Поэтому фактически получается:
будем говорить, что множество $B\subset \left \{0,1\right \}^{\infty }$ характеристических последовательностей перечислимых подмножеств натуральных чисел перечислимо, если каждое $b\in B$ есть характеристическая последовательность некоторого перечислимого множества натуральных чисел.
"Масло масляное".

Ага. Я начал про перечисление, но закончил просто определением того, что такое характеристическая последовательность.

Цитата:

Обратите еще раз внимание (чтобы опять не возникло недопонимания) - в этом варианте формулировки
. . .

алгоритм $\mathcal{A}: \mathbb{N}\rightarrow \left \{ 0,1 \right \}$ - полуразрешающий, то есть, гарантирующий 1 только в случае принадлежности числа множеству! Нули он не обязан давать (может дать, а может и зависнуть)!

Да, да. Именно так. Все верно. Именно полуразрешающий. Гарантируются только 1, а нули- как получится. Если бы я потребовал большего (а вы это мне как-то обеспечили) то я бы быстренько разрешил бы проблему остановки.

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

Цитата:

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

Тогда это доказательство и есть те три сонны, где, как сказал Профессор Снэйп , я запутался.

Где что непонятно?
Пусть $\mathcal{Q}:\mathbb{N} \rightarrow \mathfrak{L}$ - алгоритм, перечисляющий программы всех алгоритмов $\mathcal{A}: \mathbb{N}\rightarrow \mathbb{N}$, записанных на языке $\mathfrak{L}$.
И пусть $\mathcal{T}:\mathfrak{L}\rightarrow \mathfrak{L}$ алгоритм, который действует так: в поданную на вход программу $p\in \mathfrak{L}$ алгоритма дописывает строки: "если результат работы больше единицы, то заменить его единицей".
Тогда $\mathcal{R}(m) = \mathcal{T}\big(\mathcal{Q}(m)\big)$ будет алгоритмом, перечисляющим все алгоритмы $\mathcal{A}: \mathbb{N}\rightarrow \left \{0,1\}$. А значит, по принятому выше определению, перечисляющим множество всех характеристических последовательностей перечислимых подмножеств натуральных чисел.

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

Отсюда получается, что аналогичным же образом можно отобразить натуральный аргумент на множество {0,1, 2, . .. 9} и в итоге получить перечисление всех вычислимых действительных чисел в десятичном основании.

Спасибо огромное! Вы мне помогли.
По сути, мне и нужен был всего лишь авторитет, который бы дал подзатыльник в этом месте. По всей видимости, любые попытки самостоятельно понять математику достаточно ограничены. Мало того, что они бессистемны, нет еще и интерактивного общения с учителем, который бы через "насилие" над студентом научил его ступать и не сомневаться там, где это действительно надо делать и быть осторожным там, где нужна осмотрительность. Что называется нужна "математическая культура" которую вряд ли можно получить, читая книги и кое-что пробуя сам не зная правильно ли ты это сделал.

[_hum_]

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

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

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

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

Отсюда получается, что аналогичным же образом можно отобразить натуральный аргумент на множество {0,1, 2, . .. 9} и в итоге получить перечисление всех вычислимых действительных чисел в десятичном основании.

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

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

По сути, мне и нужен был всего лишь авторитет, который бы дал подзатыльник в этом месте.

За мнением авторитета - это наверное к Профессор Снэйпу. Я не специалист в этой области.

[Alex_semenov]

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

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

Это были последние капли сомнений.
Считай, что я не спрашивал вас об этом.

Цитата:

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

Да, разумеется. Насколько я понимаю, даже просто перечислимость множества стараются дать через вычислимую функцию. Если есть выбор сказать:

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

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

Цитата:

За мнением авторитета - это наверное к Профессор Снэйпу. Я не специалист в этой области.

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

[Alex_semenov]

Тема вроде как исчерпана.
Но в качестве итога. Я несколько дней пытался собрать все вместе. Вот итог моих потуг:

Теорема Поста утверждает что множество $A$ разрешимо тогда и только тогда, когда перечислимо и $A$ и его дополнение $B=\mathbb{N} \setminus A$.
От нее и будем отталкиваться, учитывая, что множество может быть перечислимым, но неразрешимым.
Перечисляем в лексикографическом порядке все программы $f : \mathbb{N}\rightarrow \mathbb{N}$ и составляем из таких программ все возможные упорядоченные пары. Например, "змейкой Кантора":



Назовем первую программу у всякой такой пары $\mathcal{A}$, а вторую $\mathcal{B}$. Для каждой пары построим следующий алгоритм отображения $p: \mathbb{N}\rightarrow \left \{ 0,1 \right \}$. Назовем его "составным". Вход такого алгоритма подаем на вход и $\mathcal{A} (x)$ и $\mathcal{B} (x)$, которые выполняем пошагово. Первый шаг $\mathcal{A}$, первый шаг $\mathcal{B}$, второй шаг $\mathcal{A}$, второй шаг $\mathcal{B}$. И т.д. Если остановилась программа $\mathcal{A}$, печатаем на выход $1$. Если остановилась программа $\mathcal{B}$ печатаем $0$. В результате получим перечисление всех алгоритмов вида $ p:\mathbb{N}\rightarrow \left \{ 0,1 \right \}$.
Все такие составленные программ $p(x)$ можно разделить на три группы программ (договоримся область определения алгоритма $\mathcal{A}$ называть $A$. Область определение алгоритма $\mathcal{B}$ называть $B$):

Первая группа. Когда область определения $\mathcal{B}$ есть дополнение до $\mathbb{N}$ области определения $\mathcal{A}$. То есть $B=\mathbb{N}\setminus A$ . В этой группе мы получаем все всюду определенные характеристические последовательности для всех разрешимых подмножеств $\mathbb{N}$.

Вторая группа. Когда область определения $\mathcal{B}$ есть некоторое подмножество дополнения до области определения алгоритма $\mathcal{A}$. То есть $B \subset \mathbb{N}\setminus A$. При этом $B$ вообще может быть пустым множеством (программа $\mathcal{B}$ на любом $x$ зацикливается). В этой группе представлены все полу-разрешимые характеристические последовательности.

Объединение этих двух групп (назовем все такие программы "правильными") есть исчерпывающе представление всех как-то вычислимых характеристических последовательностей. Обозначим их звездочкой, $p^{*}$. Для каждой правильной составной программы $B \subseteq \mathbb{N}\setminus A$ и при этом $A \cap B =\varnothing$.

Но есть третья группа программ. Когда $A \cap B \neq \varnothing$. Это значит, что на некоторых $x$ остановится и $\mathcal{A}$ и $\mathcal{B}$. Яркий пример - если в качестве $\mathcal{A}$ и $\mathcal{B}$ взять одну и ту же программу. Такую пару (и программу $p$) назовем "неправильной" (без звездочки).
Однако, каждая такая неправильная программа, получив некоторый $x$, в любом случае выдаст $1$, $0$ или зациклится. И такой результат строго детерминирован для каждого $x$. Потому что из двух конкретных программ $\mathcal{A}$ и $\mathcal{B}$ на конкретном $x$ одна всегда остановится раньше другой. Даже если пара состоит из копий одной и той же программы, копия $\mathcal{A}$ выполняется первой и на шаг остановится раньше копии $\mathcal{B}$. Единственное, для такой пары нельзя четко сказать область значений какой вычислимой функции теперь кодируют единицы?
Однако. Могут ли неправильные программы напечатать такую кодовую последовательность, какую не напечатает ни одна правильная программа? Нет. Правильные программы печатают вес вычислимые характеристические последовательности. Значит, для каждой последовательности из неправильной программы, существует копия, которую печатает правильная. То есть на самом деле все наши составные алгоритмы правильные. Их всех можно пометить звездочкой, $p^{*}$. Деление на правильные и неправильные было условным.

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

Теперь смотрим. А нужно ли было суетиться со "змейкой" и конструировать составные алгоритмы специально? Ведь, перечисляя алгоритмы в лексикографическом порядке, мы и так перечисляем все возможные алгоритмы. В том числе и все наши составные.
Но с ними есть одна техническая проблема. На выходе каждого алгоритма из "простого" перечисления - натуральное число. А нам нужна область значений $\left \{0,1 \right \}$. Мы, конечно можем каждый алгоритм $f(x)$ дописать как $g(f(x))$ , где $g: \mathbb{N}\rightarrow \left \{ 0,1 \right \}$, но как выбрать для этого правильное отображение? Ясно, что вычислимая функция $g(x)$ должна быть всюду определена. Но какая это должна быть функция?
Ответь - любая.
Но интуитивно не понятно, почему годится любая? Не верится как-то.
Идея "правильных" и "неправильных" программ нам поможет рассеять сомнения.

Выбираем некоторое (любое) всюду вычислимое отображение $g: \mathbb{N}\rightarrow \left \{ 0,1 \right \}$, назвав его образно "ключ". Для него существует обратное ему всюду вычислимое отображение $g^{-1}: \left \{ 0,1 \right \}\rightarrow \mathbb{N}$, которое можно назвать "замок".
Далее, обозначим как $p^{*}(x)$ любую правильную программу из рассуждений выше. Всякая такая должна встречаться в лексикографическом перечислении, но область ее значений не $\mathbb{N}$. Поэтому в перечислении такая программа будут представлена как $f(x)$ с некоторым "замком" дающий натуральный результат: $f(x) = g^{-1}(p^{*}(x))$. И если вы теперь правильно подобрали функцию-ключ, то в итоге получите:

$g(f(x))= g(g^{-1}(p^{*}(x))) = p^{*}(x)$

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

Не знаю, был ли толк в таком длинном рассуждении? И правильное ли оно?