Строимые бесконечные последовательности в доказательствах

[Dan B-Yallay]

(Оффтоп)

svv

Да, гены не перешибить ничем! Тюркизмы так и норовят выдать ...

[manul91]

Однако у меня хорошая весть! Я кажется разобрался, почему для Кантора строки из таблицы и строку $\Psi$ можно считать "однотипными".

Помогли мне следующие рассуждения/отождествления:
1) "Вычислимая бесконечная последовательность" <-> любой конечный алгоритм, который получая на вход только натуральное число (номер разряда), выплевывает за конечное время либо 0 либо 1 (должен быть "хорошим" в смысле, чтобы останавливался для любых натуральных чисел)
2) "Стандартнаяя бесконечная последовательность" (детерминирована, возможно невычислимая и т.д.) <-> на вход задаются: односторонне-бесконечная заполненная лента, плюс натуральное число $k$; и фиксированный тривиальный алгоритм который "проматывает" $k$ клеток из ленты и выдает цифру (0 или 1) записанной в $k$-той клетке последовательности.

Теперь сразу очевидно, что в доказательстве Кантора, как строки-последовательности в таблице, так и строка $\Psi$ являются последовательностями "одного и того же типа", а именно типа 2) выше.
Стоит только сообразить, что $\Psi$ "на вход" не нужна вся таблица $S$, а только ее главная диагональ - что по сути, та же "односторонне-бесконечная последовательность" на входе. (Ну и $\Psi$ не выдает самО число на входной ленте, а его противоположное, но это мелочи).
(разумеется я теперь вижу что "определение 2" несколько "замусорено" лишним, но это неважно т.к. именно оно помогло мне "прозреть").

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

Тьфу! Все сошлось. Я счастлив как никогда. Наконец-то могу вздохнуть, и спать спокойно :)

Dan B-Yallay в сообщении #1567899 писал(а):

Вычленимиз таблицы строку ($s_{1, j}, \ j \in \mathbb N$).
Вы согласны, что при нахождении значения $k$-того элемента этой первой строки (да и вообще любого элемента любой строки), необходимо знание (использование) таблицы $S$?
Если "да", то строка $\Psi$, полученная диагональным методом, будет того же "типа", что и строки в таблице.

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

Спасибо всем.
И особо вам, Dan B-Yallay - я вижу вы "подталкивали" меня в правильном направлении (и что особенно ценно, говоря на "моем языке"). С одной стороны жаль что я прочитал только сейчас ваше сообщение; но я уверен что если сам не дошел бы, то с вашей помощью точно разобрался бы.

[Dan B-Yallay]

manul91
Я рад, что мои подсказки немножко помогли.

(Оффтоп)

manul91 в сообщении #1567909 писал(а):

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

Да, это верно в случае, если рассматривается одна-единственная таблица.

Но ведь таблиц подобного типа существует довольно большое множество и теорема Кантора справедлива для всех них. Для разных таблиц механизмы (алгоритмы) определения элементов первой (или любой другой) строки - будyт строго говоря различными. Это равносильно тому, что на вход алгoритму/механизму подаётся не только номер $n$ элемента строки-последовательности, но также и информация о самой таблице $S$. В точности как и для нахождения элементов диагональной последовательности $\Psi$

[Vozduh]

Dan B-Yallay в сообщении #1567911 писал(а):

Да, это верно в случае, если рассматривается одна-единственная таблица.
Но ведь таблиц подобного типа существует довольно большое множество и теорема Кантора справедлива для всех них.

Пока тему не закрыли, ТС вроде бы разобрался, всеже спрошу, т.к. комментарий интересный. Имеется в виду каждой или всех ? Если мы возьмем две таблицы ($S$ из Вашего сообщения), одну из них занумеруем четными числами, вторую нечетными. Первой строкой в каждой таблице поставим диагональное число другой таблицы. Получится, что в каждой таблице по отдельности биекции нет, но вместе есть (объединение пары счетных множеств). Как построить диагональное число для двух таких таблиц (ну или для всех) ?

[manul91]

Dan B-Yallay в сообщении #1567911 писал(а):

Да, это верно в случае, если рассматривается одна-единственная таблица.

Нет, это здесь непричем.

Dan B-Yallay в сообщении #1567911 писал(а):

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

