Парадоксы о сжатии данных +32




Задача сжатия данных в своей простейшей форме может относиться к числам и их обозначениям. Числа можно обозначать числительными («одиннадцать» для числа 11), математическими выражениями («два в двадцатой» для 1048576), строковыми выражениями («пять девяток» для 99999), именами собственными («число зверя» для 666, «год смерти Тьюринга» для 1954), или произвольными их комбинациями. Годится любое обозначение, по которому собеседник сможет однозначно определить, о каком числе речь. Очевидно, что сообщить собеседнику «факториал восьми» эффективнее, чем эквивалентное обозначение «сорок тысяч триста двадцать». Здесь возникает логичный вопрос: какое обозначение для заданного числа самое короткое?

Философ Бертран Рассел в 1908 опубликовал «парадокс Берри», который затрагивает вопрос обозначений чисел с противоположной стороны: какое самое маленькое число, для обозначения которого недостаточно восьмидесяти букв?
Такое число обязано существовать: из восьмидесяти русских букв и пробелов можно составить всего 3480 обозначений, значит, с использованием восьмидесяти букв можно обозначить не более 3480 чисел. Значит, некое число, не большее чем 3480, обозначить таким образом невозможно.

Значит, этому числу будет соответствовать обозначение «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв», в котором всего 78 букв! С одной стороны, это число обязано существовать; с другой, если это число существует, то его обозначение ему не соответствует. Парадокс!

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

Есть ли формальные способы описания последовательности (алгоритма) действий над числами? Есть, и в изобилии — их называют языками программирования. Будем вместо словесных обозначений использовать программы (например, на Python), выводящие нужные числа. Например, для пяти девяток подойдёт программа print("9"*5). По-прежнему будем интересоваться самой короткой программой для заданного числа. Длину такой программы называют колмогоровской сложностью числа; это теоретический предел, до которого заданное число можно сжать.

Вместо парадокса Берри теперь можно рассмотреть аналогичный: какое самое маленькое число, для вывода которого недостаточно килобайтной программы?

Рассуждать будем так же, как и раньше: существует 2561024 килобайтных текстов, значит, килобайтными программами можно вывести не более 2561024 чисел. Значит, некое число, не большее чем 2561024, вывести таким способом невозможно.

Но напишем на Python программу, которая генерирует все возможные килобайтные тексты, запускает их на выполнение, и если они выводят какое-то число — то добавляет это число в словарь достижимых. После проверки всех 2561024 возможностей, сколько бы времени это ни заняло — программа ищет, какое самое маленькое число отсутствует в словаре, и выводит это число. Кажется очевидным, что такая программа уложится в килобайт кода — и выведет то самое число, которое невозможно вывести килобайтной программой!

В чём же подвох теперь? На неформальность обозначений его списать уже нельзя!

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

Или не завершится? Ведь среди всех программ, которые будут испробованы, встретится while True: pass (и её функциональные аналоги) — и дальше проверки такой программы дело уже не пойдёт!

В отличие от парадокса Берри, где подвох был в неформальности обозначений, во втором случае мы имеем хорошо замаскированную переформулировку «проблемы остановки». Дело в том, что по программе невозможно за конечное время определить её вывод. В частности, колмогоровская сложность невычислима: нет никакого алгоритма, который бы позволил для заданного числа найти длину самой короткой программы, выводящей это число; а значит, нет решения и для задачи Берри — найти для заданного числа длину самого короткого словесного обозначения.




