Comments 104
С каких пор пробелы и запятые стали буквами?
Если использовать «символов», то парадокс пропадает.
Если использовать «символов», то парадокс пропадает.
Почему пропадает?
Потому что в фразе «самое маленькое число, для обозначения которого недостаточно восьмидесяти символов» будет 83 символа.
Прошу прощения за придирки, меня просто зацепила фраза про 78 букв (которых 69 в исходной фразе)
Прошу прощения за придирки, меня просто зацепила фраза про 78 букв (которых 69 в исходной фразе)
ну поменять 80 на 100 и делов то, "самое маленькое число, для обозначения которого недостаточно ста символов".
Вот только я тогда тоже не вижу парадокса, ведь это обозначение уже будет занято значительно раньше другим числом (оно не будет семантическим, но будет соответствовать нашим правилам). Если мы игнорируем это — тоже нету парадокса, ведь у нас обычная коллизия.
А это кстати хороший момент, как будет меняться число при изменении нижней границы количества букв для его описания?
То есть если поменять границы с 80 до 100 само число изменится?
То есть если поменять границы с 80 до 100 само число изменится?
Учитывая, что такого числа не существует ни для 80, ни для 100 — ваш вопрос вызывает удивление.
А мне вот что стало интересно. Опустим парадокс. Скажем, мы не можем записать все числа от 1 до n^m (n — размер алфавита, m — количество символов) через естественный алфавит из-за отсутствия однозначного кодирования числа через произвольную строку.
Допустим, мы сделаем такую систему кодирования, скажем, по аналогии с base64, т.е. можем закодировать любое число меньше n^m через последовательность символов из нашего словаря не длинее m штук. При каком размере строки на естественном языке в нее же влезет "алгоритм расшифровки" (который так же должен быть, очевидно, частью закодированного числа)?
Запись алгоритма сама по себе — бессмысленный набор символов, она обретает смысл, только когда есть субъект, способный прочитать, понять и исполнить алгоритм.
А разные субъекты могут по разному понимать одну и ту же запись алгоритма. Чтобы они гарантированно понимали его одинаково, нужно в последовательность вложить ещё и подробный стандарт, который для языка программирования может занимать толстый том.
Но при этом и текст стандарта нужно прочитать и осмыслить одинаково, а это всё равно предполагает, что у субъектов есть некий общий осмысливающий аппарат, который, получается, тоже должен быть как-то занесён в сообщение.
А разные субъекты могут по разному понимать одну и ту же запись алгоритма. Чтобы они гарантированно понимали его одинаково, нужно в последовательность вложить ещё и подробный стандарт, который для языка программирования может занимать толстый том.
Но при этом и текст стандарта нужно прочитать и осмыслить одинаково, а это всё равно предполагает, что у субъектов есть некий общий осмысливающий аппарат, который, получается, тоже должен быть как-то занесён в сообщение.
Да, всё так и есть. Но при этом живые люди как-то общаются при помощи коротких сообщений, не включающих в себя всю эпистемологию, — и друг друга понимают.
Если вы спросите прохожего, который час, и он вам ответит «одиннадцать», вы же даже не подумаете переспрашивать «в какой системе счисления»?
Вот философов и занимает вопрос о том, почему вам вполне понятно сообщение, которое, строго говоря, недоопределено.
Если вы спросите прохожего, который час, и он вам ответит «одиннадцать», вы же даже не подумаете переспрашивать «в какой системе счисления»?
Вот философов и занимает вопрос о том, почему вам вполне понятно сообщение, которое, строго говоря, недоопределено.
Любой набор символов имеет смысл, только когда есть субъект, способный его прочитать и понять.
Само понятие смысла знаков/символов связано с наличием такого субъекта.
Само понятие смысла знаков/символов связано с наличием такого субъекта.
Об этом и речь. На самом деле, точнее даже говорить о системе «субъект + контекст».
Весь кажущийся парадокс строится вокруг того, что якобы некая фраза на естественном языке что-то означает сама по себе.
Что очевидно не так, и «парадокс» возникает исключительно из-за того, что попытка осмыслить субъектом фразу ломает тот контекст, в рамках которого эта фраза должна быть осмыслена.
Весь кажущийся парадокс строится вокруг того, что якобы некая фраза на естественном языке что-то означает сама по себе.
Что очевидно не так, и «парадокс» возникает исключительно из-за того, что попытка осмыслить субъектом фразу ломает тот контекст, в рамках которого эта фраза должна быть осмыслена.
Парадокс своими словами:
Возьмем любой словарь размера n. Возьмем строку длиной m.
Существует n^m способов расположить символы из этого словаря в строки длиной n. Т.е. конечное число. Самих чисел — бесконечное число. Мы не можем описать любое число из бесконечного набора используя конечный словарь и конечную длину строк.
Значит — обязано существовать какое-то минимальное число, которое мы уже не можем описать в рамках словаря и заданной длины строки. Однако при длине строки 100, у нас может быть фраза "самое маленькое число, для обозначения которого недостаточно ста символов", которая это самое минимальное число и описывает. Но раз что-то его описывает, оно уже противоречит своему же определению, и минимальным неописываемым становится следующее. Но тогда это становится неописываемым обратно и у нас вечный цикл, что и вызывает парадокс.
Достаточно очевидно, что n^m является верхней границей этого парадоксального числа, потому что из-за того, что не все фразы обозначают число, а некоторые числа обозначаются повторно — какое-то число до n^m уже точно нельзя описать этими строками.
Все комбинации n символов в строке длиной до m мы использовали для обозначения чисел от 1 до n^m. Следовательно фраза «самое маленькое число, для обозначения которого недостаточно ста символов» уже была занята значительно меньшим числом и не может быть использована для отображения числа n^m+1. Она занята. Парадокса нет.
Не совсем так. Большая часть просмотренных комбинаций — например, «абырвалг», «быстрая коричневая лиса» и «натуральное число между двумя и тремя» — не обозначают никакие числа. Поэтому фраза «самое маленькое число, для обозначения которого недостаточно ста символов», хоть и обязательно входит в число просмотренных, не обязательно была занята меньшим числом.
Тогда я не вижу парадокса тоже. Просто такого числа, подходящего под эту фразу, не существует
Парадокс в том, что а) существуют числа, для обозначения которых недостаточно ста символов; б) среди этих чисел должно существовать самое маленькое.
Почему такие числа должны существовать на изменяющихся правилах? Любое число можно записать ста символами, если изменить правила, по которым это число вычисляется. По сути, вы используете не только 100 символов, но и мета-информацию
Точно так же как существует сельский брадобрей, который бреет всех тех и только тех, кто не бреется сам.
Ненене. Любому из чисел в диапазоне до n^m можно однозначно сопоставить одну из строк длиной m из алфавита в n символов.
Большинство этих строк с точки зрения естественного языка будет бессмысленным набором букв, но часть таки будет валидными фразами. Говоря по другому — любая валидная фраза длины до n будет содержаться в этом списке, включая и «абырвалг», и прочие другие.
Причем, фразы длиной менее n в этом списке будут встречаться несколько раз, по-разному дополненные пробелами (в начале, в конце, в начале и конце). Если мы считаем это одной и той же фразой, а не разными комбинациями — то получаем, что такие короткие фразы обозначают аж несколько чисел.
Большинство этих строк с точки зрения естественного языка будет бессмысленным набором букв, но часть таки будет валидными фразами. Говоря по другому — любая валидная фраза длины до n будет содержаться в этом списке, включая и «абырвалг», и прочие другие.
Причем, фразы длиной менее n в этом списке будут встречаться несколько раз, по-разному дополненные пробелами (в начале, в конце, в начале и конце). Если мы считаем это одной и той же фразой, а не разными комбинациями — то получаем, что такие короткие фразы обозначают аж несколько чисел.
При предлагаемом вами кодировании фраза «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» заведомо не будет соответствовать самому маленькому числу, для обозначения которого недостаточно восьмидесяти букв.
Поэтому ваше кодирование, хотя и осуществимо, но никакого интереса не представляет.
Поэтому ваше кодирование, хотя и осуществимо, но никакого интереса не представляет.
UFO just landed and posted this here
Очевидно, не каждая последовательность букв обозначает число. Например — «Самое Большое Простое Число». Так что в парадоксе нет ничего парадоксального.
Нетрудно заметить, что приведенный алгоритм из второй части статьи рано или поздно найдет сам себя, таким образом он эквивалентен тому что используется в доказательстве «проблемы останова».
Нетрудно заметить, что приведенный алгоритм из второй части статьи рано или поздно найдет сам себя, таким образом он эквивалентен тому что используется в доказательстве «проблемы останова».
Какое отношение к этому парадоксу имеет то, что не каждая последовательность букв обозначает число?
Самое прямое. Фраза «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» тоже не обозначает число, согласно приведенных в статье рассуждений.
Есть разница. Фраза "Самое большое простое число" обозначает некий критерий, которому число может или соответствовать, или нет: оно должно быть простым и быть больше всех остальных простых чисел. Ему ничего не соответсвует, так же как критериям "простое число, кратное пяти", "четвёртый муж королевы Виктории" или "сочинения Сократа о Платоне". Но это свойство реальности, а не самого определения. Если бы простые числа были устроены иначе, а Сократ любил бы писать диалоги о своих учениках — эти фразы означали бы конкретные числа и тексты.
А фраза «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» (высказывание, не последовательность символов; очевидно, что Рассел писал не на русском, но нам не приходится переходить на английский для обсуждения этого парадокса) внутренне противоречива. Она, грубо говоря, не может корректно парситься.
Близкая по смыслу статья о 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…
for i=1 to Мульярд
и в цикле фигачить print(...)
ах,
нам нужна длинная прога аж в килобайт?
ну давайте натулим 10 вложенных for…
Не понял порадокса с 80 буквами. Если мы определяем запись числа буквами, то фраза самое маленькое число, для обозначения которого недостаточно восьмидесяти букв будет соответвовать какому-то конкретному числу из этой записи, а не смыслом, который в нём читается. Иначе получается, что одними и теми же символами мы можем одновременно записать разные числа — что не способствует конструктивным построениям.
В качестве примера, часто использующееся DEADBEEF, которые означает конкретное число 3735928559, а не кусок говядины, случайно обнаружившийся в компьютере.
В качестве примера, часто использующееся DEADBEEF, которые означает конкретное число 3735928559, а не кусок говядины, случайно обнаружившийся в компьютере.
Не понял, почему «одними и теми же символами мы можем одновременно записать разные числа».
Вот есть обозначение «одинадцать» — каким ещё числам оно соответствует, кроме числа 11?
Вот есть обозначение «одинадцать» — каким ещё числам оно соответствует, кроме числа 11?
Смотрите. У нас есть тридцатичетырёхричная система счистления (буквы русского языка + пробел). Условно говоря а — 0, я — 32. Соответственно «слово»: гад = 4 * 34 * 34 + 0 * 34 + 5
«Слово» одиннадцать тоже соответствует какому-то числу, как и слово жопа, как и слово то число которое нельзяназывать записать. И даже если в рускком языке слово кажется осмысленным, оно имеет совершенно конкретное значение, соответствующее единственному числу согласно правилам записи таких чисел.
«Слово» одиннадцать тоже соответствует какому-то числу, как и слово жопа, как и слово то число которое нельзя
Здесь имеется именно смысловое описание. Т.е. «число Грея» (кстати, меньше 80ти символов!) — это именно вон то самое число Грея, а не цифра в base33-RU
Вроде бы не похоже на смысловое
А если смысловое, то весь пассаж не имеет смысла, т.к. ваш же пример противоречит последней фразе.
Такое число обязано существовать: из восьмидесяти русских букв и пробелов можно составить всего 3480 обозначений, значит, с использованием восьмидесяти букв можно обозначить не более 3480 чисел. Значит, некое число, не большее чем 3480, обозначить таким образом невозможно.
А если смысловое, то весь пассаж не имеет смысла, т.к. ваш же пример противоречит последней фразе.
Я так полагаю, что здесь не совсем корректный перевод/выражение.
Имеется ввиду, всего чисел описываемых 80ю буквами не более 34^80. Но приняв это мы вроде как получаем + 1 такое число.
Но это странно, т.к. это +1 "появится" из ранее бессмысленных комбинаций букв. Я тоже как-то не понимаю этот парадокс — потому и упомянул число Грея
Именно смысловое, а не тридцатичетыричное.
34-ричные комбинации использовались только для подсчёта возможных обозначений, а не для определения обозначаемых чисел.
34-ричные комбинации использовались только для подсчёта возможных обозначений, а не для определения обозначаемых чисел.
<grammar_mode>
Оно и числу один*н*адцать не соответствует.
</grammar_mode>
Оно и числу один*н*адцать не соответствует.
</grammar_mode>
Способов сопоставлять символьные последовательности числам мы можем придумать бесконечно много; парадокс, однако, возникает только при выборе одного из них и только если этот способ является собственным метаязыком, т.е. может содержать (возможно, непрямым образом) аналог фразы "данное предложение" или eval. Таковыми являются все тюринг-полные языки программирования и вроде бы все натуральные. Это очередной парадокс вида "Существует такая хреновина, что она не соответствует своему описанию в данном предложении". Если она действительно существует, то ей придётся соответствовать описанию (а иначе это какая-то другая хреновина). Но если она таки соответсвует описанию — то это вовсе не та хреновина, а всё-таки какая-то другая. В данном случае более строгая формулировка будет "Существует такое число, кратчайшее возможное описание которого на русском языке длиннее данного предложения". Парадокс по сути эквивалентен парадоксу лжеца, когда утверждение (в данном случае косвенно) утверждает свою ложность.
«Одиннадцать» может означать любое число начина с 3 и до бесконечности, потому что «по факту» это «база + 1».
А ещё хочу вот предложить универсальный скрипт на питоне, который может выводит любые числа (и не только числа, вообще всё что угодно). Занимает всего 54 байта.
Хотим, к примеру, вывести на экран число Пи с точностью до двадцатого знака, выполняем
Или можно ещё вот так подойти к решению проблемы: есть такая дёмка Advanced Raytracing. «Занимает» всего 256 байт, но при этом выводит на экран картинку (которую можно увидеть на скриншоте, если по ссылке перейти) которая в виде гифки весит 64кб.
И ещё, если вдруг не натыкались: онлайн библиотека в которой хранятся вообще все тексты которые когда либо были написаны или только ещё будут написаны (правда всё только на английском, так что или транслит или в переводе).
А если серьёзно, то это всё очень похоже на философские жонглирования или шутки типа «данное выражение ложно».
На википедии в статье про Колмогоровскую сложность есть две части: Сжатие и Колмогоровская случайность. И лично я из них делаю вывод что обязательно найдётся строка в 1024 байта для которой ну никак не получится написать программу её выводящую, да ещё такую что она сама уместится в 1024 байта. И ещё я делаю вывод что тут всегда речь идёт о «программе» которая содержит в себе всё необходимое для вывода этой строки.
Другими словами программа, которая перебирает все возможные килобайтники, а потом выводит число которое не нашлось в их результатах, это метод нахождения этого самого числа брутфорсом, а никак не одна из таких программ. Причём из-за проблемы остановки это весьма не самый удачный вид брутфорса.
И вот что ещё меня беспокоит во всей этой затее. Если ещё раз перечитать про колмогоровскую случайность, то можно представить что взяв, скажем, джаваскрипт мы таки найдём строку в 1024 байта которую нельзя вывести программой такой же длинны. То есть программа конечно и для этого числа найдётся, вот только будет длинной, скажем, в 1600 байт.
И на джаваскрипте код этой программы может выглядеть как-то вот так. Всматриваемся в содержимое поля «Original source» и видим что там одна сплошная математика. Сложение, вычитание, косинусы, квадратные корни, битовая ерунда всякая. Я охотно верю что примерно такой код и будет для тех самых «несжимаемых» чисел. Писали писали алгоритм, а он, зараза, длиннее чем 1024 байта. Ну, нас ведь предупреждали, что есть такие вот числа, верно? Ну вот, это оно самое.
А теперь жмём кнопку «Pack» и получаем программу которая почти в два раза короче (821 байт) и при этом делает ровно тоже самое что и оригинал. Неувязочка.
Столько написал, а что сказать-то хотел? Вся эта «гимнастика для ума» безусловно штука полезная и нужная. Вот только перекладывать её на реальный питон надо очень аккуратно дабы не сделать ошибок в интерпретации или не создать случайно вечную брутфорсилку.
А ещё хочу вот предложить универсальный скрипт на питоне, который может выводит любые числа (и не только числа, вообще всё что угодно). Занимает всего 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). Не знаю что там в питоне, но не буду удивлён если ситуация аналогичная.
Первый обман это когда мы говорим «смотрите, эта программа длинной 821 байт выводит строку длиной 1024 байта». На самом деле у нас есть программа которая генерирует вторую программу. А вот уже та вторая программа (длинной 1600 байт) и выводит нужную нам строку.
Второй обман заключается в том что мы выдаём исходный текст программы за байткод который непосредственно и будет выполнять наша машина. В случае джаваскрипта байткод может занимать сильно больше места чем исходный текст из которого он был создан (вот тот кусок скрипта что я использовал для примера распухает почти в два раза после перевода в байткод для V8). Не знаю что там в питоне, но не буду удивлён если ситуация аналогичная.
Байткод как раз не мешает: во-первых, нет проблем создать железку, которая будет выполнять непосредственно байткод — как Java-процессоры. Во-вторых, можно посчитать движок V8 частью программы, и порог парадокса сдвинется с 1КБ на (1КБ + размер V8), но качественно ничего не изменится.
«Одиннадцать» может означать любое число начина с 3 и до бесконечности, потому что «по факту» это «база + 1».
Для математика — да. Для нормального человека, и в том числе для философа Рассела — оно означает 11 в десятичной системе.
Точно так же, «год смерти Тьюринга» для нормального человека означает 1954, хотя я подозреваю, что хотя бы один носитель фамилии Тьюринг умирает каждый год.
Исток парадокса Берри — не математический, а именно философский: Рассел и его корреспонденты пытались понять связь между объектами и их общепринятыми, общепонятными обозначениями.
Как и любой другой парадокс этот основан на смешении мета-языка и языка-объекта. Об этом давно еще писал Альфред Тарский, — нельзя в фразе (язык-объект) говорить о ней самой (мета-язык).
самое маленькое число, для обозначения которого недостаточно восьмидесяти букв плюс 1
а вот это не решение?
а вот это не решение?
Я рад, что вопрос брут-форса алгоритмов перебором кода, закрыли на самой заре CS. Ибо иначе матпорнография какая-то получается: «Мы только что показали, что хоть какая-то программа существует, значит задача решена».
Это парадокс Самореференции возникающий из-за смешения языка и метаязыка. «Самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» не является обозначением числа, а описывает язык обозначения чисел.
Аналогично с программой, она не самостоятельна, а включает в себя все множество программ, тоже является метапрограммой.
Аналогично с программой, она не самостоятельна, а включает в себя все множество программ, тоже является метапрограммой.
Не могу с вами согласиться. Не вижу в фразе «Самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» самореференции. Разве есть проблема с фразой «Самое маленькое число, для записи которого недостаточно восьмидесяти двоичных цифр»? Если бы самореференция имела место, то замена алфавита не могла бы ее убрать. И уж тем более не повлияла бы замена обозначение/запись т. к. запись это частный случай обозначения.
Так в чем же разница? Элементарно в недоопределенности условий первой формулировки и полной определенности (условно, боюсь найдется и в этом случае возможность трактовать по-разному) второй. В первом случае необходимо дополнительно описать все обозначения, которыми владеет субъект. А еще для разных субъектов это будут разные наборы обозначений. И для разных моментов времени для одного и того же субъекта набор обозначений будет отличаться. Но если со всем этим справиться, то будем иметь четкий алгоритм выбора самого маленького числа, для обозначения которого недостаточно восьмидесяти букв для конкретного субъекта в конкретный момент времени. И он будет столь же точным, как и выбор наименьшего двоичного числа для второго примера.
А автору все-же формально следует заменить 34^80 на 35^80 и фразу «из восьмидесяти русских букв и пробелов» на «из восьмидесяти русских букв, пробелов и запятых», ведь вы посчитали запятую в 78 символов длины строки. Или как-то иначе устранить несоответствие.
Так в чем же разница? Элементарно в недоопределенности условий первой формулировки и полной определенности (условно, боюсь найдется и в этом случае возможность трактовать по-разному) второй. В первом случае необходимо дополнительно описать все обозначения, которыми владеет субъект. А еще для разных субъектов это будут разные наборы обозначений. И для разных моментов времени для одного и того же субъекта набор обозначений будет отличаться. Но если со всем этим справиться, то будем иметь четкий алгоритм выбора самого маленького числа, для обозначения которого недостаточно восьмидесяти букв для конкретного субъекта в конкретный момент времени. И он будет столь же точным, как и выбор наименьшего двоичного числа для второго примера.
А автору все-же формально следует заменить 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]);
};
Это просто нормальное математическое утверждение (при условии полного определения задачи, как писал об этом выше). Наверняка вы могли бы написать код и поизящнее чем это сделал я. Но особо и не старался, честно говоря. Главная цель — показать, что в определении значения переменной ни сама переменная ни ссылка на нее не используется и значит Самореференции быть не может. Просто не следует отождествлять строку символов (обозначение) с ее смысловой нагрузкой в понимании субъекта.
Меняя алфавит мы однозначно разделяем язык и метаязык и парадокс исчезает. В случае фразы «Самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» получается нечто похожее на Парадокс Греллинга — Нельсона, когда фраза и описывает саму себя и одновременно опровергает себя.
Мне лично больше нравится подход фон Неймана: данные и код — это одна и та же неразделимая сущность (т.е. bmp-файл — это программа для отображения картинки). И в таком подходе нет разделения на «язык» и «мета-язык». Потому допустима и рекурсия.
Но в таком представлении парадокс тоже буксует: в означенной длине вполне можно записать слово «бесконечность» и, следовательно, такого числа (минимального из всех, что можно описать 80-ю символами) просто может не существовать (это уже надо строго доказывать). Т.е. эта фраза просто не описывает числа.
Но в таком представлении парадокс тоже буксует: в означенной длине вполне можно записать слово «бесконечность» и, следовательно, такого числа (минимального из всех, что можно описать 80-ю символами) просто может не существовать (это уже надо строго доказывать). Т.е. эта фраза просто не описывает числа.
Есть формальное описание описание языка, на пример описание BMP файла, которое не в состоянии отобразить ни одной картинки — вот это метаязык по отношению к «программе для отображения картинки».
И да, «бесконечность» это слишком много и не совсем число, давайте возьмем число «Самое большое число» и получим такую же динамически самоувеличивающуюся переменную.
И да, «бесконечность» это слишком много и не совсем число, давайте возьмем число «Самое большое число» и получим такую же динамически самоувеличивающуюся переменную.
У фон Неймана описание BMP файла и сам BMP файл — это именно сущности одного порядка. И то что наши компьютеры пока не доросли до того, что бы по команде «а сгенери-ка мне пейзажик» выдавать картинку — это чисто технические сложности.
Т.е. тут можно спорить с таким подходом и находить парадоксы, но мне больше нравится воспринимать так (возможно детская травма от кодогенерации тройного порядка SQL DDL->xml->Java->PHP, наш тимлид был затейник).
Т.е. тут можно спорить с таким подходом и находить парадоксы, но мне больше нравится воспринимать так (возможно детская травма от кодогенерации тройного порядка SQL DDL->xml->Java->PHP, наш тимлид был затейник).
Чуть выше ответил synedra как раз по этому поводу. Утверждаю, что в данном выражении Самореференции нет, нет и смешивания языка и метаязыка, а есть абсолютно нормальное математическое утверждение, однако в условиях недоопределенности задачи. Подробнее посмотрите пожалуйста одним уровнем выше.
— Что такое парадокс?
— Двоюродный брат фокуса (который показывает фокусник), там он прячет кролика в ящике, а тут тоже что-то похожее делают.
По условию каждому набору букв соответствует число некоторое, пропуски чисел возможны (какие-то числа меньше 34^80 не будут использованы, а будут использованы бОльшие числа). Есть массив чисел и есть массив строк, каждая строка указывает на число. Сто — это просто 100, гугол — это просто гугол. А одна строка пытается через логику указать на число за пределом этого массива.
— Двоюродный брат фокуса (который показывает фокусник), там он прячет кролика в ящике, а тут тоже что-то похожее делают.
По условию каждому набору букв соответствует число некоторое, пропуски чисел возможны (какие-то числа меньше 34^80 не будут использованы, а будут использованы бОльшие числа). Есть массив чисел и есть массив строк, каждая строка указывает на число. Сто — это просто 100, гугол — это просто гугол. А одна строка пытается через логику указать на число за пределом этого массива.
Интересно, а причём здесь сжатие данных?
Задачу (проблему) сжатия данных нельзя же рассматривать в отрыве такого понятия как стохастический поток сообщений (букв). Причём тут каждое слово важно — и стохастичность и наличие потока — т.е. достаточно большого количества.
Без этого сжать можно до одного бита (есть/нет вот эта длиннющая простыня захардкоженная в алгоритме сжатия/расшифровки — пресловутый «утюг в окне»)
Задачу (проблему) сжатия данных нельзя же рассматривать в отрыве такого понятия как стохастический поток сообщений (букв). Причём тут каждое слово важно — и стохастичность и наличие потока — т.е. достаточно большого количества.
Без этого сжать можно до одного бита (есть/нет вот эта длиннющая простыня захардкоженная в алгоритме сжатия/расшифровки — пресловутый «утюг в окне»)
Что мешает рассматривать алгоритмы сжатия конечных и неслучайных текстов? Например, русских числительных?
В конце концов, практически используемые алгоритмы сжатия работают именно с конечными и неслучайными файлами, а не с бесконечным стохастическим потоком.
В конце концов, практически используемые алгоритмы сжатия работают именно с конечными и неслучайными файлами, а не с бесконечным стохастическим потоком.
Как раз именно со стохастическим потоком все практические алгоритмы дело и имеют — программа и её создатели ничего не знают о том что конкретно она будет сжимать на своём жизненном пути, только некую обобщённую статистику. Поэтому что-то жмётся хорошо, а что-то вообще увеличивается при использовании одного и того же алгоритма.
А алгоритм сжатия и расшифровки конечного и неслучайного текста я вам привёл. Сжимается такой текст ровно в 1 бит.
(Я не понимаю, вы Шеннона решили опровергнуть?)
А алгоритм сжатия и расшифровки конечного и неслучайного текста я вам привёл. Сжимается такой текст ровно в 1 бит.
(Я не понимаю, вы Шеннона решили опровергнуть?)
При чём тут Шеннон?
Возьмём практический алгоритм сжатия JPEG — он работает со стохастическим потоком, или с двумерной матрицей наперёд известного размера?
Возьмём практический алгоритм сжатия JPEG — он работает со стохастическим потоком, или с двумерной матрицей наперёд известного размера?
Шеннон ввёл понятие информационной энтропии и доказал парочку — другую теорем про неё связи с обменом сообщениями. Не? В частности там что-то есть и про сжатие…
Алгоритм JPEG работает со стохастическим потоком матриц заранее неизвестных размеров. По крайней мере у меня одной и той же программой в JPEG сохраняются как картинки 1x1, так и 1023х767 и никаких ограничений он на меня не накладывал.
Очень сомнительно практическое будущее алгоритма способного работать с матрицами только наперёд известного размера.
Алгоритм JPEG работает со стохастическим потоком матриц заранее неизвестных размеров. По крайней мере у меня одной и той же программой в JPEG сохраняются как картинки 1x1, так и 1023х767 и никаких ограничений он на меня не накладывал.
Очень сомнительно практическое будущее алгоритма способного работать с матрицами только наперёд известного размера.
Вы можете привести утверждение Шеннона, которое, по-вашему, я пытаюсь опровергнуть?
По-видимому, мы с вами по-разному понимаем, что такое «поток». Обычно «поток» — это то, в начале чего неизвестно, когда будет конец. Изображения от потока принципиально отличаются тем, что размер изображения известен ещё до чтения первого элемента матрицы.
По-видимому, мы с вами по-разному понимаем, что такое «поток». Обычно «поток» — это то, в начале чего неизвестно, когда будет конец. Изображения от потока принципиально отличаются тем, что размер изображения известен ещё до чтения первого элемента матрицы.
Что энтропия конечного и неслучайного текста выше нуля и потому имеет какой-то разумный смысл рассматривать алгоритмы сжатия и кодирования таких объектов.
По потокам- действительно понимание разное, нигде никогда не говорится, что у потока не может быть точно известного конца и начала. Он вполне может быть и фиксированной длинны. А может и не быть.
По файлам — сами файлы образуют «поток файлов». Никто не пишет «практический алгоритм» для кодирования одного, десяти или другого конечного, заранее известного количества файлов. Файлы — именно что неизвестно когда они в этих проклятых интернетах закончатся. Но мы должны сжать и распаковать их все (хотя и понятно, что их будет конечное количество — интернеты с JPEG когда-нибудь закончатся).
По файлам — сами файлы образуют «поток файлов». Никто не пишет «практический алгоритм» для кодирования одного, десяти или другого конечного, заранее известного количества файлов. Файлы — именно что неизвестно когда они в этих проклятых интернетах закончатся. Но мы должны сжать и распаковать их все (хотя и понятно, что их будет конечное количество — интернеты с 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, обозначить таким образом невозможно» — то вы ошиблись :-)
Увы, я так и прочитал, упустил частицу «не».
Но если прочитать правильно — то смысла в этой фразе я вообще не вижу. Почему невозможно?
Но если прочитать правильно — то смысла в этой фразе я вообще не вижу. Почему невозможно?
Раз возможных обозначений 3480, значит обозначаемых ими чисел не больше чем 3480, значит какие-то числа среди первых 3480 обозначить восьмидесятью буквами невозможно.
Почему?
большая часть возможных обозначений не соответствует никаким числама вот это оговорено не было. А кстати, почему не соответствует? Просто волевым решением?
В случае сплошного сопоставления — таки не понимаю, с чего невозможно-то. Если это возможно для алфавита из цифр, то почему нет для расширенного? По сути, «обозначение, составленное из букв» само по себе является числом, записанным в системе счисления с основанием, равным количеству букв в алфавите (то есть буква — это цифра).
Каким числам вы бы сопоставили строки «абырвалг», «быстрая коричневая лиса» и «натуральное число между двумя и тремя»?
Речь в статье не об изобретении новой кодировки «base34-RU», а об обозначениях чисел, используемых людьми и понятных людям, — таких, как «одиннадцать», «пять девяток», и «год смерти Тьюринга».
Речь в статье не об изобретении новой кодировки «base34-RU», а об обозначениях чисел, используемых людьми и понятных людям, — таких, как «одиннадцать», «пять девяток», и «год смерти Тьюринга».
Каким числам вы бы сопоставили строки «абырвалг»
Ну, например, 0xE0E1FBF0E2E0EBE3
а об обозначениях чисел, используемых людьми и понятных людям
А обозначение типа 0x5A081F — не понятно людям?
Вы хотите меня убедить, что если вместо привычных людям обозначений взять вашу кодировку, то парадокс Берри не возникнет?
Совершенно верно, не возникнет. А при использовании привычных людям обозначений — возникает.
Совершенно верно, не возникнет. А при использовании привычных людям обозначений — возникает.
Тут ещё такой вопрос. Насколько являются валидными фразы:
— «один и два»
— «пять или двадцать пять»
Если они невалидны, т.к. указывают на непонятно какое число, то и ключевую фразу тогда можно назвать невалидной, т.к. она тоже не указывает на непонятно какое число.
Т.е. парадокса нет.
Если же эти фразы валидны, то валидна и фраза:
— «все натуральные числа»
И снова, парадокса нет.
Что скажете?
— «один и два»
— «пять или двадцать пять»
Если они невалидны, т.к. указывают на непонятно какое число, то и ключевую фразу тогда можно назвать невалидной, т.к. она тоже не указывает на непонятно какое число.
Т.е. парадокса нет.
Если же эти фразы валидны, то валидна и фраза:
— «все натуральные числа»
И снова, парадокса нет.
Что скажете?
Есть бессмысленные комбинации букв. И для «человеческого» описания цифр (т.е. не кодирование, а простой язык) таких комбинаций будет большинство.
Но это не имеет особого значения в данном парадоксе: главное что это НЕ все возможные _натуральные_ числа (для ненатуральных парадокс не работает).
Следовательно среди оставшихся должно найтись наименьшее ( это свойство любого подмножества натуральных чисел).
Тут как раз можно и провести атаку на парадокс: составить рекурсивное описание, которое назовёт каждое натуральное число.
Но это не имеет особого значения в данном парадоксе: главное что это НЕ все возможные _натуральные_ числа (для ненатуральных парадокс не работает).
Следовательно среди оставшихся должно найтись наименьшее ( это свойство любого подмножества натуральных чисел).
Тут как раз можно и провести атаку на парадокс: составить рекурсивное описание, которое назовёт каждое натуральное число.
А почему бессмысленные комбинации букв не могут быть обозначениями чисел? Что-то я не вижу, чтобы требование осмысленности оговаривалось в тексте. Вообще, слова «смысл» в статье не встречается ни разу.
Используется только слово «обозначение», а обозначение это всего лишь некое соответствие, сопоставление (заданное аналитически, алгоритмически или таблично).
Примеры, приводимые в статье, я воспринял именно как экзотические частные случаи кодирования, отнюдь не исключащие кодирования простого (про которое я и распинываюсь в своих комментах).
Используется только слово «обозначение», а обозначение это всего лишь некое соответствие, сопоставление (заданное аналитически, алгоритмически или таблично).
(т.е. не кодирование, а простой язык)Из статьи это как-то не очевидно, особенно учитывая ее заголовок. Если мы рассуждаем о сжатии данных, это напрямую подразумевает именно что кодирование.
Примеры, приводимые в статье, я воспринял именно как экзотические частные случаи кодирования, отнюдь не исключащие кодирования простого (про которое я и распинываюсь в своих комментах).
Да какая разница? Для парадокса важно, что в рамках 80ти символов нельзя назвать каждое число.
А осмысленность требуется чтобы работала ключевая фраза: «наименьшее число, которое нельзя описать меньше чем ста символами»
А осмысленность требуется чтобы работала ключевая фраза: «наименьшее число, которое нельзя описать меньше чем ста символами»
Во втором предложении статьи оговаривается, что словом «одиннадцать» принято обозначать число 11, а не 0xd0bed0b4d0b8d0bdd0bdd0b0d0b4d186d0b0d182d18c. По-моему, из этого ясно, что речь идёт о смысле, а не о тридцатичетыричной (или любой другой) кодировке.
Совершенно неясно, поскольку пассаж о «из восьмидесяти русских букв и пробелов можно составить всего 3480 обозначений» склоняет именно к 34-ричной системе кодирования.
Вы не один такой, force тоже подумал про 34-ричное кодирование. В действительности, 34-ричные комбинации используются только для подсчёта возможных обозначений, а не для определения обозначаемых чисел.
Если предложите, как сформулировать эту идею понятнее, то я охотно исправлю статью.
Если предложите, как сформулировать эту идею понятнее, то я охотно исправлю статью.
Или не завершится? Ведь среди всех программ, которые будут испробованы, встретится while True: pass (и её функциональные аналоги) — и дальше проверки такой программы дело уже не пойдёт!
Вообще не обязательно.
Давайте сделаем так: разобьём каждую программу на некие атомарные операции и сделаем очередь программ. Затем будем каждую итерацию добавлять в список следующую программу и исполнять по одной атомарной итерации из каждой программы списка.
Таким образом, любая программа будет запущена через некоторое конечное время.
(что конечно же не сработает на практике, но ведь мы не об этом говорим?)
Не надо пытаться опровергнуть теорему об остановке.
Невозможно произвольную программу разбить только на атомарные операции. А с фундаментально неатомарными приходим к тому с чего начали
Невозможно произвольную программу разбить только на атомарные операции. А с фундаментально неатомарными приходим к тому с чего начали
Хмм, а почему нельзя произвольную программу разбить на атомарные операции? Давайте возьмём машину Тьюринга, там атомарные операции вполне очевидны, и программа разбивается на них просто по определению. Нет?
Возможно, я сейчас спрашиваю о каких-то банальных вещах, которые рассказывают в институте на Computer Science, но я, к сожалению, учился на немного другом направлении.
Возможно, я сейчас спрашиваю о каких-то банальных вещах, которые рассказывают в институте на Computer Science, но я, к сожалению, учился на немного другом направлении.
Таким образом, любая программа будет запущена через некоторое конечное время.
Вы правы, ваш подход это обеспечит.
Но в какой момент программа-генератор может выводить до сих пор не «вычеркнутое» число в качестве искомого? Может быть, одна из запущенных программ через несколько шагов его как раз выведет и тем самым «вычеркнет»?
Попробуйте доказать, что строка "омышнхи" не обозначает искомое число.
Это "наводящий вопрос" на ответ. Вначале нужно определить значения для всех обозначений - только тогда будет иметь смысл поставленный в статье вопрос.
Sign up to leave a comment.
Парадоксы о сжатии данных