Как раз так я и ошибочно "думал".
Но тогда как раз выходит, что $\Psi$ не такого типа как остальные строки!
Смотрите: как вы говорите, для каждой строки тогда будет свой (разный) алгоритм.
Тогда каждая из строк (в любой из этих разных таблицах), будет определяться в соответствием с соответным конечным алгоритмом у которого на вход подается номер разряда а он выплевывает его значение.
Практически можно считать что в каждой из этих таблиц в строке записана не бесконечная последовательность, а сам соответный алгоритм что ее генерирует (что делает строку конечной, мы "сжали" бесконечные последовательность в строки этих таблиц до конечными, заменяя бесконечную последовательность записью конечного алгоритма который ее "генерит").
Итак, это равносильно самыми разными таблицами с конечными строками в которые записаны алгоритмы (и счетно-бесконечного номера строк у каждой из таблиц) - в одной из этих таблиц для первой строки будет какой-то алгоритм X, в другой для той же первой строки будет "другой" алгоритм Y и т.д.
Но тогда как раз последовательности строк, и последовательность $\Psi$ не однотипные!
Возьмем одну конкретную (хотя и любую, произвольную) из этих таблиц. Возьмем любую из ее строк. Соответная последовательность генерится алгоритмом записанным на ней, на маньер на вход число (номер разряда) - на выход значение соответного разряда.
Но $\Psi$ (которое "строится" для этой конкретной, хотя и произвольной таблицы) никак нельзя сгенерить таким алгоритмом. Кроме номера, алгоритму $\Psi$ не обойтись без "знания" данной конкретной таблицы - чтобы он смог выдавать соответные отличающиеся разряды, для каждой из (счетно-бесконечного к-ва) строк в ней.

Весь цимес однако в том, что сопоставление бесконечной последовательности с алгоритмом, который на вход получает номер разряда, а на выход выдает его значение - неверно!
Точнее оно верно, но только для вычислимых (конструктивных) последовательностей.
Например, для последовательности двоичных разрядов числа $\pi$, или $\sqrt{2}$, или периодической последовательности, и т.д.
Но если последовательность невычислима, или возможно-невычислима (типа константы Чаитина, или если я генерю последовательность подбрасыванием квантовой монеткой и записываю каждый сгенеренный разряд, и т.д.) - на таких последовательностей алгоритм типа "на вход - номер, на выход - значение цифры того номера" - не существует.

Поэтому рассуждения выше, на самом деле относились для случая когда в строки таблиц записаны только вычислимые последовательности. И тогда последовательность $\Psi$ которая не входит в каждой конкретной (хотя и произвольной) из таблиц - заведомо "не такого типа" (на самом деле, она невычислимая, ибо требует не только номер разряда, но и весь диагонал таблицы на вход) - и как раз это ничего не доказывает (итак известно, что вычислимые последовательности счетное количество).

Так что то важное, что я осознал - это что значения разрядов возможно-невычислимых последовательностей можно предъявить только одним образом - если последовательность записана в явном виде, она должна быть "явно подана на вход", один номер разряда недостаточен чтобы выдавать значения соответной цифры по заказу (обычным алгоритмом, всяких выдумок типа оракулов не рассматриваем ибо таких никто не видел).
Чтобы вы заведомо выдавали мне значения цифр невычислимой последовательности по заказу - вы должны считывать их откуда-то, где они записаны в явном виде - иначе никак вам не справится с этой задачей!

Как раз тогда все сходится.
Если в строк $S$ записаны (возможно, только в некоторых из строк) невычислимые последовательности - то этих строк нельзя отождествить с алгоритмами указанного типа "на вход номер -> на выход значение".
Мы должны считать таких строк явно предъявленными (во всей своей счетной-бесконечности разрядов); их нельзя "сжать" до конечной записи соответного строкового алгоритма.
Теперь-то все единообразно: нужно ведь считать что на каждой из строк (поскольку где вычислимые, где невычислимые - неизвестно) сопоставляется алгоритм типа "на вход беск. последовательность в явном виде, плюс номер - алгоритм тупо считывающий значение из строки по этому номеру и выдающий его".
Как раз такого "типа" теперь является и $\Psi$ (строку которой его считыватель требует, это диагональ таблицы).

[Dan B-Yallay]

Vozduh
Вообще говоря, в данной теме рассматриваются последовательности/таблицы, состоящие из нулей и единиц, а не чётных или нечётных чисел.

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

О парах или других комбинациях таблиц речи нет.

[Dan B-Yallay]

manul91 в сообщении #1567953 писал(а):

Смотрите: как вы говорите, для каждой строки тогда будет свой (разный) алгоритм.