Комментарии (102):

  1. exception13x
    /#20002886

    С каких пор пробелы и запятые стали буквами?
    Если использовать «символов», то парадокс пропадает.

    • tyomitch
      /#20003024 / +1

      Почему пропадает?

      • exception13x
        /#20003594

        Потому что в фразе «самое маленькое число, для обозначения которого недостаточно восьмидесяти символов» будет 83 символа.

        Прошу прощения за придирки, меня просто зацепила фраза про 78 букв (которых 69 в исходной фразе)

        • kahi4
          /#20003868 / +1

          ну поменять 80 на 100 и делов то, "самое маленькое число, для обозначения которого недостаточно ста символов".

          • TheShock
            /#20005988

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

            • exception13x
              /#20008492

              А это кстати хороший момент, как будет меняться число при изменении нижней границы количества букв для его описания?
              То есть если поменять границы с 80 до 100 само число изменится?

              • tyomitch
                /#20008540

                Учитывая, что такого числа не существует ни для 80, ни для 100 — ваш вопрос вызывает удивление.

                • kahi4
                  /#20008776

                  А мне вот что стало интересно. Опустим парадокс. Скажем, мы не можем записать все числа от 1 до n^m (n — размер алфавита, m — количество символов) через естественный алфавит из-за отсутствия однозначного кодирования числа через произвольную строку.


                  Допустим, мы сделаем такую систему кодирования, скажем, по аналогии с base64, т.е. можем закодировать любое число меньше n^m через последовательность символов из нашего словаря не длинее m штук. При каком размере строки на естественном языке в нее же влезет "алгоритм расшифровки" (который так же должен быть, очевидно, частью закодированного числа)?

                  • fireSparrow
                    /#20009996 / +1

                    Запись алгоритма сама по себе — бессмысленный набор символов, она обретает смысл, только когда есть субъект, способный прочитать, понять и исполнить алгоритм.
                    А разные субъекты могут по разному понимать одну и ту же запись алгоритма. Чтобы они гарантированно понимали его одинаково, нужно в последовательность вложить ещё и подробный стандарт, который для языка программирования может занимать толстый том.
                    Но при этом и текст стандарта нужно прочитать и осмыслить одинаково, а это всё равно предполагает, что у субъектов есть некий общий осмысливающий аппарат, который, получается, тоже должен быть как-то занесён в сообщение.

                    • tyomitch
                      /#20010174

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

                    • juray
                      /#20010512 / +1

                      Любой набор символов имеет смысл, только когда есть субъект, способный его прочитать и понять.

                      Само понятие смысла знаков/символов связано с наличием такого субъекта.

                      • fireSparrow
                        /#20010934

                        Об этом и речь. На самом деле, точнее даже говорить о системе «субъект + контекст».

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

            • kahi4
              /#20008672 / +1

              Парадокс своими словами:


              Возьмем любой словарь размера n. Возьмем строку длиной m.


              Существует n^m способов расположить символы из этого словаря в строки длиной n. Т.е. конечное число. Самих чисел — бесконечное число. Мы не можем описать любое число из бесконечного набора используя конечный словарь и конечную длину строк.


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


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

              • TheShock
                /#20008888

                Все комбинации n символов в строке длиной до m мы использовали для обозначения чисел от 1 до n^m. Следовательно фраза «самое маленькое число, для обозначения которого недостаточно ста символов» уже была занята значительно меньшим числом и не может быть использована для отображения числа n^m+1. Она занята. Парадокса нет.

                • tyomitch
                  /#20008932

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

                  • TheShock
                    /#20009076

                    Тогда я не вижу парадокса тоже. Просто такого числа, подходящего под эту фразу, не существует

                    • tyomitch
                      /#20009246

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

                      • TheShock
                        /#20009316

                        Почему такие числа должны существовать на изменяющихся правилах? Любое число можно записать ста символами, если изменить правила, по которым это число вычисляется. По сути, вы используете не только 100 символов, но и мета-информацию

                      • ioannes
                        /#20009390

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

                  • juray
                    /#20010580

                    Ненене. Любому из чисел в диапазоне до n^m можно однозначно сопоставить одну из строк длиной m из алфавита в n символов.

                    Большинство этих строк с точки зрения естественного языка будет бессмысленным набором букв, но часть таки будет валидными фразами. Говоря по другому — любая валидная фраза длины до n будет содержаться в этом списке, включая и «абырвалг», и прочие другие.

                    Причем, фразы длиной менее n в этом списке будут встречаться несколько раз, по-разному дополненные пробелами (в начале, в конце, в начале и конце). Если мы считаем это одной и той же фразой, а не разными комбинациями — то получаем, что такие короткие фразы обозначают аж несколько чисел.

                    • tyomitch
                      /#20010614

                      При предлагаемом вами кодировании фраза «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» заведомо не будет соответствовать самому маленькому числу, для обозначения которого недостаточно восьмидесяти букв.
                      Поэтому ваше кодирование, хотя и осуществимо, но никакого интереса не представляет.

                      • TheShock
                        /#20011870 / +1

                        В смысле алгоритмов сжатия ваше «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» тоже никакого интереса не представляет

                        • tyomitch
                          /#20012554

                          Это правда; но зато оно представляет занятный парадокс, тогда как 34-ричное кодирование не даёт ни сжатия, ни парадокса.

  2. vvadzim
    /#20002924 / +1

    Та программа на питоне, если она в килобайт укладывается, сгенерит и запустит в т.ч. и себя и будет ждать остановки. А тот второй экземпляр тоже сгенерит и запустит себя и тоже будет ждать остановки. И так до бесконечности.
    В приведённом в статье алгоритме просто есть бесконечный цикл, соответственно до фазы поиска самого маленького числа в словаре управление никогда не дойдёт и самого маленького программа не выведет.

    • tyomitch
      /#20003030 / +1

      Именно об этом последний абзац статьи :)

  3. farafonoff
    /#20002928

    Очевидно, не каждая последовательность букв обозначает число. Например — «Самое Большое Простое Число». Так что в парадоксе нет ничего парадоксального.
    Нетрудно заметить, что приведенный алгоритм из второй части статьи рано или поздно найдет сам себя, таким образом он эквивалентен тому что используется в доказательстве «проблемы останова».

    • tyomitch
      /#20004698

      Какое отношение к этому парадоксу имеет то, что не каждая последовательность букв обозначает число?

      • farafonoff
        /#20005394

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

        • synedra
          /#20006594 / +1

          Есть разница. Фраза "Самое большое простое число" обозначает некий критерий, которому число может или соответствовать, или нет: оно должно быть простым и быть больше всех остальных простых чисел. Ему ничего не соответсвует, так же как критериям "простое число, кратное пяти", "четвёртый муж королевы Виктории" или "сочинения Сократа о Платоне". Но это свойство реальности, а не самого определения. Если бы простые числа были устроены иначе, а Сократ любил бы писать диалоги о своих учениках — эти фразы означали бы конкретные числа и тексты.


          А фраза «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» (высказывание, не последовательность символов; очевидно, что Рассел писал не на русском, но нам не приходится переходить на английский для обсуждения этого парадокса) внутренне противоречива. Она, грубо говоря, не может корректно парситься.

  4. Sabin
    /#20003470

    Близкая по смыслу статья о Busy Beaver https://m.habr.com/ru/post/317996/

  5. Akon32
    /#20003792 / +1

    какое самое маленькое число, для обозначения которого недостаточно восьмидесяти букв?
    Такое число обязано существовать: из восьмидесяти русских букв и пробелов можно составить всего 34^80 обозначений, значит, с использованием восьмидесяти букв можно обозначить не более 34^80 чисел.

    Это совершенно не означает, что минимальное число будет порядка 34^80. Есть тенденция обозначать огромные числа кратко, "гугол" = 10^100 — всего 5 букв. Утверждение, что такое число обязано существовать, хотя оно и верное, кажется мне нереалистичным по причине того, что завязано на семантику слов в каком-то языке. После того, как мы назовём число, люди могут придумать более краткое обозначение для ещё большего числа, и даже задействовать старое слово для нового понятия.


    какое самое маленькое число, для вывода которого недостаточно килобайтной программы?

    Не обязательно перебирать 256^1024 программ.
    Можно подойти как раз со стороны колмогороской сложности — взять чисто случайное число, записываемое объёмом 1кбайт+1бит, записать его в десятичном, шестнадцатеричном виде, или в аналоге base64 (это компактнее) и добавить код для раскодирования наподобие "print(...)".

    • tyomitch
      /#20004724

      Это совершенно не означает, что минимальное число будет порядка 34^80.

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

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

      • Akon32
        /#20004898

        Вторую часть вашего комментария я не понял. Взять чисто случайное число, и что дальше?

        Я некорректно понял задачу — посчитал, что можно предоставить число минимальной длины, которое не влезет в 1кбайт программы. Очевидно, не все такие числа минимальны.

    • nikandr23
      /#20007276

      можно написать
      for i=1 to Мульярд
      и в цикле фигачить print(...)

      ах,
      нам нужна длинная прога аж в килобайт?
      ну давайте натулим 10 вложенных for…

      • rombell
        /#20007958

        запись вот этого «Мульярд» и может занять всё отведённое место

      • tyomitch
        /#20008232

        Проблема не в том, чтобы напечатать очень большое число; проблема в том, чтобы найти самое маленькое число, которое напечатать нельзя.

  6. force
    /#20004186 / +1

    Не понял порадокса с 80 буквами. Если мы определяем запись числа буквами, то фраза самое маленькое число, для обозначения которого недостаточно восьмидесяти букв будет соответвовать какому-то конкретному числу из этой записи, а не смыслом, который в нём читается. Иначе получается, что одними и теми же символами мы можем одновременно записать разные числа — что не способствует конструктивным построениям.

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

    • tyomitch
      /#20005082

      Не понял, почему «одними и теми же символами мы можем одновременно записать разные числа».
      Вот есть обозначение «одинадцать» — каким ещё числам оно соответствует, кроме числа 11?

      • force
        /#20005130

        Смотрите. У нас есть тридцатичетырёхричная система счистления (буквы русского языка + пробел). Условно говоря а — 0, я — 32. Соответственно «слово»: гад = 4 * 34 * 34 + 0 * 34 + 5
        «Слово» одиннадцать тоже соответствует какому-то числу, как и слово жопа, как и слово то число которое нельзя называть записать. И даже если в рускком языке слово кажется осмысленным, оно имеет совершенно конкретное значение, соответствующее единственному числу согласно правилам записи таких чисел.

        • ksbes
          /#20005460

          Здесь имеется именно смысловое описание. Т.е. «число Грея» (кстати, меньше 80ти символов!) — это именно вон то самое число Грея, а не цифра в base33-RU

          • force
            /#20005808 / +2

            Вроде бы не похоже на смысловое

            Такое число обязано существовать: из восьмидесяти русских букв и пробелов можно составить всего 3480 обозначений, значит, с использованием восьмидесяти букв можно обозначить не более 3480 чисел. Значит, некое число, не большее чем 3480, обозначить таким образом невозможно.

            А если смысловое, то весь пассаж не имеет смысла, т.к. ваш же пример противоречит последней фразе.

            • ksbes
              /#20005878 / +1

              Я так полагаю, что здесь не совсем корректный перевод/выражение.
              Имеется ввиду, всего чисел описываемых 80ю буквами не более 34^80. Но приняв это мы вроде как получаем + 1 такое число.


              Но это странно, т.к. это +1 "появится" из ранее бессмысленных комбинаций букв. Я тоже как-то не понимаю этот парадокс — потому и упомянул число Грея

              • TheShock
                /#20006650 / +1

                Имеется ввиду, всего чисел описываемых 80ю буквами не более 34^80. Но приняв это мы вроде как получаем + 1 такое число.

                У нас есть правила, по которым мы описываем числа. Если при изменении правил подходит число А — значит перестает подходить число Б.

            • tyomitch
              /#20006954

              Именно смысловое, а не тридцатичетыричное.
              34-ричные комбинации использовались только для подсчёта возможных обозначений, а не для определения обозначаемых чисел.

      • synedra
        /#20006538 / +2

        <grammar_mode>
        Оно и числу один*н*адцать не соответствует.
        </grammar_mode>

        Способов сопоставлять символьные последовательности числам мы можем придумать бесконечно много; парадокс, однако, возникает только при выборе одного из них и только если этот способ является собственным метаязыком, т.е. может содержать (возможно, непрямым образом) аналог фразы "данное предложение" или eval. Таковыми являются все тюринг-полные языки программирования и вроде бы все натуральные. Это очередной парадокс вида "Существует такая хреновина, что она не соответствует своему описанию в данном предложении". Если она действительно существует, то ей придётся соответствовать описанию (а иначе это какая-то другая хреновина). Но если она таки соответсвует описанию — то это вовсе не та хреновина, а всё-таки какая-то другая. В данном случае более строгая формулировка будет "Существует такое число, кратчайшее возможное описание которого на русском языке длиннее данного предложения". Парадокс по сути эквивалентен парадоксу лжеца, когда утверждение (в данном случае косвенно) утверждает свою ложность.

        • tyomitch
          /#20006940

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

      • flashkot
        /#20007518

        «Одиннадцать» может означать любое число начина с 3 и до бесконечности, потому что «по факту» это «база + 1».

        А ещё хочу вот предложить универсальный скрипт на питоне, который может выводит любые числа (и не только числа, вообще всё что угодно). Занимает всего 54 байта.

        #!/usr/bin/env python
        import sys
        print sys.argv[1]

        Хотим, к примеру, вывести на экран число Пи с точностью до двадцатого знака, выполняем

        anynum.py 3,14159265358979323846

        Или можно ещё вот так подойти к решению проблемы: есть такая дёмка Advanced Raytracing. «Занимает» всего 256 байт, но при этом выводит на экран картинку (которую можно увидеть на скриншоте, если по ссылке перейти) которая в виде гифки весит 64кб.

        И ещё, если вдруг не натыкались: онлайн библиотека в которой хранятся вообще все тексты которые когда либо были написаны или только ещё будут написаны (правда всё только на английском, так что или транслит или в переводе).

        А если серьёзно, то это всё очень похоже на философские жонглирования или шутки типа «данное выражение ложно».

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

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

        И вот что ещё меня беспокоит во всей этой затее. Если ещё раз перечитать про колмогоровскую случайность, то можно представить что взяв, скажем, джаваскрипт мы таки найдём строку в 1024 байта которую нельзя вывести программой такой же длинны. То есть программа конечно и для этого числа найдётся, вот только будет длинной, скажем, в 1600 байт.

        И на джаваскрипте код этой программы может выглядеть как-то вот так. Всматриваемся в содержимое поля «Original source» и видим что там одна сплошная математика. Сложение, вычитание, косинусы, квадратные корни, битовая ерунда всякая. Я охотно верю что примерно такой код и будет для тех самых «несжимаемых» чисел. Писали писали алгоритм, а он, зараза, длиннее чем 1024 байта. Ну, нас ведь предупреждали, что есть такие вот числа, верно? Ну вот, это оно самое.

        А теперь жмём кнопку «Pack» и получаем программу которая почти в два раза короче (821 байт) и при этом делает ровно тоже самое что и оригинал. Неувязочка.

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

        • TheShock
          /#20007586

          А теперь жмём кнопку «Pack» и получаем программу которая почти в два раза короче (821 байт) и при этом делает ровно тоже самое что и оригинал. Неувязочка.
          Ну, значит это не то число, которое нельзя вместить в 1024 байта программы, никакой неувязочки.

          • flashkot
            /#20008192

            У нас тут на самом деле аж две неувязочки. Хотя, лучше использовать слово «обман».

            Первый обман это когда мы говорим «смотрите, эта программа длинной 821 байт выводит строку длиной 1024 байта». На самом деле у нас есть программа которая генерирует вторую программу. А вот уже та вторая программа (длинной 1600 байт) и выводит нужную нам строку.

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

            • tyomitch
              /#20008338

              Байткод как раз не мешает: во-первых, нет проблем создать железку, которая будет выполнять непосредственно байткод — как Java-процессоры. Во-вторых, можно посчитать движок V8 частью программы, и порог парадокса сдвинется с 1КБ на (1КБ + размер V8), но качественно ничего не изменится.

              • flashkot
                /#20009626

                В таком случае всё в порядке. Либо всегда есть строка которую мы не можем вывести скриптом такой же длинны. Либо мы используем для этого программу размером в десяток мегабайт, а с таким ограничением мы сможем вывести все возможные строки длиной в 1024 байта.

        • tyomitch
          /#20008310

          «Одиннадцать» может означать любое число начина с 3 и до бесконечности, потому что «по факту» это «база + 1».

          Для математика — да. Для нормального человека, и в том числе для философа Рассела — оно означает 11 в десятичной системе.
          Точно так же, «год смерти Тьюринга» для нормального человека означает 1954, хотя я подозреваю, что хотя бы один носитель фамилии Тьюринг умирает каждый год.

          Исток парадокса Берри — не математический, а именно философский: Рассел и его корреспонденты пытались понять связь между объектами и их общепринятыми, общепонятными обозначениями.

  7. sl0
    /#20004672 / +1

    Как и любой другой парадокс этот основан на смешении мета-языка и языка-объекта. Об этом давно еще писал Альфред Тарский, — нельзя в фразе (язык-объект) говорить о ней самой (мета-язык).

  8. irvinatkins
    /#20004674

    самое маленькое число, для обозначения которого недостаточно восьмидесяти букв плюс 1

    а вот это не решение?

    • tyomitch
      /#20004682

      Если первое число не существует, то и со вторым получается проблема :)

  9. amarao
    /#20005488

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

  10. ioannes
    /#20005926 / +4

    Это парадокс Самореференции возникающий из-за смешения языка и метаязыка. «Самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» не является обозначением числа, а описывает язык обозначения чисел.
    Аналогично с программой, она не самостоятельна, а включает в себя все множество программ, тоже является метапрограммой.

    • Saiho
      /#20007792 / +1

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

      Так в чем же разница? Элементарно в недоопределенности условий первой формулировки и полной определенности (условно, боюсь найдется и в этом случае возможность трактовать по-разному) второй. В первом случае необходимо дополнительно описать все обозначения, которыми владеет субъект. А еще для разных субъектов это будут разные наборы обозначений. И для разных моментов времени для одного и того же субъекта набор обозначений будет отличаться. Но если со всем этим справиться, то будем иметь четкий алгоритм выбора самого маленького числа, для обозначения которого недостаточно восьмидесяти букв для конкретного субъекта в конкретный момент времени. И он будет столь же точным, как и выбор наименьшего двоичного числа для второго примера.

      А автору все-же формально следует заменить 34^80 на 35^80 и фразу «из восьмидесяти русских букв и пробелов» на «из восьмидесяти русских букв, пробелов и запятых», ведь вы посчитали запятую в 78 символов длины строки. Или как-то иначе устранить несоответствие.

      • synedra
        /#20007842 / +1

        Разве есть проблема с фразой «Самое маленькое число, для записи которого недостаточно восьмидесяти двоичных цифр»?

        Нет, потому что эта фраза не записана двоичными цифрами. Нет самореференции — нет и парадокса.

        • Saiho
          /#20009358

          Совсем нет. Фактически она двоичными цифрами и записана. Вы же ее на экране монитора прочитали? Каждую букву можно обозначить двоичным кодом и получить взаимно однозначное отображение двух множеств. Т. е. подмена алфавита ни на что повлиять не может (это просто «замена переменной в уравнении»), только количество нужно тоже менять во фразе поскольку оно зависит от алфавита.

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

          very_long_int Самое_маленькое_число_для_обозначения_которого_недостаточно_восьмидесяти_букв;
          very_long_int description_len(very_long_int);

          Самое_маленькое_число_для_обозначения_которого_недостаточно_восьмидесяти_букв = min(
          description_len(1) > 80 ? 1 ; NULL,
          description_len(2) > 80 ? 2; NULL,
          ...
          description_len(35^80+1) > 80 ? 35^80+1 ; NULL
          )

          very_long_int description_len(very_long_int i) {
          /* Здесь должно быть определение понятий субъекта на данный момент времени в виде одномерного массива строк, которое не определено в исходной задаче. Каждому индексу соответствует строка обозначения числа равного индексу.*/

          return len(description_string[i]);
          };

          Это просто нормальное математическое утверждение (при условии полного определения задачи, как писал об этом выше). Наверняка вы могли бы написать код и поизящнее чем это сделал я. Но особо и не старался, честно говоря. Главная цель — показать, что в определении значения переменной ни сама переменная ни ссылка на нее не используется и значит Самореференции быть не может. Просто не следует отождествлять строку символов (обозначение) с ее смысловой нагрузкой в понимании субъекта.

          • ioannes
            /#20009568

            Просто не следует отождествлять строку символов (обозначение) с ее смысловой нагрузкой в понимании субъекта.


            Это как раз и есть разделение языка и метаязыка.

            • Saiho
              /#20009718 / +1

              Об этом и речь. Их не стоит смешивать. В моей «программе» субъект представлен одномерным массивом строк. Это не метаязык, а просто язык. В самом коде метаязыка вообще нет.

      • ioannes
        /#20008308

        Меняя алфавит мы однозначно разделяем язык и метаязык и парадокс исчезает. В случае фразы «Самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» получается нечто похожее на Парадокс Греллинга — Нельсона, когда фраза и описывает саму себя и одновременно опровергает себя.

        • ksbes
          /#20009030

          Мне лично больше нравится подход фон Неймана: данные и код — это одна и та же неразделимая сущность (т.е. bmp-файл — это программа для отображения картинки). И в таком подходе нет разделения на «язык» и «мета-язык». Потому допустима и рекурсия.

          Но в таком представлении парадокс тоже буксует: в означенной длине вполне можно записать слово «бесконечность» и, следовательно, такого числа (минимального из всех, что можно описать 80-ю символами) просто может не существовать (это уже надо строго доказывать). Т.е. эта фраза просто не описывает числа.

          • ioannes
            /#20009086

            Есть формальное описание описание языка, на пример описание BMP файла, которое не в состоянии отобразить ни одной картинки — вот это метаязык по отношению к «программе для отображения картинки».

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

            • ksbes
              /#20009234

              У фон Неймана описание BMP файла и сам BMP файл — это именно сущности одного порядка. И то что наши компьютеры пока не доросли до того, что бы по команде «а сгенери-ка мне пейзажик» выдавать картинку — это чисто технические сложности.
              Т.е. тут можно спорить с таким подходом и находить парадоксы, но мне больше нравится воспринимать так (возможно детская травма от кодогенерации тройного порядка SQL DDL->xml->Java->PHP, наш тимлид был затейник).

        • Saiho
          /#20009404

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

  11. mafia8
    /#20008496

    — Что такое парадокс?
    — Двоюродный брат фокуса (который показывает фокусник), там он прячет кролика в ящике, а тут тоже что-то похожее делают.

    По условию каждому набору букв соответствует число некоторое, пропуски чисел возможны (какие-то числа меньше 34^80 не будут использованы, а будут использованы бОльшие числа). Есть массив чисел и есть массив строк, каждая строка указывает на число. Сто — это просто 100, гугол — это просто гугол. А одна строка пытается через логику указать на число за пределом этого массива.

    • tyomitch
      /#20008546

      каждому набору букв соответствует число некоторое

      Не обязательно. Обозначению «абырвалг» не соответствует никакое число, как и обозначению «быстрая коричневая лиса», как и обозначению «натуральное число между двумя и тремя».

  12. ksbes
    /#20009078

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

    • tyomitch
      /#20009676

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

      • ksbes
        /#20009804

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

        А алгоритм сжатия и расшифровки конечного и неслучайного текста я вам привёл. Сжимается такой текст ровно в 1 бит.
        (Я не понимаю, вы Шеннона решили опровергнуть?)

        • tyomitch
          /#20010198

          При чём тут Шеннон?

          Возьмём практический алгоритм сжатия JPEG — он работает со стохастическим потоком, или с двумерной матрицей наперёд известного размера?

          • ksbes
            /#20010310

            Шеннон ввёл понятие информационной энтропии и доказал парочку — другую теорем про неё связи с обменом сообщениями. Не? В частности там что-то есть и про сжатие…

            Алгоритм JPEG работает со стохастическим потоком матриц заранее неизвестных размеров. По крайней мере у меня одной и той же программой в JPEG сохраняются как картинки 1x1, так и 1023х767 и никаких ограничений он на меня не накладывал.
            Очень сомнительно практическое будущее алгоритма способного работать с матрицами только наперёд известного размера.

            • tyomitch
              /#20010332

              Вы можете привести утверждение Шеннона, которое, по-вашему, я пытаюсь опровергнуть?

              По-видимому, мы с вами по-разному понимаем, что такое «поток». Обычно «поток» — это то, в начале чего неизвестно, когда будет конец. Изображения от потока принципиально отличаются тем, что размер изображения известен ещё до чтения первого элемента матрицы.

              • ksbes
                /#20010376

                Что энтропия конечного и неслучайного текста выше нуля и потому имеет какой-то разумный смысл рассматривать алгоритмы сжатия и кодирования таких объектов.

              • ksbes
                /#20010538

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

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

                • tyomitch
                  /#20010556

                  Нигде и никогда? Я же специально поставил ссылку на википедию.

  13. juray
    /#20009420 / -1

    из восьмидесяти русских букв и пробелов можно составить всего 3480 обозначений, значит, с использованием восьмидесяти букв можно обозначить не более 3480 чисел. Значит, некое число, не большее чем 3480, обозначить таким образом невозможно.
    Только при дополнительном условии — числа обозначаются подряд, без пропусков.

    Рассмотрим элементарный пример на двоичном алфавите (0 и 1).
    Комбинация из 2 двоичных символов имеет 4 варианта — и обычно считается, что число, представленное двумя двоичными разрядами, не может превышать 4 (при отсчете с 1) или даже 3 (если считаем от 0).

    Но при табличном сопоставлении с пропусками может быть и так:
    00 = 1
    01 = 2
    10 = 4
    11 = 8

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

    Опять же лучше упростить до более простого примера. Возьмём язык HQ9+, состоящий из 4 инструкций (собственно, H,Q, 9 и +). Как вы думаете, какое число может вывести программа из одной инструкции?
    Инструкция H выводит «Hello, world!», что в машинном представлении является числом. Для 8-битной кодировки получаем 13 байт, в десятичной системе это где-то в диапазоне 1020 — 1030.
    Инструкция 9 выводит «99-бутылочный тест», то есть «99 бутылок пива стоят на стене. Одна упала. 98 бутылок пива стоят на стене. Одна упала. 97 бутылок...» и так далее. Это тоже число, и еще более огромное.

    • tyomitch
      /#20009612

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

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

      Если вы вместо «некое число, не большее чем 3480, обозначить таким образом невозможно» прочитали «никакое число, большее чем 3480, обозначить таким образом невозможно» — то вы ошиблись :-)

      • juray
        /#20009908

        Увы, я так и прочитал, упустил частицу «не».
        Но если прочитать правильно — то смысла в этой фразе я вообще не вижу. Почему невозможно?

        • tyomitch
          /#20010050

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

          • TheShock
            /#20010150

            Почему?

            • tyomitch
              /#20010210

              Потому что какие-то из пересчитанных обозначений не соответствуют числам из первых 3480.

          • juray
            /#20010252

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

            В случае сплошного сопоставления — таки не понимаю, с чего невозможно-то. Если это возможно для алфавита из цифр, то почему нет для расширенного? По сути, «обозначение, составленное из букв» само по себе является числом, записанным в системе счисления с основанием, равным количеству букв в алфавите (то есть буква — это цифра).

            • tyomitch
              /#20010318

              Каким числам вы бы сопоставили строки «абырвалг», «быстрая коричневая лиса» и «натуральное число между двумя и тремя»?

              Речь в статье не об изобретении новой кодировки «base34-RU», а об обозначениях чисел, используемых людьми и понятных людям, — таких, как «одиннадцать», «пять девяток», и «год смерти Тьюринга».

              • juray
                /#20010448

                Каким числам вы бы сопоставили строки «абырвалг»

                Ну, например, 0xE0E1FBF0E2E0EBE3
                а об обозначениях чисел, используемых людьми и понятных людям

                А обозначение типа 0x5A081F — не понятно людям?

                • tyomitch
                  /#20010534

                  Вы хотите меня убедить, что если вместо привычных людям обозначений взять вашу кодировку, то парадокс Берри не возникнет?
                  Совершенно верно, не возникнет. А при использовании привычных людям обозначений — возникает.

                  • ksbes
                    /#20010610 / +1

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

                    Если же эти фразы валидны, то валидна и фраза:
                    — «все натуральные числа»
                    И снова, парадокса нет.

                    Что скажете?

                    • tyomitch
                      /#20010624

                      Совершенно верно, ваши фразы — как и ключевая — не указывают ни на какие числа.
                      Разница в том, что для ваших фраз это очевидно, а для ключевой — не столь очевидно.

            • ksbes
              /#20010350 / +1

              Есть бессмысленные комбинации букв. И для «человеческого» описания цифр (т.е. не кодирование, а простой язык) таких комбинаций будет большинство.

              Но это не имеет особого значения в данном парадоксе: главное что это НЕ все возможные _натуральные_ числа (для ненатуральных парадокс не работает).
              Следовательно среди оставшихся должно найтись наименьшее ( это свойство любого подмножества натуральных чисел).

              Тут как раз можно и провести атаку на парадокс: составить рекурсивное описание, которое назовёт каждое натуральное число.

              • juray
                /#20010456

                А почему бессмысленные комбинации букв не могут быть обозначениями чисел? Что-то я не вижу, чтобы требование осмысленности оговаривалось в тексте.

                • ksbes
                  /#20010464 / +1

                  Да какая разница? Для парадокса важно, что в рамках 80ти символов нельзя назвать каждое число.

                  А осмысленность требуется чтобы работала ключевая фраза: «наименьшее число, которое нельзя описать меньше чем ста символами»

                • tyomitch
                  /#20010514

                  Во втором предложении статьи оговаривается, что словом «одиннадцать» принято обозначать число 11, а не 0xd0bed0b4d0b8d0bdd0bdd0b0d0b4d186d0b0d182d18c. По-моему, из этого ясно, что речь идёт о смысле, а не о тридцатичетыричной (или любой другой) кодировке.

                  • juray
                    /#20010604

                    Совершенно неясно, поскольку пассаж о «из восьмидесяти русских букв и пробелов можно составить всего 3480 обозначений» склоняет именно к 34-ричной системе кодирования.

                    • tyomitch
                      /#20010648

                      Вы не один такой, force тоже подумал про 34-ричное кодирование. В действительности, 34-ричные комбинации используются только для подсчёта возможных обозначений, а не для определения обозначаемых чисел.

                      Если предложите, как сформулировать эту идею понятнее, то я охотно исправлю статью.

                      • juray
                        /#20012068

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

  14. Keyten
    /#20020850

    Или не завершится? Ведь среди всех программ, которые будут испробованы, встретится while True: pass (и её функциональные аналоги) — и дальше проверки такой программы дело уже не пойдёт!

    Вообще не обязательно.
    Давайте сделаем так: разобьём каждую программу на некие атомарные операции и сделаем очередь программ. Затем будем каждую итерацию добавлять в список следующую программу и исполнять по одной атомарной итерации из каждой программы списка.
    Таким образом, любая программа будет запущена через некоторое конечное время.

    (что конечно же не сработает на практике, но ведь мы не об этом говорим?)

    • ksbes
      /#20021038

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

      • Keyten
        /#20021066

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

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

    • tyomitch
      /#20023926

      Таким образом, любая программа будет запущена через некоторое конечное время.

      Вы правы, ваш подход это обеспечит.
      Но в какой момент программа-генератор может выводить до сих пор не «вычеркнутое» число в качестве искомого? Может быть, одна из запущенных программ через несколько шагов его как раз выведет и тем самым «вычеркнет»?