Нормальные числа: ликбез

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

    image



    Вавилонская библиотека


    Числа, подходящие для того, чтобы «хранить» в них детскую порнографию и нелицензионный контент произвольные данные посредством метода, напоминающего книжный шифр, называются дизъюнктивными. Более строго, число называется дизъюнктивным по основанию b, если его b-ичная запись содержит любую конечную последовательность b-ичных цифр. Такие числа несложно построить искусственно. К примеру, выпишем все натуральные числа подряд в качестве дробной части десятичного дизъюнктивного числа:
    0,12345678910111213...

    Чуть менее «искусственное» дизъюнктивное число можно получить как сумму ряда: , что будет выглядеть как:
    0,1002000030000004...

    Или, используя результат, полученный мной здесь, а также уменьшив количество лишних нулей, можно в качестве нашей «вавилонской библиотеки» взять сумму , которая выглядит следующим образом:
    1.204008001600032...

    Аналогичные конструкции можно использовать для построения дизъюнктивных чисел по произвольному основанию.

    Лексикон


    Лексиконом, или абсолютно дизъюнктивным числом называется число, дизъюнктивное по любому основанию. Если обычное дизъюнктивное число — это вавилонская библиотека, то лексикон можно назвать «вавилонской википедией», содержащей вавилонскую библиотеку в каждом языковом разделе (системе счисления).

    Такую штуку сконструировать уже сложнее. Однако, как говаривал вещий Олег, «мой конь не боится опасных трудов». Идея следующая: каждое b-значное число можно немного увеличить на некое Δ так, чтобы его первые k цифр остались неизменными (b и k любые). Более того, для нескольких систем счисления можно выбрать некое Δmin так, чтобы при увеличении на него не пострадали первые k цифр ни в одной из этих систем счисления. Поэтому для построения лексикона L можно использовать следующий алгоритм:

    1. Вначале возьмём L = 0.
    2. Для каждого n от 2 до ∞ выполним пункт 3.
    3. Для каждого b от 2 до n выполним пункт 4.
    4. Увеличим число L на такое минимальное Δ, чтобы в b-ичной системе счисления его запись стала содержать b-ичную запись числа (n — b + 1), но при этом не «стёрлась» ни одна запись, внесённая предыдущими итерациями этого пункта.
    5. Совершаем предельный переход
    6. Профит!


    Можно попытаться проследить несколько первых шагов этого алгоритма.
    Но это небезопасно для психики...
    Сначала алгоритм запишет в «двоичный раздел» лексикона единицу. Получится (0,1)2, т.е. 1/2. Затем он запишет в двоичный раздел двойку, т.е (10)2. Получится (0,10)2 — число по сути не изменилось, Δ=0, но второй знак после запятой в двоичной системе счисления теперь «зарезервирован» и не может быть изменён последующими шагами алгоритма. Дальше мы должны записать единицу в троичный раздел. (0,1)2 = (0,11111111...)3, увеличение не требуется, но мы резервируем первый троичный знак после запятой. Теперь записываем в двоичный раздел тройку, получаем (0,10011)2 = 19/32 (заметим, что если бы мы взяли (0,1011)2, это изменило бы первый троичный знак, который уже зарезервирован). И так далее ad infinitum.


    Тряхнём нормальностью


    Нормальное число по основанию b — это такое дизъюнктивное число (по тому же основанию), что для всякого k все последовательности b-ичных цифр длины k входит в b-ичную запись этого числа с одной и той же асимптотической плотностью b-k. Под асимптотической плотностью последовательности w подразумевается , где count(w,n) — это сколько раз последовательность w встретилась среди первых n цифр.

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

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

    Ненормальная нормальность


    Удивительно, но все числа, с которыми мы имеем дело в повседневной жизни, не являются нормальными. «Ненормальность» целых чисел очевидна — их дробная состоит из одних нулей. Также ненормальны и рациональные числа, поскольку их дробная часть в некоторый момент становится периодической, и мы можем подобрать последовательность цифр, которая с этой периодичностью жёстко дисгармонирует.

    Что касается привычных нашему глазу иррациональностей (пи, е, корень из двух etc.) — с ними тоже всё далеко не гладко. Британские учёные полагают, эти числа нормальны; однако на сегодняшний день, насколько мне известно, не существует даже доказательства того, что они дизъюнктивны.

    Выходит, что мы не знаем ни одного «адекватного», естественным образом полученного нормального числа. Что же тогда в них нормального? Ответ прост: нормальных чисел большинство. Доказано, что множество «ненормальных» чисел имеет лебегову меру 0. Это означает, что если ткнуть пальцем в единичный отрезок, то с вероятностью 100% попадёшь в нормальное число.

    Нормальность vs Дизъюнктивность


    Между нормальными и дизъюнктивными числами есть две существенных разницы. Первая — дополнительное условие, накладываемое на асимптотическую плотность последовательностей цифр в записи нормального числа. Вторая — само существование нормальных чисел куда менее очевидно.

    Вернёмся к примерам дизъюнктивных чисел из раздела «Вавилонская библиотека». Нетрудно понять, что второй и третий пример ненормальны: в них асимптотическая плотность нуля будет существенно выше, чем у других цифр. Скажу по секрету:
    Скрытый текст
    асимптотическая плотность нуля в этих примерах равна 1. Чем дальше мы уйдём от целой части, тем менее вероятным будет встретить любую другую цифру. В пределе этой вероятностью можно пренебречь, сказав, что запись состоит из нулей практически полностью.

    А вот первый пример, как ни странно, является нормальным числом. Кстати, это число называется константой Чамперноуна. Также нормальна константа Коуплэнда-Эрдёша:

    0,235711131719...

    — состоящая из десятичных записей простых чисел. Доказано, что аналогичные константы являются нормальными в других системах счисления. Также доказана нормальность таких чисел, как:
    0,1491625364964...
    0,182764125216...
    0,1361015212836...

    — и многих других. Однако доказательства их нормальности не являются тривиальными. В следующей статье, если данная тема заинтересует хабрасообщество, я покажу, как построить число, нормальность которого очевидна. Это потребует отдельной статьи, поскольку весьма неочевиден (и интересен!) способ его построения. Похоже, существует некий аналог гейзенберговского принципа неопределённости, касающийся сложности построения нормального числа и сложности доказательства его нормальности :)

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

    Резюме


    Существует вероятность, что число Пи не обеспечит должную сохранность ваших файлов. Рекомендую использовать вместо него любое искусственно выведенное нормальное число, например — константу Чамперноуна. Кстати, довольно интересная алгоритмическая задача — по заданной последовательности цифр определить индекс её первого вхождения в десятичную запись этой константы.

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

    Ну. И что?
    Реклама
    Комментарии 38
    • +7
      Спасибо большое, я смеялся, как ребенок, от восторга! )
      • 0
        Ага. Если я правильно понял, по заданной последовательности чисел (в заданной системе счисления) можно построить дизъюнктивное число. А есть ли какой-то «хороший» способ это число обозначить так, чтобы этот способ не сводился к формуле
        \sum_{0}^{\infty}\frac{n}{10^{n^2}}
        и исходной заданной последовательности? Ну, вот число \pi все знают, его «обозначили». Может, какие-то хорошие свойства таких дизъюнктивных чисел можно автоматически выводить?

        Зачем: если ответ на вопрос из предыдущего абзаца «да», то открывается прекрасная возможность троллинга патентовладельцев. Берем официальную аудио-запись в цифровой форме, определяем ее дизъюнктивное число, предъявляем претензию на отмену патента на основании «нет новизны».
        • +2
          Попробуйте www.codecogs.com/latex/eqneditor.php, а то читать некомфортно.
          • +2
            О, спасибо — не знал о таком ресурсе. В комментарии выше формула выглядит так:
          • 0
            Не до конца понял, зачем строить отдельное дизъюнктивное число для каждой записи. Достаточно взять любое дизъюнктивное число и показать, что данная запись где-то в нём находится)
            • 0
              А что вычислительно проще? Когда я читал про pifs, у меня сложилось впечатление, что «показать, что данная запись находится в данном числе» вычислительно трудоемко. А построить новое число для заданной последовательности вроде бы попроще будет. Но возникает проблема с однозначной красивой идентификацией этого нового числа (например по дополнительным свойствам, неочевидным образом связанным с исходной последовательностью).
              • 0
                Можно показать неконструктивно. Собственно, из строгого доказательства того, что число дизъюнктивно, уже следует, что нужный фрагмент в нём содержится. Чтобы обвинить человека, например, в краже, достаточно доказать, что он украл деньги, и нет необходимости указывать, где эти деньги сейчас находятся.
                • 0
                  как математик по образованию, я вам верю (хоть доказательства и не видел пока), что теоремы существования должно для доказательства хватить. Но согласитесь, это не тот способ, которым можно уверенно убеждать юристов и привлечь много сторонников-программистов (в некотором роде исходящих из принципа «считает — значит существует»). В общем, было бы здорово иметь технологию явного вычисления либо новых дизъюнктивных чисел (с условием из камента выше), либо бОлее вычислительно эффективного восстановления позиции последовательности в одном из известных дизъюнктивных. Зачем? Затем, что при желании тогда можно развернуть массовую кампанию по сведению официальных музыкальных/видео-треков к известным числам, с известными последствиями.
                  • 0
                    Стандартный аргумент про невозможность сжатия произвольной последовательности. Если бы можно было задать любую последовательность, не используя объём данных, сравнимый с самой последовательностью, то получилось бы идеальное сжатие, которое невозможно. А если для задания нужен сравнимый объём данных — получается просто ещё один формат тех же данных.
                    • 0
                      Пардон, а при чём здесь сжатие?
                      • 0
                        «Ваш 700Mb файл film.avi уже существовал задолго до вас! Вот, смотрите, моя программа по 1 Gb данных выдаст ваш film.avi!»
                      • 0
                        Это верно, если ждать ответов от информатики. А мой вопрос скорее к математике. Я спрашивал, возможно ли получить опосредованное описание заданного дизъюнктивного числа. Например, если вам показать 3.1415926… то вы скажете — конечно это пи! А чем пи отличается от других дизъюнктивных чисел? Во-первых его все знают :) (Что значит «знают»? Только то, что все это странное дизъюнктивное число запомнили). Но знают-то его за его свойства! Как то: длина окружности, интеграл от экспоненты -x^2 и т.п. И мой вопрос о том, можно ли аналогичные свойства выводить автоматически для новых дизъюнктивных чисел. Если да, то получив новое дизъюнктивное число, можно сказать: это не просто случайная длинная последовательность циферок, а такое специальное число, однозначно определяемое вот этим списком свойств (которые полностью определяют вашу песенку бритни спирс, а ну снимайте копирайт).
                        • 0
                          Тот же самый аргумент. Если список свойств однозначно определяет произвольный 700 Мb файл, то сам список свойств должен занимать не менее 700 Мb.
                          • 0
                            Вас подводит применение теоремы Шеннона, она тут ни при чем. Еще раз: я могу вам выписать бесконечное число знаков числа пи, но предъявить лишь одно свойство, однозначно определяющее это число. Свойство, дословно:
                            константа, иррациональное число, равное длине окружности поделенной на удвоенный радиус этой окружности.
                            У меня вышло 104 символа полного описания свойства, однозначно определяющего константу пи. Но число знаков у контанты в ее десятичной записи — бесконечно.
                            • 0
                              Тут, видимо, нужно вспомнить еще про колмогоровскую сложность.
                              • 0
                                Развейте вашу мысль, плиз. А то я пока не понял, какую сторону вы поддерживаете и что именно с колмогоровской сложностью нужно делать.
                                • 0
                                  Я это к тому, что
                                  константа, иррациональное число, равное длине окружности поделенной на удвоенный радиус этой окружности.
                                  фактически колмогоровская сложность числа pi.
                                  Вы предлагаете по произвольной последовательности находить колмогоровскую сложность. Но, если я ничего не путаю, колмогоровская сложность невычислима.
                                  • 0
                                    Заметьте, я не предлагаю, а спрашиваю: возможно ли. К тому же, у нас не произвольная последовательность, а десятичное представление дизъюнктивного числа. Это означает, что у такой последовательности могут появиться более сильные свойства, позволяющие обойти невычислимость колмогоровской сложности. Но я тут не эксперт, поэтому собственно, вопрос и задал.
                              • 0
                                Вы можете задать 104 символами (не пересчитывал и можно придраться к определению, но пусть будет 104) первые 1000 цифр числа пи, но принципиально не сможете задать 104 символами произвольные 1000 цифр. Более того, если ограничиться 104 символами, то доля 1000-циферных последовательностей, которые в принципе можно задать, пренебрежимо мала (точное значение зависит от множества разрешённых цифр и символов), и все такие последовательности исключительно специальны и не имеют собственного смысла в отрыве от определения. Так что либо вам придётся создавать большие семейства свойств (типа «i-я цифра равна j»), для задания которых нужны данные, сравнимые по размеру с исходной последовательностью, либо не рассчитывать на то, что последовательности, имеющие независимый смысл, уложатся в описание.
                                • 0
                                  тут не произвольные последовательности, а десятичные представления дизъюнктивных чисел. Это могут быть последовательности со специальным набором свойств. Каких? В этом и был мой исходный вопрос топикстартеру.
                                  • 0
                                    Процитирую статью:
                                    нормальных чисел большинство. Доказано, что множество «ненормальных» чисел имеет лебегову меру 0. Это означает, что если ткнуть пальцем в единичный отрезок, то с вероятностью 100% попадёшь в нормальное число.

                                    Нет никаких свойств, специфических для нормальных (и, тем более, дизъюнктивных) чисел и при этом отсеивающих значительные множества.
                                    • 0
                                      Ваш аргумент выглядит разумно. No offence, но я бы хотел услышать аргументы топикстартера. Не потому что вам не доверяю, а лишь потому что он обещал некий специальный способ конструировать «число, нормальность которого очевидна». В рассуждениях «принципиально невозможно потому что ...» я не очень свободно ориентируюсь (если не специалист в теории чисел/матлогике, легко пропустить мелкие детали), проще плясать от конкретного предложения.
                                      • 0
                                        Сконструировать число можно. А вот сконструировать для него «хорошее» описание — в общем случае нет.
              • +2
                Конечно, все читают теги!
                • 0
                  Давно хочу спросить — а что означает это «помогитеязастряловмеханизмевселенной»? Какая-то мнемоника? Если да то как она работает?
                  • +6
                    Нет, это шутка о том, как будто некий разум общается с нами, записывая послания в константы физических законов нашей вселенной.
                    • +1
                      • 0
                        На случай, если не все знают этот шаблон, ссылка на TVTropes (осторожно: это ссылка на tvtropes! прочитайте статью и немедленно закрывайте вкладку, не щёлкая по ссылкам, если вам дорог ваш день!). Самый интересный вариант я встречал в 4 сезоне «Robot Chicken».
                    • 0
                      У меня есть ощущение, что хранение файла в виде смещения и длины в каком-то дизъюнктивном числе числе едва ли будет эффективнее, чем хранение номера файла (все возможные файлы ведь можно занумеровать). Если вообще не эквивалентно.
                      • 0
                        Скорее всего, хранение номера файла будет эффективнее. Особенно если файлы занумеровать умно (более распространённым файлам — более короткие номера). Это, по идее, вообще идеальный, неулучшаемый вариант.
                      • 0
                        Биекция. Ни первое ни второе ни разу не эффективнее, ибо и в том и другом случае множества равномощны. В среднем количество цифр в «смещении» или в «порядковом номере» будет равно количеству цифр исходного сообщения.
                        • 0
                          Ещё длина. Вообще, утверждение не слишком очевидное.
                          • 0
                            Удивительно. Первое N-значное число впервые встретится по смещению 0, последнее — по смещению примерно 2.3*N*10N, но в среднем по всем числам смещение их первого вхождения в нормальное число будет ровно 10N, несмотря на повторы. Всего вдвое больше среднего значения самих чисел. Слегка неожиданно. Я думал, что будет ближе к N*10N.
                        • +2
                          А мне вспомнилось, как Фейнман троллил первый отдел, отправив в письме 1/243 в десятичной записи
                          • +2
                            0.(004115226337448559670781893)? Всего 27 цифр, в лучшем случае, три телефонных номера вместится. Вот 1/983 — дело другое :)
                          • +1
                            После прочтения статьи чувствую себя полным болваном.
                            «Вавилонская библиотека» — это из Борхеса и Макса Фрая?
                            • 0
                              Изначально из Борхеса. Хотя я не удивлюсь, если у Фрая она тоже побывала.

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

                            Самое читаемое