... еще и привязанный к данной таблице. Для другой таблицы $T$, отличающейся от данной ($T \neq S$), алгоритм генериривания какой-либо строки будет уже другим. И это не я говорю, а поясняю, как я понял Вашу идею о неравнозначности типов строк. Тут возникает вопрос: почему для диагонального процесса мы требуем некоей "универсальности": чтобы он для любой заданной таблицы $S$ выдавал соответствующую этой таблице последовательность, а от алгоритм нахождения элементов строк мы такого не требуем и привязываем каждый к своей таблице? Типы этих строк потому и получаются разныe.

А давайте для механизма нахождения строк таблицы потребуем тоже "универсальности", то есть, чтобы он был един для всех таблиц? Tогда этот механизм тоже будет должен получать на входе информацию о $S$, прежде чем выдавать скажем, eё первую строку. Соответственно, тип такой строки совпадёт с типом диагональной последовательности. Разве нет?

(Более детально)

Рассмотрим множество таблиц определюнного вида (который мы с Вами обсуждаем), обозначим его $S_{\alpha}$.

Для конкретно заданной таблицы $S \in S_{\alpha}$ Вы предполагаете существование "частного" алгоритмa $u_{S, 1}(. ) \to \{0,1\}$ позволяющего вычислить значение $n$-ого номера первой строки: $u_{S,1}(n)$ и генерирующего последовательность при $n = 1,2,3, \ldots$. Для второй строки имеется уже другой, не менее "частный" алгоритм $u_{S, 2}(.) \to \{0,1\}$. Верно?

Cоответственно для какой-то другой таблицы $T \in S_{\alpha}$ предполагаются алгоритмы $u_{T, 1}, \ u_{T, 2}$ etc. Но все эти алгоритмы не универсальны, каждый только для своей таблицы и строки. Универсальный же механизм для нахождения произвольного элемента в произвольной таблицe будет иметь 3 аргумента: $U(S, k, n)$. И те "частные" алгоритмы тогда будут выражаться через этот "универсальный":

$$ \begin{align}u_{S,1}(.) = U(S,1, .)\\ u_{T,2}(n) = U(T, 2,n) \end{align}$$

Канторовская диагональная последовательность $\Psi$ для $S$ (или $T$) будет получена как

$$ \Psi_S(k) = U(S,k,k) \ \text{XOR} \ 1$$

$$\big( \Psi_T(k) = U(T,k,k)\ \text{XOR}\ 1\big)$$

Думаю, что в этом случает типы последовательностей/строк будут совпадать

[manul91]

Dan B-Yallay в сообщении #1567977 писал(а):

... еще и привязанный к данной таблице. Для другой таблицы $T$, отличающейся от данной ($T \neq S$), алгоритм генериривания какой-либо строки будет уже другим. И это не я говорю, а поясняю, как я понял Вашу идею о неравнозначности типов строк.

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

(Более детально:)

Dan B-Yallay в сообщении #1567977 писал(а):

А давайте для механизма нахождения строк таблицы потребуем тоже "универсальности", то есть, чтобы он был един для всех таблиц? Tогда этот механизм тоже будет должен получать на входе информацию о $S$, прежде чем выдавать скажем, eё первую строку. Соответственно, тип такой строки совпадёт с типом диагональной последовательности. Разве нет?

Впервых я не понимаю почему нужно рассматривать "всех таблиц сразу"; достаточно рассматривать любую конкретную, хотя и произвольную таблицу. Если для произвольно взятую таблицу мы можем построить объект $\Psi$ такого же типа, как и ее строчные объекты (привязанные к этой таблице), так что $\Psi$ не совпадает ни с одного из ее строчных объектов - то несчетность этого типа объектов доказана.
Во вторых, пока не понятно как так этот механизм будет универсальным "для всех таблиц сразу", и в то же время будет получать на вход только одну конкретную из них: $S$.

Dan B-Yallay в сообщении #1567977 писал(а):

Для конкретно заданной таблицы $S \in S_{\alpha}$ Вы предполагаете существование "частного" алгоритмa $u_{S, 1}(. ) \to \{0,1\}$ позволяющего вычислить значение $n$-ого номера первой строки: $u_{S,1}(n)$ и генерирующего последовательность при $n = 1,2,3, \ldots$. Для второй строки имеется уже другой, не менее "частный" алгоритм $u_{S, 2}(.) \to \{0,1\}$. Верно?

Верно. Точнее верно, что я так предполагал прежде.
Но таких таблиц рассматривать (в связи с д-вом Кантора) неправильно, потому что если мы рассматриваем такие таблицы - это означает что мы рассматриваем таблицы у которых в строках только вычислимые последовательности!

