Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 38
Спасибо большое, я смеялся, как ребенок, от восторга! )
Ага. Если я правильно понял, по заданной последовательности чисел (в заданной системе счисления) можно построить дизъюнктивное число. А есть ли какой-то «хороший» способ это число обозначить так, чтобы этот способ не сводился к формуле
Зачем: если ответ на вопрос из предыдущего абзаца «да», то открывается прекрасная возможность троллинга патентовладельцев. Берем официальную аудио-запись в цифровой форме, определяем ее дизъюнктивное число, предъявляем претензию на отмену патента на основании «нет новизны».
\sum_{0}^{\infty}\frac{n}{10^{n^2}}Зачем: если ответ на вопрос из предыдущего абзаца «да», то открывается прекрасная возможность троллинга патентовладельцев. Берем официальную аудио-запись в цифровой форме, определяем ее дизъюнктивное число, предъявляем претензию на отмену патента на основании «нет новизны».
Попробуйте www.codecogs.com/latex/eqneditor.php, а то читать некомфортно.
Не до конца понял, зачем строить отдельное дизъюнктивное число для каждой записи. Достаточно взять любое дизъюнктивное число и показать, что данная запись где-то в нём находится)
А что вычислительно проще? Когда я читал про pifs, у меня сложилось впечатление, что «показать, что данная запись находится в данном числе» вычислительно трудоемко. А построить новое число для заданной последовательности вроде бы попроще будет. Но возникает проблема с однозначной красивой идентификацией этого нового числа (например по дополнительным свойствам, неочевидным образом связанным с исходной последовательностью).
Можно показать неконструктивно. Собственно, из строгого доказательства того, что число дизъюнктивно, уже следует, что нужный фрагмент в нём содержится. Чтобы обвинить человека, например, в краже, достаточно доказать, что он украл деньги, и нет необходимости указывать, где эти деньги сейчас находятся.
как математик по образованию, я вам верю (хоть доказательства и не видел пока), что теоремы существования должно для доказательства хватить. Но согласитесь, это не тот способ, которым можно уверенно убеждать юристов и привлечь много сторонников-программистов (в некотором роде исходящих из принципа «считает — значит существует»). В общем, было бы здорово иметь технологию явного вычисления либо новых дизъюнктивных чисел (с условием из камента выше), либо бОлее вычислительно эффективного восстановления позиции последовательности в одном из известных дизъюнктивных. Зачем? Затем, что при желании тогда можно развернуть массовую кампанию по сведению официальных музыкальных/видео-треков к известным числам, с известными последствиями.
Стандартный аргумент про невозможность сжатия произвольной последовательности. Если бы можно было задать любую последовательность, не используя объём данных, сравнимый с самой последовательностью, то получилось бы идеальное сжатие, которое невозможно. А если для задания нужен сравнимый объём данных — получается просто ещё один формат тех же данных.
Пардон, а при чём здесь сжатие?
Это верно, если ждать ответов от информатики. А мой вопрос скорее к математике. Я спрашивал, возможно ли получить опосредованное описание заданного дизъюнктивного числа. Например, если вам показать 3.1415926… то вы скажете — конечно это пи! А чем пи отличается от других дизъюнктивных чисел? Во-первых его все знают :) (Что значит «знают»? Только то, что все это странное дизъюнктивное число запомнили). Но знают-то его за его свойства! Как то: длина окружности, интеграл от экспоненты -x^2 и т.п. И мой вопрос о том, можно ли аналогичные свойства выводить автоматически для новых дизъюнктивных чисел. Если да, то получив новое дизъюнктивное число, можно сказать: это не просто случайная длинная последовательность циферок, а такое специальное число, однозначно определяемое вот этим списком свойств (которые полностью определяют вашу песенку бритни спирс, а ну снимайте копирайт).
Тот же самый аргумент. Если список свойств однозначно определяет произвольный 700 Мb файл, то сам список свойств должен занимать не менее 700 Мb.
Вас подводит применение теоремы Шеннона, она тут ни при чем. Еще раз: я могу вам выписать бесконечное число знаков числа пи, но предъявить лишь одно свойство, однозначно определяющее это число. Свойство, дословно:
константа, иррациональное число, равное длине окружности поделенной на удвоенный радиус этой окружности.У меня вышло 104 символа полного описания свойства, однозначно определяющего константу пи. Но число знаков у контанты в ее десятичной записи — бесконечно.
Тут, видимо, нужно вспомнить еще про колмогоровскую сложность.
Развейте вашу мысль, плиз. А то я пока не понял, какую сторону вы поддерживаете и что именно с колмогоровской сложностью нужно делать.
Я это к тому, что
Вы предлагаете по произвольной последовательности находить колмогоровскую сложность. Но, если я ничего не путаю, колмогоровская сложность невычислима.
константа, иррациональное число, равное длине окружности поделенной на удвоенный радиус этой окружности.фактически колмогоровская сложность числа pi.
Вы предлагаете по произвольной последовательности находить колмогоровскую сложность. Но, если я ничего не путаю, колмогоровская сложность невычислима.
Заметьте, я не предлагаю, а спрашиваю: возможно ли. К тому же, у нас не произвольная последовательность, а десятичное представление дизъюнктивного числа. Это означает, что у такой последовательности могут появиться более сильные свойства, позволяющие обойти невычислимость колмогоровской сложности. Но я тут не эксперт, поэтому собственно, вопрос и задал.
Вы можете задать 104 символами (не пересчитывал и можно придраться к определению, но пусть будет 104) первые 1000 цифр числа пи, но принципиально не сможете задать 104 символами произвольные 1000 цифр. Более того, если ограничиться 104 символами, то доля 1000-циферных последовательностей, которые в принципе можно задать, пренебрежимо мала (точное значение зависит от множества разрешённых цифр и символов), и все такие последовательности исключительно специальны и не имеют собственного смысла в отрыве от определения. Так что либо вам придётся создавать большие семейства свойств (типа «i-я цифра равна j»), для задания которых нужны данные, сравнимые по размеру с исходной последовательностью, либо не рассчитывать на то, что последовательности, имеющие независимый смысл, уложатся в описание.
тут не произвольные последовательности, а десятичные представления дизъюнктивных чисел. Это могут быть последовательности со специальным набором свойств. Каких? В этом и был мой исходный вопрос топикстартеру.
Процитирую статью:
Нет никаких свойств, специфических для нормальных (и, тем более, дизъюнктивных) чисел и при этом отсеивающих значительные множества.
нормальных чисел большинство. Доказано, что множество «ненормальных» чисел имеет лебегову меру 0. Это означает, что если ткнуть пальцем в единичный отрезок, то с вероятностью 100% попадёшь в нормальное число.
Нет никаких свойств, специфических для нормальных (и, тем более, дизъюнктивных) чисел и при этом отсеивающих значительные множества.
Ваш аргумент выглядит разумно. No offence, но я бы хотел услышать аргументы топикстартера. Не потому что вам не доверяю, а лишь потому что он обещал некий специальный способ конструировать «число, нормальность которого очевидна». В рассуждениях «принципиально невозможно потому что ...» я не очень свободно ориентируюсь (если не специалист в теории чисел/матлогике, легко пропустить мелкие детали), проще плясать от конкретного предложения.
Конечно, все читают теги!
Давно хочу спросить — а что означает это «помогитеязастряловмеханизмевселенной»? Какая-то мнемоника? Если да то как она работает?
Нет, это шутка о том, как будто некий разум общается с нами, записывая послания в константы физических законов нашей вселенной.
На случай, если не все знают этот шаблон, ссылка на TVTropes (осторожно: это ссылка на tvtropes! прочитайте статью и немедленно закрывайте вкладку, не щёлкая по ссылкам, если вам дорог ваш день!). Самый интересный вариант я встречал в 4 сезоне «Robot Chicken».
У меня есть ощущение, что хранение файла в виде смещения и длины в каком-то дизъюнктивном числе числе едва ли будет эффективнее, чем хранение номера файла (все возможные файлы ведь можно занумеровать). Если вообще не эквивалентно.
Скорее всего, хранение номера файла будет эффективнее. Особенно если файлы занумеровать умно (более распространённым файлам — более короткие номера). Это, по идее, вообще идеальный, неулучшаемый вариант.
Кстати, чем-то похожая идея же применяется в арифметическом кодировании.
Биекция. Ни первое ни второе ни разу не эффективнее, ибо и в том и другом случае множества равномощны. В среднем количество цифр в «смещении» или в «порядковом номере» будет равно количеству цифр исходного сообщения.
Ещё длина. Вообще, утверждение не слишком очевидное.
Удивительно. Первое N-значное число впервые встретится по смещению 0, последнее — по смещению примерно 2.3*N*10N, но в среднем по всем числам смещение их первого вхождения в нормальное число будет ровно 10N, несмотря на повторы. Всего вдвое больше среднего значения самих чисел. Слегка неожиданно. Я думал, что будет ближе к N*10N.
А мне вспомнилось, как Фейнман троллил первый отдел, отправив в письме 1/243 в десятичной записи
После прочтения статьи чувствую себя полным болваном.
«Вавилонская библиотека» — это из Борхеса и Макса Фрая?
«Вавилонская библиотека» — это из Борхеса и Макса Фрая?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Нормальные числа: ликбез