Информационная ёмкость чисел

[Андрей АK]

migmit в сообщении #411849 писал(а):

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

Универсальный архиватор, получает на вход любой текст (определенной длины) и на выходе ВСЕГДА выдает текст меньшей длины, по которому потом можно восстановить исходный текст.
Такого архиватора не существует.
Еще его можно называть "идеальным архиватором".

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

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

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

[venco]

Андрей АK, проблема в том, что считать минимальной записью. Ваши 52 символа требуют кучи вспомогательной информации - значения использованных слов, предложенное мной $4 \arctan 1$ - определения функции $\arctan$. Если же эту вспомогательную информацию не учитывать, то можно записать и ещё короче - $\pi$.
Выходит, длина записи числа зависит от сложности интерпретатора этой записи, т.е. по сути это тот же "персональный архиватор". Только практически невозможно определить информационную длину такого "архиватора".
Если же пытаться использовать "универсальный архиватор", то длина записи будет зависеть от того, какой именно "архиватор" (интерпретатор записи) мы выберем. Т.е. получается, что нет такого универсального параметра, как информационная длина числа, и эта длина зависит от сложности интерпретатора. В идеальном случае, например в $\TeX$, достаточно одного символа $\pi$, ну или трёх (\pi), если рассматривать исходный код.

[Андрей АK]

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

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

С этой точки зрения, поскольку $\pi$ не имеет своего множества, то и говорить о его информационной ёмкости нет смысла ... это да.
Тут я ,наверное, погорячился.

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

[venco]

(о конструктивности)

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

[Руст]

venco в сообщении #411966 писал(а):

(о конструктивности)

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

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

[venco]

Руст в сообщении #411976 писал(а):

Не согласен. Во первых для каждого конструктивного числа существует бесконечно много алгоритмов, вычисляющих это число.

А разве это мешает построению числа, отличного от всех перечисленных (пусть и по многу раз)?

[Руст]

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

[venco]

Руст в сообщении #411985 писал(а):

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

Т.е. контруктивные числа задаются не так, как я описал? (Алгоритмом получения k-ой цифры).
А как?

[Xenia1996]

Андрей АK в сообщении #411603 писал(а):

Любое число, которое можно задать алгоритмом можно записать при помощи конечного набора символов.
Число $\pi$ ,например, можно описать следующей фразой: "Число, равное отношению длины окружности к диаметру" - имеет конечное число символов, что и требовалось.

У $\pi$ колмогоровская сложность - пустяковая. Вот Вы попробуйте последовательность из миллиона случайных чисел сжать.

[venco]

venco в сообщении #411989 писал(а):

Руст в сообщении #411985 писал(а):

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

Т.е. контруктивные числа задаются не так, как я описал? (Алгоритмом получения k-ой цифры).
А как?

Обновил память.
Вроде я не ошибся, и конструктивность требует от алгоритма вычисления с указанной точностью, что эквивалентно вычислению k-ой цифры.
Медленно сходящиеся алгоритмы просто долго вычисляют, но всё равно обязаны досчитать до заказанной точности.

[Xaositect]

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

[venco]

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

[Руст]

Xaositect в сообщении #412027 писал(а):

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

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

[migmit]

Андрей АK в сообщении #411875 писал(а):

migmit в сообщении #411849 писал(а):

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

Универсальный архиватор, получает на вход любой текст (определенной длины) и на выходе ВСЕГДА выдает текст меньшей длины, по которому потом можно восстановить исходный текст.

А, ну, это-то нам не нужно. Нас вполне удовлетворит архиватор, который некоторые числа сжимает, а некоторые - удлинняет.

[Андрей АK]

Xenia1996 в сообщении #412001 писал(а):

Андрей АK в сообщении #411603 писал(а):

Любое число, которое можно задать алгоритмом можно записать при помощи конечного набора символов.
Число $\pi$ ,например, можно описать следующей фразой: "Число, равное отношению длины окружности к диаметру" - имеет конечное число символов, что и требовалось.

У $\pi$ колмогоровская сложность - пустяковая. Вот Вы попробуйте последовательность из миллиона случайных чисел сжать.

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

Насчет конструктивности - мне пришла в голову одна мысль - в чем смысл конструктивной логики , что имеет непосредственное отношение к вопросу о счетности.
Если сильно упростить (да простят меня поборники строгого формализма) то конструктивная логика - это открытые и замкнутые множества.
(а также вычислимые и невычислимые и т.п.)
Смысл вот в чем: объединение и пересечение открытых множеств - открытое множество (замкнутых - замкнутое,...)
Нет никакого способа из множества открытых множеств перейти в множество замкнутых ... кроме как используя операцию $XOR$ - сложение по модулю 2.
Эта операция обеспечивает и отрицание (отрицание - это сложение по модулю два некоторого множества с единичным множеством. Единичное - это объединение всех множеств.).
Именно поэтому в доказательствах о существовании несчетных или неконструктивных чисел необходимо применять отрицание.
Диагональ Кантора - это один из таких способов.
В этом методе ,как и во всех прочих, применяется отрицание: "Выбрать число НЕ входящее в некое множество".

Но отрицание ,в доказательствах, - это не корректный метод.
Это брат близнец ,или скорее, двойственный принцип к нарушению принципа причинности.
Если при нарушении принципа причинности следствие становиться собственной причиной, то применение при доказательства отрицания - это некий вывод вообще без причины.
А не даром еще Лейбниц считал Принцип достаточного основания самым главным принципом всего сущего.
А доказательство через отрицание его нарушает.