Dan B-Yallay в сообщении #1567977 писал(а):

Cоответственно для какой-то другой таблицы $T \in S_{\alpha}$ предполагаются алгоритмы $u_{T, 1}, \ u_{T, 2}$ etc. Но все эти алгоритмы не универсальны, каждый только для своей таблицы и строки.

Да, все так для таблиц, у которых в строках только вычислимые последовательности. Важно уточнять, что эти алгоритмы не абы какие, а такие что на вход у них подается натуральное число (номер разряда цифры), и на базе этой (и только этой!) информации, они выплевывают значение разряда последовательности (0 или 1).
Собственно другие "типы" алгоритмов (например алгоритмы с бесконечном количеством информации на вход) - в строгом (классическом) смысле определения алгоритма, алгоритмами и не являются, мы можем только условно говорить так о них, но они качественно "другого типа". Это разграничение важно.

Dan B-Yallay в сообщении #1567977 писал(а):

Универсальный же механизм для нахождения произвольного элемента в произвольной таблицe будет иметь 3 аргумента: $U(S, k, n)$. И те "частные" алгоритмы тогда будут выражаться через этот "универсальный":
.....
Канторовская диагональная последовательность $\Psi$ для $S$ (или $T$) будет получена как
.....
Думаю, что в этом случает типы последовательностей/строк будут совпадать

Да, я понял о чем вы.

Такой подход мне кажется надуманным, потому что рассматривать множество таблиц только для того, чтобы искуственно впихнуть таблицу как аргумент алгоритма ненужно.
Как я выше писал, рассматривать много таблиц нет никакой необходимости.
Если дело только за том, чтобы искуственно впихнуть таблицу как аргумент алгоритма (чтобы якобы "уеднаквить типы") - то итак это можно сделать сразу же: любого алгоритма $U(n)$ можно представить как алгоритм $A(S,n)$ формально впихивая лишнюю таблицу в аргументах. При этом $A(S,n)$ делает то же самое что и $U(n)$, практически не пользуясь своего табличного аргумента.
Разумеется, такое "уеднаквление типов" является не более чем "мошенничеством" - оно не изменяет факт что строковым алгоритмам таблица на самом не нужна, а алгоритмам для $\Psi$ без таблицы (точнее, ее бесконечной диагонали) на вход не обойтись. Что и есть качественное отличие.

Как я выше несколько раз сказал, суть дела в том что нельзя считать что конкретным последовательностям соответствуют "свои" алгоритмы типа $U(n)$.
Это просто ошибочно!
(и если с этим вашим много-табличным доказательством "согласиться", то из него будет следовать что вычислимых последовательностей - континуум - что попросту неверно).
Для невычислимых последовательностей - которые могут участвовать в строках таблицы рассматриваемой Кантором, "своего" алгоритма типа $U(n)$ не существует. Если вообще мы их хотим сопоставлять с алгоритмами - то только с нестандартными - типа с "бесконечным входом" $U(S,n)$ где $S$ бесконечная таблица, последовательность и т.д. которую алгоритм в явном виде обязан иметь на входе, чтобы смог с ней считывать что понадобится.

[Dan B-Yallay]

manul91
Xочу принести извинения, что сразу не оговорил своё использование понятия "алгоритм нахождения элементов строки". Я представлял их просто как некоторое существующее отображение, необязательно конструктивнoe или вычислимoе. То есть последовательность в стандартном смысле.

Если же понимать "алгоритм" как "вычислимый" (что Вы как раз используете ), тогда я полностью согласен с Вашими аргументами.

[Vozduh]

Dan B-Yallay в сообщении #1567986 писал(а):

manul91
Xочу принести извинения, что сразу не оговорил своё использование понятия "алгоритм нахождения элементов строки". Я представлял их просто как некоторое существующее отображение, необязательно конструктивнoe или вычислимoе.

Интересно, этот ординал больше, чем ординал Черча-Тьюринга ?
Или первый невычислимый ординал ?
Если разбить на две таблицы: одна из которых нумеруется четными натуральными числами, а другая - нечетными, то тогда это будет соответствовать ординалу :$w+w$ или $w \cdot 2$
Если глубже - то другим ординалам, все более запутанным, невычислимым.
Думаю, диагональное число, в данном контексте, соответствует, одному из недостижимых ординалов.
Все-равно, их всех никак не пронумеровать..
Просто интересно, какая именно аксиома (существования недостижимых ординалов) используется ?