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

[Андрей АK]

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

Получается что, хотя $\pi$ имеет бесконечное число знаков (в десятичной записи) но информации в себе содержит не более чем на 52 буквы.

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

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

А общее количество информации среди множества чисел не должно изменяться.

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

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

[Legioner93]

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

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

Как-то связан
Вы эту фразу просто так вставили? Откуда в ваших рассуждениях логарифм появляется вообще?

[venco]

Андрей АK, в который раз уже Вы интересную идею облачили в безграмотные и бессмысленные слова.
Что Вы понимаете под фразой "информация не сжимаема"? По-моему, это просто чушь.
Взять то же число $\pi=4\arctan 1$. Получилось гораздо короче 52 букв, а число то же самое.
Под "системами счисления" Вы, похоже, тоже понимаете что-то нестандартное. Поэтому стоит сначала объяснить, что Вы имеете в виду.

[Андрей АK]

Отвечаю по порядку.
Информация измеряется в битах.
Если у нас есть нечто записанное при помощи $N$ битов, то не существует универсального архиватора, который ту же информацию запишет при помощи $M<N$ битов, если заранее неизвестно что там такое записано.
Доказательство элементарно- множество всех комбинаций нулей и единиц из $N$ битов не может быть быть сопоставлена во взаимно однозначное соответствие с множеством всех комбинаций нулей и единиц из $M$ битов.
Вот это и называется - "Информация несжимаема".

Далее
Количество битов (т.е. количество информации) равно двоичному логарифму от количества чисел (вариантов).
Вот откуда логарифм.

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

Кроме всем общеизвестных есть еще и множество экзотических систем счисления, например, "Система остаточных классов" (СОК) -запись чисел через их остатки от деления на простые (и не обязательно на простые) числа.
(см. Самофалов К.Г. и др. "Прикладная теория цифровых автоматов" 1987)

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

[svv]

Андрей АK писал(а):

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

А Вы можете в рамках этой системы счисления перемножить два числа -- "число, равное отношению длины окружности к диаметру" и "число, равное основанию натуральных логарифмов"?

[Андрей АK]

svv в сообщении #411676 писал(а):

Андрей АK писал(а):

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

А Вы можете в рамках этой системы счисления перемножить два числа -- "число, равное отношению длины окружности к диаметру" и "число, равное основанию натуральных логарифмов"?

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

[venco]

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

Отвечаю по порядку.
Информация измеряется в битах.
Если у нас есть нечто записанное при помощи $N$ битов, то не существует универсального архиватора, который ту же информацию запишет при помощи $M<N$ битов, если заранее неизвестно что там такое записано.

Враньё. Неправда.

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

Доказательство элементарно- множество всех комбинаций нулей и единиц из $N$ битов не может быть быть сопоставлена во взаимно однозначное соответствие с множеством всех комбинаций нулей и единиц из $M$ битов.

При чём тут множество всех комбинаций?

[Андрей АK]

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

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

Отвечаю по порядку.
Информация измеряется в битах.
Если у нас есть нечто записанное при помощи $N$ битов, то не существует универсального архиватора, который ту же информацию запишет при помощи $M<N$ битов, если заранее неизвестно что там такое записано.

Враньё. Неправда.

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

Доказательство элементарно- множество всех комбинаций нулей и единиц из $N$ битов не может быть быть сопоставлена во взаимно однозначное соответствие с множеством всех комбинаций нулей и единиц из $M$ битов.

При чём тут множество всех комбинаций?

Множество всех комбинаций - это то количество слов, которые можно составить при помощи заданного количества бит.
Я сказал "заранее неизвестно, что там записано" - это значит что может быть записано любое слово из этого множества.
Если бы существовал универсальный архиватор, то он обязан был бы каждое из слов сжать до размера $M$ бит или меньше.
Но тогда множество всех возможных результатов сжатия было бы меньше множества всех исходников - поскольку количество слов, которые можно задать при помощи $M$ бит меньше количества, которое можно задать при помощи $N$ бит , если $M<N$.
Иначе при разархивации одному образу соответствовало бы несколько исходников - а это уже потеря информации.
Так понятней?

-- Пт фев 11, 2011 02:23:08 --

Насчет того что "Информация измеряется битами":
Формула Хартли
В нашем случае нет никаких случайных вероятностных распределений.
Поэтому для определения количества информации в конкретной строке символов используется формула Хартли:
"Количество информации (k), необходимой для определения конкретного элемента, есть логарифм по основанию 2 общего количества элементов (N)."

А логарифм по основанию 2 - это количество битов.

Т.е. информация измеряется в битах.

[venco]

При чём тут универсальный архиватор? Вы заявили о невозможности сжать конкретное число.

[migmit]

И как это pkzip работает...

[Андрей АK]

Я сказал, что из конкретного числа нельзя выжать больше информации, чем в его минимальной записи.
Записать таким образом , что его длина станет сколь угодно большой - это можно, но при чем тут информация?
Поскольку универсальных архиваторов не существует - мы не можем получать дополнительную информацию, переводя числа из одной системы счисления в другую.
Изменяется только форма записи, но количество реальной информации не меняется.
Например, число $1/3$ имеет реальную информационную ёмкость - два бита (как и число три) , но ,при переводе в двоичную систему счисления, для его записи требуется бесконечный набор знаков ... но этот набор все также несет в себе информационную емкость - два бита - поскольку период двоичной записи числа $1/3$ равен двум битам.
Записав любое рациональное число в двоичной системе счисления и вычислив его период, мы узнаем реальную информационную емкость натуральных чисел, из которых состоит наше число.
Или ,зная емкость двух натуральных чисел, можно попытаться вычислить длину периода их дроби.
Хотя вот ,например, у числа $5$ длина периода равна четырем битам , хотя двоичная запись $5$ занимает три бита.
Т.е. не все так просто...
может надо считать информационную емкость простых чисел равной их двоичному логарифму ? (А не сколько бит требуется для их записи)
А у периода дроби свои особенности ...

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

(Это я не проверял - будем считать что это гипотеза)

Интересно что ,например, число $1/7$ имеет десятичный период равный $6$, а вот в двоичной записи её период равен ... $3$ битам - ровно столько, сколько занимает двоичная запись числа $7$.

[venco]

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

Я сказал, что из конкретного числа нельзя выжать больше информации, чем в его минимальной записи.

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

[Андрей АK]

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

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

Я сказал, что из конкретного числа нельзя выжать больше информации, чем в его минимальной записи.

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

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

Например, число $\pi$ в системе счисления пи-натуральных чисел:
$0,\pi,2\pi,3\pi,4\pi...$
кодируется одним битом - единицей.
Но поскольку это индивидуальный ,для $\pi$, архиватор, вам придется к нему добавлять определение числа $\pi$
Вы получите код числа $\pi$ уже не единицу а больше (хотя все же меньше чем бесконечность).

[migmit]

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

[Ales]

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

Любое число, которое можно задать алгоритмом можно записать при помощи конечного набора символов.

Похоже на определение сложности по Колмогорову.