Задача сжатия данных в своей простейшей форме может относиться к числам и их обозначениям. Числа можно обозначать числительными («одиннадцать» для числа 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)
vvadzim
09.04.2019 10:41+1Та программа на питоне, если она в килобайт укладывается, сгенерит и запустит в т.ч. и себя и будет ждать остановки. А тот второй экземпляр тоже сгенерит и запустит себя и тоже будет ждать остановки. И так до бесконечности.
В приведённом в статье алгоритме просто есть бесконечный цикл, соответственно до фазы поиска самого маленького числа в словаре управление никогда не дойдёт и самого маленького программа не выведет.
farafonoff
09.04.2019 10:41Очевидно, не каждая последовательность букв обозначает число. Например — «Самое Большое Простое Число». Так что в парадоксе нет ничего парадоксального.
Нетрудно заметить, что приведенный алгоритм из второй части статьи рано или поздно найдет сам себя, таким образом он эквивалентен тому что используется в доказательстве «проблемы останова».
tyomitch Автор
09.04.2019 14:30Какое отношение к этому парадоксу имеет то, что не каждая последовательность букв обозначает число?
farafonoff
09.04.2019 16:09Самое прямое. Фраза «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» тоже не обозначает число, согласно приведенных в статье рассуждений.
synedra
09.04.2019 20:11+1Есть разница. Фраза "Самое большое простое число" обозначает некий критерий, которому число может или соответствовать, или нет: оно должно быть простым и быть больше всех остальных простых чисел. Ему ничего не соответсвует, так же как критериям "простое число, кратное пяти", "четвёртый муж королевы Виктории" или "сочинения Сократа о Платоне". Но это свойство реальности, а не самого определения. Если бы простые числа были устроены иначе, а Сократ любил бы писать диалоги о своих учениках — эти фразы означали бы конкретные числа и тексты.
А фраза «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» (высказывание, не последовательность символов; очевидно, что Рассел писал не на русском, но нам не приходится переходить на английский для обсуждения этого парадокса) внутренне противоречива. Она, грубо говоря, не может корректно парситься.
Akon32
09.04.2019 12:40+1какое самое маленькое число, для обозначения которого недостаточно восьмидесяти букв?
Такое число обязано существовать: из восьмидесяти русских букв и пробелов можно составить всего 34^80 обозначений, значит, с использованием восьмидесяти букв можно обозначить не более 34^80 чисел.Это совершенно не означает, что минимальное число будет порядка 34^80. Есть тенденция обозначать огромные числа кратко, "гугол" = 10^100 — всего 5 букв. Утверждение, что такое число обязано существовать, хотя оно и верное, кажется мне нереалистичным по причине того, что завязано на семантику слов в каком-то языке. После того, как мы назовём число, люди могут придумать более краткое обозначение для ещё большего числа, и даже задействовать старое слово для нового понятия.
какое самое маленькое число, для вывода которого недостаточно килобайтной программы?
Не обязательно перебирать 256^1024 программ.
Можно подойти как раз со стороны колмогороской сложности — взять чисто случайное число, записываемое объёмом 1кбайт+1бит, записать его в десятичном, шестнадцатеричном виде, или в аналоге base64 (это компактнее) и добавить код для раскодирования наподобие "print(...)".tyomitch Автор
09.04.2019 14:34Это совершенно не означает, что минимальное число будет порядка 34^80.
Минимальное число было бы намного меньше 3480 — уже хотя бы потому, что не все последовательности букв являются описаниями чисел.
Но поскольку его не существует, то нет смысла обсуждать, какого порядка оно было бы.
Вторую часть вашего комментария я не понял. Взять чисто случайное число, и что дальше? Оно чисто случайно окажется тем самым самым маленьким числом, которое мы ищем?Akon32
09.04.2019 14:57Вторую часть вашего комментария я не понял. Взять чисто случайное число, и что дальше?
Я некорректно понял задачу — посчитал, что можно предоставить число минимальной длины, которое не влезет в 1кбайт программы. Очевидно, не все такие числа минимальны.
nikandr23
09.04.2019 23:42можно написать
for i=1 to Мульярд
и в цикле фигачить print(...)
ах,
нам нужна длинная прога аж в килобайт?
ну давайте натулим 10 вложенных for…tyomitch Автор
10.04.2019 09:48Проблема не в том, чтобы напечатать очень большое число; проблема в том, чтобы найти самое маленькое число, которое напечатать нельзя.
force
09.04.2019 13:28+1Не понял порадокса с 80 буквами. Если мы определяем запись числа буквами, то фраза самое маленькое число, для обозначения которого недостаточно восьмидесяти букв будет соответвовать какому-то конкретному числу из этой записи, а не смыслом, который в нём читается. Иначе получается, что одними и теми же символами мы можем одновременно записать разные числа — что не способствует конструктивным построениям.
В качестве примера, часто использующееся DEADBEEF, которые означает конкретное число 3735928559, а не кусок говядины, случайно обнаружившийся в компьютере.tyomitch Автор
09.04.2019 15:17Не понял, почему «одними и теми же символами мы можем одновременно записать разные числа».
Вот есть обозначение «одинадцать» — каким ещё числам оно соответствует, кроме числа 11?force
09.04.2019 15:24Смотрите. У нас есть тридцатичетырёхричная система счистления (буквы русского языка + пробел). Условно говоря а — 0, я — 32. Соответственно «слово»: гад = 4 * 34 * 34 + 0 * 34 + 5
«Слово» одиннадцать тоже соответствует какому-то числу, как и слово жопа, как и слово то число которое нельзяназыватьзаписать. И даже если в рускком языке слово кажется осмысленным, оно имеет совершенно конкретное значение, соответствующее единственному числу согласно правилам записи таких чисел.
ksbes
09.04.2019 16:22Здесь имеется именно смысловое описание. Т.е. «число Грея» (кстати, меньше 80ти символов!) — это именно вон то самое число Грея, а не цифра в base33-RU
force
09.04.2019 17:22+2Вроде бы не похоже на смысловое
Такое число обязано существовать: из восьмидесяти русских букв и пробелов можно составить всего 3480 обозначений, значит, с использованием восьмидесяти букв можно обозначить не более 3480 чисел. Значит, некое число, не большее чем 3480, обозначить таким образом невозможно.
А если смысловое, то весь пассаж не имеет смысла, т.к. ваш же пример противоречит последней фразе.ksbes
09.04.2019 17:34+1Я так полагаю, что здесь не совсем корректный перевод/выражение.
Имеется ввиду, всего чисел описываемых 80ю буквами не более 34^80. Но приняв это мы вроде как получаем + 1 такое число.
Но это странно, т.к. это +1 "появится" из ранее бессмысленных комбинаций букв. Я тоже как-то не понимаю этот парадокс — потому и упомянул число Грея
TheShock
09.04.2019 20:30+1Имеется ввиду, всего чисел описываемых 80ю буквами не более 34^80. Но приняв это мы вроде как получаем + 1 такое число.
У нас есть правила, по которым мы описываем числа. Если при изменении правил подходит число А — значит перестает подходить число Б.
tyomitch Автор
09.04.2019 21:56Именно смысловое, а не тридцатичетыричное.
34-ричные комбинации использовались только для подсчёта возможных обозначений, а не для определения обозначаемых чисел.
synedra
09.04.2019 19:54+2<grammar_mode>
Оно и числу один*н*адцать не соответствует.
</grammar_mode>
Способов сопоставлять символьные последовательности числам мы можем придумать бесконечно много; парадокс, однако, возникает только при выборе одного из них и только если этот способ является собственным метаязыком, т.е. может содержать (возможно, непрямым образом) аналог фразы "данное предложение" или
eval. Таковыми являются все тюринг-полные языки программирования и вроде бы все натуральные. Это очередной парадокс вида "Существует такая хреновина, что она не соответствует своему описанию в данном предложении". Если она действительно существует, то ей придётся соответствовать описанию (а иначе это какая-то другая хреновина). Но если она таки соответсвует описанию — то это вовсе не та хреновина, а всё-таки какая-то другая. В данном случае более строгая формулировка будет "Существует такое число, кратчайшее возможное описание которого на русском языке длиннее данного предложения". Парадокс по сути эквивалентен парадоксу лжеца, когда утверждение (в данном случае косвенно) утверждает свою ложность.tyomitch Автор
09.04.2019 21:53Вся прелесть этого парадокса в том, что с одной стороны он похож на парадокс лжеца, но не совсем; а с другой — на проблему остановки, но не совсем.
flashkot
10.04.2019 02:13«Одиннадцать» может означать любое число начина с 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
10.04.2019 03:02А теперь жмём кнопку «Pack» и получаем программу которая почти в два раза короче (821 байт) и при этом делает ровно тоже самое что и оригинал. Неувязочка.
Ну, значит это не то число, которое нельзя вместить в 1024 байта программы, никакой неувязочки.flashkot
10.04.2019 09:40У нас тут на самом деле аж две неувязочки. Хотя, лучше использовать слово «обман».
Первый обман это когда мы говорим «смотрите, эта программа длинной 821 байт выводит строку длиной 1024 байта». На самом деле у нас есть программа которая генерирует вторую программу. А вот уже та вторая программа (длинной 1600 байт) и выводит нужную нам строку.
Второй обман заключается в том что мы выдаём исходный текст программы за байткод который непосредственно и будет выполнять наша машина. В случае джаваскрипта байткод может занимать сильно больше места чем исходный текст из которого он был создан (вот тот кусок скрипта что я использовал для примера распухает почти в два раза после перевода в байткод для V8). Не знаю что там в питоне, но не буду удивлён если ситуация аналогичная.tyomitch Автор
10.04.2019 10:06Байткод как раз не мешает: во-первых, нет проблем создать железку, которая будет выполнять непосредственно байткод — как Java-процессоры. Во-вторых, можно посчитать движок V8 частью программы, и порог парадокса сдвинется с 1КБ на (1КБ + размер V8), но качественно ничего не изменится.
flashkot
10.04.2019 14:10В таком случае всё в порядке. Либо всегда есть строка которую мы не можем вывести скриптом такой же длинны. Либо мы используем для этого программу размером в десяток мегабайт, а с таким ограничением мы сможем вывести все возможные строки длиной в 1024 байта.
tyomitch Автор
10.04.2019 10:00«Одиннадцать» может означать любое число начина с 3 и до бесконечности, потому что «по факту» это «база + 1».
Для математика — да. Для нормального человека, и в том числе для философа Рассела — оно означает 11 в десятичной системе.
Точно так же, «год смерти Тьюринга» для нормального человека означает 1954, хотя я подозреваю, что хотя бы один носитель фамилии Тьюринг умирает каждый год.
Исток парадокса Берри — не математический, а именно философский: Рассел и его корреспонденты пытались понять связь между объектами и их общепринятыми, общепонятными обозначениями.
sl0
09.04.2019 14:28+1Как и любой другой парадокс этот основан на смешении мета-языка и языка-объекта. Об этом давно еще писал Альфред Тарский, — нельзя в фразе (язык-объект) говорить о ней самой (мета-язык).
irvinatkins
09.04.2019 14:28самое маленькое число, для обозначения которого недостаточно восьмидесяти букв плюс 1
а вот это не решение?tyomitch Автор
09.04.2019 14:28Если первое число не существует, то и со вторым получается проблема :)
amarao
09.04.2019 16:28Я рад, что вопрос брут-форса алгоритмов перебором кода, закрыли на самой заре CS. Ибо иначе матпорнография какая-то получается: «Мы только что показали, что хоть какая-то программа существует, значит задача решена».
ioannes
09.04.2019 17:40+4Это парадокс Самореференции возникающий из-за смешения языка и метаязыка. «Самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» не является обозначением числа, а описывает язык обозначения чисел.
Аналогично с программой, она не самостоятельна, а включает в себя все множество программ, тоже является метапрограммой.Saiho
10.04.2019 07:18+1Не могу с вами согласиться. Не вижу в фразе «Самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» самореференции. Разве есть проблема с фразой «Самое маленькое число, для записи которого недостаточно восьмидесяти двоичных цифр»? Если бы самореференция имела место, то замена алфавита не могла бы ее убрать. И уж тем более не повлияла бы замена обозначение/запись т. к. запись это частный случай обозначения.
Так в чем же разница? Элементарно в недоопределенности условий первой формулировки и полной определенности (условно, боюсь найдется и в этом случае возможность трактовать по-разному) второй. В первом случае необходимо дополнительно описать все обозначения, которыми владеет субъект. А еще для разных субъектов это будут разные наборы обозначений. И для разных моментов времени для одного и того же субъекта набор обозначений будет отличаться. Но если со всем этим справиться, то будем иметь четкий алгоритм выбора самого маленького числа, для обозначения которого недостаточно восьмидесяти букв для конкретного субъекта в конкретный момент времени. И он будет столь же точным, как и выбор наименьшего двоичного числа для второго примера.
А автору все-же формально следует заменить 34^80 на 35^80 и фразу «из восьмидесяти русских букв и пробелов» на «из восьмидесяти русских букв, пробелов и запятых», ведь вы посчитали запятую в 78 символов длины строки. Или как-то иначе устранить несоответствие.synedra
10.04.2019 07:57+1Разве есть проблема с фразой «Самое маленькое число, для записи которого недостаточно восьмидесяти двоичных цифр»?
Нет, потому что эта фраза не записана двоичными цифрами. Нет самореференции — нет и парадокса.
Saiho
10.04.2019 13:18Совсем нет. Фактически она двоичными цифрами и записана. Вы же ее на экране монитора прочитали? Каждую букву можно обозначить двоичным кодом и получить взаимно однозначное отображение двух множеств. Т. е. подмена алфавита ни на что повлиять не может (это просто «замена переменной в уравнении»), только количество нужно тоже менять во фразе поскольку оно зависит от алфавита.
В исходной фразе просто нет самореференции, нет описания себя через себя, поскольку обозначению в виде текстовой строки (имени переменной) задается значение в терминах каких-то вычислений, не использующих саму эту переменную. Попробую изобразить в чертикаком коде, но должно быть понятно:
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
10.04.2019 13:58Просто не следует отождествлять строку символов (обозначение) с ее смысловой нагрузкой в понимании субъекта.
Это как раз и есть разделение языка и метаязыка.Saiho
10.04.2019 14:28+1Об этом и речь. Их не стоит смешивать. В моей «программе» субъект представлен одномерным массивом строк. Это не метаязык, а просто язык. В самом коде метаязыка вообще нет.
ioannes
10.04.2019 10:00Меняя алфавит мы однозначно разделяем язык и метаязык и парадокс исчезает. В случае фразы «Самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» получается нечто похожее на Парадокс Греллинга — Нельсона, когда фраза и описывает саму себя и одновременно опровергает себя.
ksbes
10.04.2019 12:09Мне лично больше нравится подход фон Неймана: данные и код — это одна и та же неразделимая сущность (т.е. bmp-файл — это программа для отображения картинки). И в таком подходе нет разделения на «язык» и «мета-язык». Потому допустима и рекурсия.
Но в таком представлении парадокс тоже буксует: в означенной длине вполне можно записать слово «бесконечность» и, следовательно, такого числа (минимального из всех, что можно описать 80-ю символами) просто может не существовать (это уже надо строго доказывать). Т.е. эта фраза просто не описывает числа.ioannes
10.04.2019 12:19Есть формальное описание описание языка, на пример описание BMP файла, которое не в состоянии отобразить ни одной картинки — вот это метаязык по отношению к «программе для отображения картинки».
И да, «бесконечность» это слишком много и не совсем число, давайте возьмем число «Самое большое число» и получим такую же динамически самоувеличивающуюся переменную.ksbes
10.04.2019 12:52У фон Неймана описание BMP файла и сам BMP файл — это именно сущности одного порядка. И то что наши компьютеры пока не доросли до того, что бы по команде «а сгенери-ка мне пейзажик» выдавать картинку — это чисто технические сложности.
Т.е. тут можно спорить с таким подходом и находить парадоксы, но мне больше нравится воспринимать так (возможно детская травма от кодогенерации тройного порядка SQL DDL->xml->Java->PHP, наш тимлид был затейник).
Saiho
10.04.2019 13:25Чуть выше ответил synedra как раз по этому поводу. Утверждаю, что в данном выражении Самореференции нет, нет и смешивания языка и метаязыка, а есть абсолютно нормальное математическое утверждение, однако в условиях недоопределенности задачи. Подробнее посмотрите пожалуйста одним уровнем выше.
mafia8
10.04.2019 10:33— Что такое парадокс?
— Двоюродный брат фокуса (который показывает фокусник), там он прячет кролика в ящике, а тут тоже что-то похожее делают.
По условию каждому набору букв соответствует число некоторое, пропуски чисел возможны (какие-то числа меньше 34^80 не будут использованы, а будут использованы бОльшие числа). Есть массив чисел и есть массив строк, каждая строка указывает на число. Сто — это просто 100, гугол — это просто гугол. А одна строка пытается через логику указать на число за пределом этого массива.tyomitch Автор
10.04.2019 10:44каждому набору букв соответствует число некоторое
Не обязательно. Обозначению «абырвалг» не соответствует никакое число, как и обозначению «быстрая коричневая лиса», как и обозначению «натуральное число между двумя и тремя».
ksbes
10.04.2019 12:17Интересно, а причём здесь сжатие данных?
Задачу (проблему) сжатия данных нельзя же рассматривать в отрыве такого понятия как стохастический поток сообщений (букв). Причём тут каждое слово важно — и стохастичность и наличие потока — т.е. достаточно большого количества.
Без этого сжать можно до одного бита (есть/нет вот эта длиннющая простыня захардкоженная в алгоритме сжатия/расшифровки — пресловутый «утюг в окне»)tyomitch Автор
10.04.2019 14:22Что мешает рассматривать алгоритмы сжатия конечных и неслучайных текстов? Например, русских числительных?
В конце концов, практически используемые алгоритмы сжатия работают именно с конечными и неслучайными файлами, а не с бесконечным стохастическим потоком.ksbes
10.04.2019 14:37Как раз именно со стохастическим потоком все практические алгоритмы дело и имеют — программа и её создатели ничего не знают о том что конкретно она будет сжимать на своём жизненном пути, только некую обобщённую статистику. Поэтому что-то жмётся хорошо, а что-то вообще увеличивается при использовании одного и того же алгоритма.
А алгоритм сжатия и расшифровки конечного и неслучайного текста я вам привёл. Сжимается такой текст ровно в 1 бит.
(Я не понимаю, вы Шеннона решили опровергнуть?)tyomitch Автор
10.04.2019 15:46При чём тут Шеннон?
Возьмём практический алгоритм сжатия JPEG — он работает со стохастическим потоком, или с двумерной матрицей наперёд известного размера?ksbes
10.04.2019 16:06Шеннон ввёл понятие информационной энтропии и доказал парочку — другую теорем про неё связи с обменом сообщениями. Не? В частности там что-то есть и про сжатие…
Алгоритм JPEG работает со стохастическим потоком матриц заранее неизвестных размеров. По крайней мере у меня одной и той же программой в JPEG сохраняются как картинки 1x1, так и 1023х767 и никаких ограничений он на меня не накладывал.
Очень сомнительно практическое будущее алгоритма способного работать с матрицами только наперёд известного размера.tyomitch Автор
10.04.2019 16:10Вы можете привести утверждение Шеннона, которое, по-вашему, я пытаюсь опровергнуть?
По-видимому, мы с вами по-разному понимаем, что такое «поток». Обычно «поток» — это то, в начале чего неизвестно, когда будет конец. Изображения от потока принципиально отличаются тем, что размер изображения известен ещё до чтения первого элемента матрицы.ksbes
10.04.2019 16:16Что энтропия конечного и неслучайного текста выше нуля и потому имеет какой-то разумный смысл рассматривать алгоритмы сжатия и кодирования таких объектов.
ksbes
10.04.2019 16:54По потокам- действительно понимание разное, нигде никогда не говорится, что у потока не может быть точно известного конца и начала. Он вполне может быть и фиксированной длинны. А может и не быть.
По файлам — сами файлы образуют «поток файлов». Никто не пишет «практический алгоритм» для кодирования одного, десяти или другого конечного, заранее известного количества файлов. Файлы — именно что неизвестно когда они в этих проклятых интернетах закончатся. Но мы должны сжать и распаковать их все (хотя и понятно, что их будет конечное количество — интернеты с JPEG когда-нибудь закончатся).
juray
10.04.2019 13:29-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 Автор
10.04.2019 14:07Только при дополнительном условии — числа обозначаются подряд, без пропусков.
Конечно же с пропусками: большая часть возможных обозначений не соответствует никаким числам.
В чём проблема?
Если вы вместо «некое число, не большее чем 3480, обозначить таким образом невозможно» прочитали «никакое число, большее чем 3480, обозначить таким образом невозможно» — то вы ошиблись :-)juray
10.04.2019 15:01Увы, я так и прочитал, упустил частицу «не».
Но если прочитать правильно — то смысла в этой фразе я вообще не вижу. Почему невозможно?tyomitch Автор
10.04.2019 15:30Раз возможных обозначений 3480, значит обозначаемых ими чисел не больше чем 3480, значит какие-то числа среди первых 3480 обозначить восьмидесятью буквами невозможно.
juray
10.04.2019 15:56большая часть возможных обозначений не соответствует никаким числам
а вот это оговорено не было. А кстати, почему не соответствует? Просто волевым решением?
В случае сплошного сопоставления — таки не понимаю, с чего невозможно-то. Если это возможно для алфавита из цифр, то почему нет для расширенного? По сути, «обозначение, составленное из букв» само по себе является числом, записанным в системе счисления с основанием, равным количеству букв в алфавите (то есть буква — это цифра).tyomitch Автор
10.04.2019 16:08Каким числам вы бы сопоставили строки «абырвалг», «быстрая коричневая лиса» и «натуральное число между двумя и тремя»?
Речь в статье не об изобретении новой кодировки «base34-RU», а об обозначениях чисел, используемых людьми и понятных людям, — таких, как «одиннадцать», «пять девяток», и «год смерти Тьюринга».juray
10.04.2019 16:32Каким числам вы бы сопоставили строки «абырвалг»
Ну, например, 0xE0E1FBF0E2E0EBE3
а об обозначениях чисел, используемых людьми и понятных людям
А обозначение типа 0x5A081F — не понятно людям?tyomitch Автор
10.04.2019 16:51Вы хотите меня убедить, что если вместо привычных людям обозначений взять вашу кодировку, то парадокс Берри не возникнет?
Совершенно верно, не возникнет. А при использовании привычных людям обозначений — возникает.ksbes
10.04.2019 17:07+1Тут ещё такой вопрос. Насколько являются валидными фразы:
— «один и два»
— «пять или двадцать пять»
Если они невалидны, т.к. указывают на непонятно какое число, то и ключевую фразу тогда можно назвать невалидной, т.к. она тоже не указывает на непонятно какое число.
Т.е. парадокса нет.
Если же эти фразы валидны, то валидна и фраза:
— «все натуральные числа»
И снова, парадокса нет.
Что скажете?tyomitch Автор
10.04.2019 17:11Совершенно верно, ваши фразы — как и ключевая — не указывают ни на какие числа.
Разница в том, что для ваших фраз это очевидно, а для ключевой — не столь очевидно.
ksbes
10.04.2019 16:12+1Есть бессмысленные комбинации букв. И для «человеческого» описания цифр (т.е. не кодирование, а простой язык) таких комбинаций будет большинство.
Но это не имеет особого значения в данном парадоксе: главное что это НЕ все возможные _натуральные_ числа (для ненатуральных парадокс не работает).
Следовательно среди оставшихся должно найтись наименьшее ( это свойство любого подмножества натуральных чисел).
Тут как раз можно и провести атаку на парадокс: составить рекурсивное описание, которое назовёт каждое натуральное число.juray
10.04.2019 16:34А почему бессмысленные комбинации букв не могут быть обозначениями чисел? Что-то я не вижу, чтобы требование осмысленности оговаривалось в тексте.
ksbes
10.04.2019 16:36+1Да какая разница? Для парадокса важно, что в рамках 80ти символов нельзя назвать каждое число.
А осмысленность требуется чтобы работала ключевая фраза: «наименьшее число, которое нельзя описать меньше чем ста символами»
tyomitch Автор
10.04.2019 16:46Во втором предложении статьи оговаривается, что словом «одиннадцать» принято обозначать число 11, а не 0xd0bed0b4d0b8d0bdd0bdd0b0d0b4d186d0b0d182d18c. По-моему, из этого ясно, что речь идёт о смысле, а не о тридцатичетыричной (или любой другой) кодировке.
juray
10.04.2019 17:06Совершенно неясно, поскольку пассаж о «из восьмидесяти русских букв и пробелов можно составить всего 3480 обозначений» склоняет именно к 34-ричной системе кодирования.
tyomitch Автор
10.04.2019 17:15Вы не один такой, force тоже подумал про 34-ричное кодирование. В действительности, 34-ричные комбинации используются только для подсчёта возможных обозначений, а не для определения обозначаемых чисел.
Если предложите, как сформулировать эту идею понятнее, то я охотно исправлю статью.juray
11.04.2019 00:04Если б я мог что-то предложить, я наверно, и посыл статьи правильно понял бы сразу, а не после битвы в комментах.
Keyten
12.04.2019 16:18Или не завершится? Ведь среди всех программ, которые будут испробованы, встретится while True: pass (и её функциональные аналоги) — и дальше проверки такой программы дело уже не пойдёт!
Вообще не обязательно.
Давайте сделаем так: разобьём каждую программу на некие атомарные операции и сделаем очередь программ. Затем будем каждую итерацию добавлять в список следующую программу и исполнять по одной атомарной итерации из каждой программы списка.
Таким образом, любая программа будет запущена через некоторое конечное время.
(что конечно же не сработает на практике, но ведь мы не об этом говорим?)ksbes
12.04.2019 16:53Не надо пытаться опровергнуть теорему об остановке.
Невозможно произвольную программу разбить только на атомарные операции. А с фундаментально неатомарными приходим к тому с чего началиKeyten
12.04.2019 16:59Хмм, а почему нельзя произвольную программу разбить на атомарные операции? Давайте возьмём машину Тьюринга, там атомарные операции вполне очевидны, и программа разбивается на них просто по определению. Нет?
Возможно, я сейчас спрашиваю о каких-то банальных вещах, которые рассказывают в институте на Computer Science, но я, к сожалению, учился на немного другом направлении.
tyomitch Автор
13.04.2019 14:25Таким образом, любая программа будет запущена через некоторое конечное время.
Вы правы, ваш подход это обеспечит.
Но в какой момент программа-генератор может выводить до сих пор не «вычеркнутое» число в качестве искомого? Может быть, одна из запущенных программ через несколько шагов его как раз выведет и тем самым «вычеркнет»?
exception13x
С каких пор пробелы и запятые стали буквами?
Если использовать «символов», то парадокс пропадает.
tyomitch Автор
Почему пропадает?
exception13x
Потому что в фразе «самое маленькое число, для обозначения которого недостаточно восьмидесяти символов» будет 83 символа.
Прошу прощения за придирки, меня просто зацепила фраза про 78 букв (которых 69 в исходной фразе)
kahi4
ну поменять 80 на 100 и делов то, "самое маленькое число, для обозначения которого недостаточно ста символов".
TheShock
Вот только я тогда тоже не вижу парадокса, ведь это обозначение уже будет занято значительно раньше другим числом (оно не будет семантическим, но будет соответствовать нашим правилам). Если мы игнорируем это — тоже нету парадокса, ведь у нас обычная коллизия.
exception13x
А это кстати хороший момент, как будет меняться число при изменении нижней границы количества букв для его описания?
То есть если поменять границы с 80 до 100 само число изменится?
tyomitch Автор
Учитывая, что такого числа не существует ни для 80, ни для 100 — ваш вопрос вызывает удивление.
kahi4
А мне вот что стало интересно. Опустим парадокс. Скажем, мы не можем записать все числа от 1 до n^m (n — размер алфавита, m — количество символов) через естественный алфавит из-за отсутствия однозначного кодирования числа через произвольную строку.
Допустим, мы сделаем такую систему кодирования, скажем, по аналогии с base64, т.е. можем закодировать любое число меньше n^m через последовательность символов из нашего словаря не длинее m штук. При каком размере строки на естественном языке в нее же влезет "алгоритм расшифровки" (который так же должен быть, очевидно, частью закодированного числа)?
fireSparrow
Запись алгоритма сама по себе — бессмысленный набор символов, она обретает смысл, только когда есть субъект, способный прочитать, понять и исполнить алгоритм.
А разные субъекты могут по разному понимать одну и ту же запись алгоритма. Чтобы они гарантированно понимали его одинаково, нужно в последовательность вложить ещё и подробный стандарт, который для языка программирования может занимать толстый том.
Но при этом и текст стандарта нужно прочитать и осмыслить одинаково, а это всё равно предполагает, что у субъектов есть некий общий осмысливающий аппарат, который, получается, тоже должен быть как-то занесён в сообщение.
tyomitch Автор
Да, всё так и есть. Но при этом живые люди как-то общаются при помощи коротких сообщений, не включающих в себя всю эпистемологию, — и друг друга понимают.
Если вы спросите прохожего, который час, и он вам ответит «одиннадцать», вы же даже не подумаете переспрашивать «в какой системе счисления»?
Вот философов и занимает вопрос о том, почему вам вполне понятно сообщение, которое, строго говоря, недоопределено.
juray
Любой набор символов имеет смысл, только когда есть субъект, способный его прочитать и понять.
Само понятие смысла знаков/символов связано с наличием такого субъекта.
fireSparrow
Об этом и речь. На самом деле, точнее даже говорить о системе «субъект + контекст».
Весь кажущийся парадокс строится вокруг того, что якобы некая фраза на естественном языке что-то означает сама по себе.
Что очевидно не так, и «парадокс» возникает исключительно из-за того, что попытка осмыслить субъектом фразу ломает тот контекст, в рамках которого эта фраза должна быть осмыслена.
kahi4
Парадокс своими словами:
Возьмем любой словарь размера n. Возьмем строку длиной m.
Существует n^m способов расположить символы из этого словаря в строки длиной n. Т.е. конечное число. Самих чисел — бесконечное число. Мы не можем описать любое число из бесконечного набора используя конечный словарь и конечную длину строк.
Значит — обязано существовать какое-то минимальное число, которое мы уже не можем описать в рамках словаря и заданной длины строки. Однако при длине строки 100, у нас может быть фраза "самое маленькое число, для обозначения которого недостаточно ста символов", которая это самое минимальное число и описывает. Но раз что-то его описывает, оно уже противоречит своему же определению, и минимальным неописываемым становится следующее. Но тогда это становится неописываемым обратно и у нас вечный цикл, что и вызывает парадокс.
Достаточно очевидно, что n^m является верхней границей этого парадоксального числа, потому что из-за того, что не все фразы обозначают число, а некоторые числа обозначаются повторно — какое-то число до n^m уже точно нельзя описать этими строками.
TheShock
Все комбинации n символов в строке длиной до m мы использовали для обозначения чисел от 1 до n^m. Следовательно фраза «самое маленькое число, для обозначения которого недостаточно ста символов» уже была занята значительно меньшим числом и не может быть использована для отображения числа n^m+1. Она занята. Парадокса нет.
tyomitch Автор
Не совсем так. Большая часть просмотренных комбинаций — например, «абырвалг», «быстрая коричневая лиса» и «натуральное число между двумя и тремя» — не обозначают никакие числа. Поэтому фраза «самое маленькое число, для обозначения которого недостаточно ста символов», хоть и обязательно входит в число просмотренных, не обязательно была занята меньшим числом.
TheShock
Тогда я не вижу парадокса тоже. Просто такого числа, подходящего под эту фразу, не существует
tyomitch Автор
Парадокс в том, что а) существуют числа, для обозначения которых недостаточно ста символов; б) среди этих чисел должно существовать самое маленькое.
TheShock
Почему такие числа должны существовать на изменяющихся правилах? Любое число можно записать ста символами, если изменить правила, по которым это число вычисляется. По сути, вы используете не только 100 символов, но и мета-информацию
ioannes
Точно так же как существует сельский брадобрей, который бреет всех тех и только тех, кто не бреется сам.
juray
Ненене. Любому из чисел в диапазоне до n^m можно однозначно сопоставить одну из строк длиной m из алфавита в n символов.
Большинство этих строк с точки зрения естественного языка будет бессмысленным набором букв, но часть таки будет валидными фразами. Говоря по другому — любая валидная фраза длины до n будет содержаться в этом списке, включая и «абырвалг», и прочие другие.
Причем, фразы длиной менее n в этом списке будут встречаться несколько раз, по-разному дополненные пробелами (в начале, в конце, в начале и конце). Если мы считаем это одной и той же фразой, а не разными комбинациями — то получаем, что такие короткие фразы обозначают аж несколько чисел.
tyomitch Автор
При предлагаемом вами кодировании фраза «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» заведомо не будет соответствовать самому маленькому числу, для обозначения которого недостаточно восьмидесяти букв.
Поэтому ваше кодирование, хотя и осуществимо, но никакого интереса не представляет.
TheShock
В смысле алгоритмов сжатия ваше «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» тоже никакого интереса не представляет
tyomitch Автор
Это правда; но зато оно представляет занятный парадокс, тогда как 34-ричное кодирование не даёт ни сжатия, ни парадокса.