Комментарии 104
Если использовать «символов», то парадокс пропадает.
Прошу прощения за придирки, меня просто зацепила фраза про 78 букв (которых 69 в исходной фразе)
ну поменять 80 на 100 и делов то, "самое маленькое число, для обозначения которого недостаточно ста символов".
То есть если поменять границы с 80 до 100 само число изменится?
А мне вот что стало интересно. Опустим парадокс. Скажем, мы не можем записать все числа от 1 до n^m (n — размер алфавита, m — количество символов) через естественный алфавит из-за отсутствия однозначного кодирования числа через произвольную строку.
Допустим, мы сделаем такую систему кодирования, скажем, по аналогии с base64, т.е. можем закодировать любое число меньше n^m через последовательность символов из нашего словаря не длинее m штук. При каком размере строки на естественном языке в нее же влезет "алгоритм расшифровки" (который так же должен быть, очевидно, частью закодированного числа)?
А разные субъекты могут по разному понимать одну и ту же запись алгоритма. Чтобы они гарантированно понимали его одинаково, нужно в последовательность вложить ещё и подробный стандарт, который для языка программирования может занимать толстый том.
Но при этом и текст стандарта нужно прочитать и осмыслить одинаково, а это всё равно предполагает, что у субъектов есть некий общий осмысливающий аппарат, который, получается, тоже должен быть как-то занесён в сообщение.
Если вы спросите прохожего, который час, и он вам ответит «одиннадцать», вы же даже не подумаете переспрашивать «в какой системе счисления»?
Вот философов и занимает вопрос о том, почему вам вполне понятно сообщение, которое, строго говоря, недоопределено.
Само понятие смысла знаков/символов связано с наличием такого субъекта.
Весь кажущийся парадокс строится вокруг того, что якобы некая фраза на естественном языке что-то означает сама по себе.
Что очевидно не так, и «парадокс» возникает исключительно из-за того, что попытка осмыслить субъектом фразу ломает тот контекст, в рамках которого эта фраза должна быть осмыслена.
Парадокс своими словами:
Возьмем любой словарь размера n. Возьмем строку длиной m.
Существует n^m способов расположить символы из этого словаря в строки длиной n. Т.е. конечное число. Самих чисел — бесконечное число. Мы не можем описать любое число из бесконечного набора используя конечный словарь и конечную длину строк.
Значит — обязано существовать какое-то минимальное число, которое мы уже не можем описать в рамках словаря и заданной длины строки. Однако при длине строки 100, у нас может быть фраза "самое маленькое число, для обозначения которого недостаточно ста символов", которая это самое минимальное число и описывает. Но раз что-то его описывает, оно уже противоречит своему же определению, и минимальным неописываемым становится следующее. Но тогда это становится неописываемым обратно и у нас вечный цикл, что и вызывает парадокс.
Достаточно очевидно, что n^m является верхней границей этого парадоксального числа, потому что из-за того, что не все фразы обозначают число, а некоторые числа обозначаются повторно — какое-то число до n^m уже точно нельзя описать этими строками.
Большинство этих строк с точки зрения естественного языка будет бессмысленным набором букв, но часть таки будет валидными фразами. Говоря по другому — любая валидная фраза длины до n будет содержаться в этом списке, включая и «абырвалг», и прочие другие.
Причем, фразы длиной менее n в этом списке будут встречаться несколько раз, по-разному дополненные пробелами (в начале, в конце, в начале и конце). Если мы считаем это одной и той же фразой, а не разными комбинациями — то получаем, что такие короткие фразы обозначают аж несколько чисел.
Поэтому ваше кодирование, хотя и осуществимо, но никакого интереса не представляет.
Нетрудно заметить, что приведенный алгоритм из второй части статьи рано или поздно найдет сам себя, таким образом он эквивалентен тому что используется в доказательстве «проблемы останова».
Есть разница. Фраза "Самое большое простое число" обозначает некий критерий, которому число может или соответствовать, или нет: оно должно быть простым и быть больше всех остальных простых чисел. Ему ничего не соответсвует, так же как критериям "простое число, кратное пяти", "четвёртый муж королевы Виктории" или "сочинения Сократа о Платоне". Но это свойство реальности, а не самого определения. Если бы простые числа были устроены иначе, а Сократ любил бы писать диалоги о своих учениках — эти фразы означали бы конкретные числа и тексты.
А фраза «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» (высказывание, не последовательность символов; очевидно, что Рассел писал не на русском, но нам не приходится переходить на английский для обсуждения этого парадокса) внутренне противоречива. Она, грубо говоря, не может корректно парситься.
Близкая по смыслу статья о Busy Beaver https://m.habr.com/ru/post/317996/
И ещё одна, об огромных числах https://habr.com/post/265067/
какое самое маленькое число, для обозначения которого недостаточно восьмидесяти букв?
Такое число обязано существовать: из восьмидесяти русских букв и пробелов можно составить всего 34^80 обозначений, значит, с использованием восьмидесяти букв можно обозначить не более 34^80 чисел.
Это совершенно не означает, что минимальное число будет порядка 34^80. Есть тенденция обозначать огромные числа кратко, "гугол" = 10^100 — всего 5 букв. Утверждение, что такое число обязано существовать, хотя оно и верное, кажется мне нереалистичным по причине того, что завязано на семантику слов в каком-то языке. После того, как мы назовём число, люди могут придумать более краткое обозначение для ещё большего числа, и даже задействовать старое слово для нового понятия.
какое самое маленькое число, для вывода которого недостаточно килобайтной программы?
Не обязательно перебирать 256^1024 программ.
Можно подойти как раз со стороны колмогороской сложности — взять чисто случайное число, записываемое объёмом 1кбайт+1бит, записать его в десятичном, шестнадцатеричном виде, или в аналоге base64 (это компактнее) и добавить код для раскодирования наподобие "print(...)".
Это совершенно не означает, что минимальное число будет порядка 34^80.
Минимальное число было бы намного меньше 3480 — уже хотя бы потому, что не все последовательности букв являются описаниями чисел.
Но поскольку его не существует, то нет смысла обсуждать, какого порядка оно было бы.
Вторую часть вашего комментария я не понял. Взять чисто случайное число, и что дальше? Оно чисто случайно окажется тем самым самым маленьким числом, которое мы ищем?
for i=1 to Мульярд
и в цикле фигачить print(...)
ах,
нам нужна длинная прога аж в килобайт?
ну давайте натулим 10 вложенных for…
В качестве примера, часто использующееся DEADBEEF, которые означает конкретное число 3735928559, а не кусок говядины, случайно обнаружившийся в компьютере.
Вот есть обозначение «одинадцать» — каким ещё числам оно соответствует, кроме числа 11?
«Слово» одиннадцать тоже соответствует какому-то числу, как и слово жопа, как и слово то число которое нельзя
Такое число обязано существовать: из восьмидесяти русских букв и пробелов можно составить всего 3480 обозначений, значит, с использованием восьмидесяти букв можно обозначить не более 3480 чисел. Значит, некое число, не большее чем 3480, обозначить таким образом невозможно.
А если смысловое, то весь пассаж не имеет смысла, т.к. ваш же пример противоречит последней фразе.
Я так полагаю, что здесь не совсем корректный перевод/выражение.
Имеется ввиду, всего чисел описываемых 80ю буквами не более 34^80. Но приняв это мы вроде как получаем + 1 такое число.
Но это странно, т.к. это +1 "появится" из ранее бессмысленных комбинаций букв. Я тоже как-то не понимаю этот парадокс — потому и упомянул число Грея
34-ричные комбинации использовались только для подсчёта возможных обозначений, а не для определения обозначаемых чисел.
Оно и числу один*н*адцать не соответствует.
</grammar_mode>
Способов сопоставлять символьные последовательности числам мы можем придумать бесконечно много; парадокс, однако, возникает только при выборе одного из них и только если этот способ является собственным метаязыком, т.е. может содержать (возможно, непрямым образом) аналог фразы "данное предложение" или eval
. Таковыми являются все тюринг-полные языки программирования и вроде бы все натуральные. Это очередной парадокс вида "Существует такая хреновина, что она не соответствует своему описанию в данном предложении". Если она действительно существует, то ей придётся соответствовать описанию (а иначе это какая-то другая хреновина). Но если она таки соответсвует описанию — то это вовсе не та хреновина, а всё-таки какая-то другая. В данном случае более строгая формулировка будет "Существует такое число, кратчайшее возможное описание которого на русском языке длиннее данного предложения". Парадокс по сути эквивалентен парадоксу лжеца, когда утверждение (в данном случае косвенно) утверждает свою ложность.
А ещё хочу вот предложить универсальный скрипт на питоне, который может выводит любые числа (и не только числа, вообще всё что угодно). Занимает всего 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 байт) и при этом делает ровно тоже самое что и оригинал. Неувязочка.
Столько написал, а что сказать-то хотел? Вся эта «гимнастика для ума» безусловно штука полезная и нужная. Вот только перекладывать её на реальный питон надо очень аккуратно дабы не сделать ошибок в интерпретации или не создать случайно вечную брутфорсилку.
А теперь жмём кнопку «Pack» и получаем программу которая почти в два раза короче (821 байт) и при этом делает ровно тоже самое что и оригинал. Неувязочка.Ну, значит это не то число, которое нельзя вместить в 1024 байта программы, никакой неувязочки.
Первый обман это когда мы говорим «смотрите, эта программа длинной 821 байт выводит строку длиной 1024 байта». На самом деле у нас есть программа которая генерирует вторую программу. А вот уже та вторая программа (длинной 1600 байт) и выводит нужную нам строку.
Второй обман заключается в том что мы выдаём исходный текст программы за байткод который непосредственно и будет выполнять наша машина. В случае джаваскрипта байткод может занимать сильно больше места чем исходный текст из которого он был создан (вот тот кусок скрипта что я использовал для примера распухает почти в два раза после перевода в байткод для V8). Не знаю что там в питоне, но не буду удивлён если ситуация аналогичная.
«Одиннадцать» может означать любое число начина с 3 и до бесконечности, потому что «по факту» это «база + 1».
Для математика — да. Для нормального человека, и в том числе для философа Рассела — оно означает 11 в десятичной системе.
Точно так же, «год смерти Тьюринга» для нормального человека означает 1954, хотя я подозреваю, что хотя бы один носитель фамилии Тьюринг умирает каждый год.
Исток парадокса Берри — не математический, а именно философский: Рассел и его корреспонденты пытались понять связь между объектами и их общепринятыми, общепонятными обозначениями.
а вот это не решение?
Аналогично с программой, она не самостоятельна, а включает в себя все множество программ, тоже является метапрограммой.
Так в чем же разница? Элементарно в недоопределенности условий первой формулировки и полной определенности (условно, боюсь найдется и в этом случае возможность трактовать по-разному) второй. В первом случае необходимо дополнительно описать все обозначения, которыми владеет субъект. А еще для разных субъектов это будут разные наборы обозначений. И для разных моментов времени для одного и того же субъекта набор обозначений будет отличаться. Но если со всем этим справиться, то будем иметь четкий алгоритм выбора самого маленького числа, для обозначения которого недостаточно восьмидесяти букв для конкретного субъекта в конкретный момент времени. И он будет столь же точным, как и выбор наименьшего двоичного числа для второго примера.
А автору все-же формально следует заменить 34^80 на 35^80 и фразу «из восьмидесяти русских букв и пробелов» на «из восьмидесяти русских букв, пробелов и запятых», ведь вы посчитали запятую в 78 символов длины строки. Или как-то иначе устранить несоответствие.
Разве есть проблема с фразой «Самое маленькое число, для записи которого недостаточно восьмидесяти двоичных цифр»?
Нет, потому что эта фраза не записана двоичными цифрами. Нет самореференции — нет и парадокса.
В исходной фразе просто нет самореференции, нет описания себя через себя, поскольку обозначению в виде текстовой строки (имени переменной) задается значение в терминах каких-то вычислений, не использующих саму эту переменную. Попробую изобразить в чертикаком коде, но должно быть понятно:
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]);
};
Это просто нормальное математическое утверждение (при условии полного определения задачи, как писал об этом выше). Наверняка вы могли бы написать код и поизящнее чем это сделал я. Но особо и не старался, честно говоря. Главная цель — показать, что в определении значения переменной ни сама переменная ни ссылка на нее не используется и значит Самореференции быть не может. Просто не следует отождествлять строку символов (обозначение) с ее смысловой нагрузкой в понимании субъекта.
Просто не следует отождествлять строку символов (обозначение) с ее смысловой нагрузкой в понимании субъекта.
Это как раз и есть разделение языка и метаязыка.
Но в таком представлении парадокс тоже буксует: в означенной длине вполне можно записать слово «бесконечность» и, следовательно, такого числа (минимального из всех, что можно описать 80-ю символами) просто может не существовать (это уже надо строго доказывать). Т.е. эта фраза просто не описывает числа.
И да, «бесконечность» это слишком много и не совсем число, давайте возьмем число «Самое большое число» и получим такую же динамически самоувеличивающуюся переменную.
Т.е. тут можно спорить с таким подходом и находить парадоксы, но мне больше нравится воспринимать так (возможно детская травма от кодогенерации тройного порядка SQL DDL->xml->Java->PHP, наш тимлид был затейник).
— Двоюродный брат фокуса (который показывает фокусник), там он прячет кролика в ящике, а тут тоже что-то похожее делают.
По условию каждому набору букв соответствует число некоторое, пропуски чисел возможны (какие-то числа меньше 34^80 не будут использованы, а будут использованы бОльшие числа). Есть массив чисел и есть массив строк, каждая строка указывает на число. Сто — это просто 100, гугол — это просто гугол. А одна строка пытается через логику указать на число за пределом этого массива.
Задачу (проблему) сжатия данных нельзя же рассматривать в отрыве такого понятия как стохастический поток сообщений (букв). Причём тут каждое слово важно — и стохастичность и наличие потока — т.е. достаточно большого количества.
Без этого сжать можно до одного бита (есть/нет вот эта длиннющая простыня захардкоженная в алгоритме сжатия/расшифровки — пресловутый «утюг в окне»)
В конце концов, практически используемые алгоритмы сжатия работают именно с конечными и неслучайными файлами, а не с бесконечным стохастическим потоком.
А алгоритм сжатия и расшифровки конечного и неслучайного текста я вам привёл. Сжимается такой текст ровно в 1 бит.
(Я не понимаю, вы Шеннона решили опровергнуть?)
Возьмём практический алгоритм сжатия JPEG — он работает со стохастическим потоком, или с двумерной матрицей наперёд известного размера?
Алгоритм JPEG работает со стохастическим потоком матриц заранее неизвестных размеров. По крайней мере у меня одной и той же программой в JPEG сохраняются как картинки 1x1, так и 1023х767 и никаких ограничений он на меня не накладывал.
Очень сомнительно практическое будущее алгоритма способного работать с матрицами только наперёд известного размера.
По-видимому, мы с вами по-разному понимаем, что такое «поток». Обычно «поток» — это то, в начале чего неизвестно, когда будет конец. Изображения от потока принципиально отличаются тем, что размер изображения известен ещё до чтения первого элемента матрицы.
По файлам — сами файлы образуют «поток файлов». Никто не пишет «практический алгоритм» для кодирования одного, десяти или другого конечного, заранее известного количества файлов. Файлы — именно что неизвестно когда они в этих проклятых интернетах закончатся. Но мы должны сжать и распаковать их все (хотя и понятно, что их будет конечное количество — интернеты с JPEG когда-нибудь закончатся).
из восьмидесяти русских букв и пробелов можно составить всего 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 бутылок...» и так далее. Это тоже число, и еще более огромное.
Только при дополнительном условии — числа обозначаются подряд, без пропусков.
Конечно же с пропусками: большая часть возможных обозначений не соответствует никаким числам.
В чём проблема?
Если вы вместо «некое число, не большее чем 3480, обозначить таким образом невозможно» прочитали «никакое число, большее чем 3480, обозначить таким образом невозможно» — то вы ошиблись :-)
Но если прочитать правильно — то смысла в этой фразе я вообще не вижу. Почему невозможно?
большая часть возможных обозначений не соответствует никаким числама вот это оговорено не было. А кстати, почему не соответствует? Просто волевым решением?
В случае сплошного сопоставления — таки не понимаю, с чего невозможно-то. Если это возможно для алфавита из цифр, то почему нет для расширенного? По сути, «обозначение, составленное из букв» само по себе является числом, записанным в системе счисления с основанием, равным количеству букв в алфавите (то есть буква — это цифра).
Речь в статье не об изобретении новой кодировки «base34-RU», а об обозначениях чисел, используемых людьми и понятных людям, — таких, как «одиннадцать», «пять девяток», и «год смерти Тьюринга».
Каким числам вы бы сопоставили строки «абырвалг»
Ну, например, 0xE0E1FBF0E2E0EBE3
а об обозначениях чисел, используемых людьми и понятных людям
А обозначение типа 0x5A081F — не понятно людям?
Совершенно верно, не возникнет. А при использовании привычных людям обозначений — возникает.
— «один и два»
— «пять или двадцать пять»
Если они невалидны, т.к. указывают на непонятно какое число, то и ключевую фразу тогда можно назвать невалидной, т.к. она тоже не указывает на непонятно какое число.
Т.е. парадокса нет.
Если же эти фразы валидны, то валидна и фраза:
— «все натуральные числа»
И снова, парадокса нет.
Что скажете?
Но это не имеет особого значения в данном парадоксе: главное что это НЕ все возможные _натуральные_ числа (для ненатуральных парадокс не работает).
Следовательно среди оставшихся должно найтись наименьшее ( это свойство любого подмножества натуральных чисел).
Тут как раз можно и провести атаку на парадокс: составить рекурсивное описание, которое назовёт каждое натуральное число.
Используется только слово «обозначение», а обозначение это всего лишь некое соответствие, сопоставление (заданное аналитически, алгоритмически или таблично).
(т.е. не кодирование, а простой язык)Из статьи это как-то не очевидно, особенно учитывая ее заголовок. Если мы рассуждаем о сжатии данных, это напрямую подразумевает именно что кодирование.
Примеры, приводимые в статье, я воспринял именно как экзотические частные случаи кодирования, отнюдь не исключащие кодирования простого (про которое я и распинываюсь в своих комментах).
А осмысленность требуется чтобы работала ключевая фраза: «наименьшее число, которое нельзя описать меньше чем ста символами»
Или не завершится? Ведь среди всех программ, которые будут испробованы, встретится while True: pass (и её функциональные аналоги) — и дальше проверки такой программы дело уже не пойдёт!
Вообще не обязательно.
Давайте сделаем так: разобьём каждую программу на некие атомарные операции и сделаем очередь программ. Затем будем каждую итерацию добавлять в список следующую программу и исполнять по одной атомарной итерации из каждой программы списка.
Таким образом, любая программа будет запущена через некоторое конечное время.
(что конечно же не сработает на практике, но ведь мы не об этом говорим?)
Невозможно произвольную программу разбить только на атомарные операции. А с фундаментально неатомарными приходим к тому с чего начали
Возможно, я сейчас спрашиваю о каких-то банальных вещах, которые рассказывают в институте на Computer Science, но я, к сожалению, учился на немного другом направлении.
Таким образом, любая программа будет запущена через некоторое конечное время.
Вы правы, ваш подход это обеспечит.
Но в какой момент программа-генератор может выводить до сих пор не «вычеркнутое» число в качестве искомого? Может быть, одна из запущенных программ через несколько шагов его как раз выведет и тем самым «вычеркнет»?
Попробуйте доказать, что строка "омышнхи" не обозначает искомое число.
Это "наводящий вопрос" на ответ. Вначале нужно определить значения для всех обозначений - только тогда будет иметь смысл поставленный в статье вопрос.
Парадоксы о сжатии данных