Краткий аргумент в пользу фундаментальной роли двоичных цифр как информационных единиц.

Я проясню контекст этого вопроса, чтобы потенциальные ответы могли быть эффективно направлены на то, что я ищу.

Информация (по крайней мере, в несемантическом, каноническом смысле слова) может быть определена с использованием либо статистического подхода Шеннона, либо вычислительного подхода Колмогорова. Первый устанавливает его как понятие средней длины кодового слова, выраженное в некотором произвольном алфавите — который намеренно выбран в качестве двоичного алфавита в любом учебнике, который я могу процитировать, — необходимом для установления биективного отображения на результаты случайного источника; Теорема исходного кодированиядоказывает, что это определение равно энтропии источника в статистическом пределе бесконечного числа исходов. Второй подход использует универсальные компьютеры в некоторой произвольной модели (почти всегда выбранной в качестве UTM), а затем определяет информацию, содержащуюся в источнике, как длину минимальной программы с саморазграничением на языке компьютера, который выводит результат. результаты источника; поскольку выбор эталонного UTM может только сделать длину минимальной программы постоянным членом, отличным от любого другого выбора , определение достаточно надежное.

Действительно, подход Колмогорова включает в себя определение Шеннона , потому что априорные значения распределения вероятностей, необходимые для кодирования источника и декодирования сообщений, эквивалентны машине Тьюринга, которая вычисляет схему энтропийного кодирования (например, кодирование Хаффмана или арифметическое кодирование).

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

Тем не менее, я нахожу эту историю несколько неудовлетворительной. Использование вычислений в качестве основы для информации кажется переворачиванием мира с ног на голову, по крайней мере, при интуитивном понимании того, что обозначает этот термин, и вопреки каноническим определениям Шеннона и Колмогорова. Компьютеры — это процедуры (или объекты, следующие за процедурами, бессмысленное различие в свете универсальности Тьюринга и взаимного моделирования машин), и поэтому они представляют собой особый вид отношения — рекурсию — между входом и выходом . Несмотря на то, что этот вид отношения уникален и абсолютен, мне кажется, что он необходимо постфактум к понятию ввода и вывода; а эти двое и есть "вещи"что интуитивно соответствует термину «информация». Вы можете сказать, что вычисление существует, показав историю шагов (сложенный список входов-выходов), точно так же, как вы можете явно показать логический вывод в последовательной записи. Тогда тезис Черча-Тьюринга будет просто утверждать, что класс стеков входов и выходов, которые могут быть эффективно получены любыми средствами, исчерпывается машиной Тьюринга или любой другой эквивалентной моделью вычислений.

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

Чтобы закончить этот раздел, я оставляю это резюме:

  1. Информация, понимаемая в интуитивном смысле как «обобщенный абстрактный материал» , кажется более фундаментальной, чем вычисление, учитывая, что понятие процедуры подразумевает ссылку на первое. Информацию следует понимать как простые цепочки символов, а символы следует понимать как обобщенные вещи (все, что можно различить );
  2. То, к чему относится канонический термин «информация», является вычислительным свойством информации в смысле 1. Я лично предпочитаю использовать термин « сложность » в обоих случаях определений Шеннона и Колмогорова и сохранить термин «информация» просто как «материал». (без ссылки на априорные вычисления или вероятности; т. е. строки «как задано»).

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

Теперь я правильно сформулирую свой вопрос:

  • а) Как можно кратко (но не эвристически ) доказать, что бит является фундаментальной единицей информации, и нет ничего проще или меньше, что могло бы выполнять эту работу?

И я оставляю этот мета-вопрос, исходя из слишком длинного вступления к основному вопросу:

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

И, наконец, конечно:

  • в) Имеет ли смысл все, что я здесь написал?
«Информацию следует понимать как простые цепочки символов, а символы следует понимать как обобщенный материал (все, что можно различить) [...] Предполагая, что информация является фундаментальным материалом, необходимым для того, чтобы концепция вычислений имела смысл, один может задаться вопросом, какой минимальный алфавит (т. е. минимальное количество различных символов) необходим для выражения любой формы информации [...]». Если информация представляет собой строку символов, которая может представлять произвольные различимые вещи, что мешает вам просто заключить, что минимум двух различимых референтов?
Потому что для человека, не имеющего знаний в области теории кодирования, не очевидно, что одного единственного символа (унарного) недостаточно для создания различимых объектов. В ответе Рекса Керра ниже я объяснил, как я решаю эти вопросы, но я чувствую, что это огромное излишество, и должен быть более простой или более элегантный аргумент, чтобы использовать двоичный код как минимальный алфавит, способный выражать любую форму информации ( факт, который, кроме того, считается само собой разумеющимся в любом стандартном учебнике). Я не разделяю точку зрения, что двоичный код — это просто инженерный выбор: его оправдывает минималистская основа.
Проблема с унарными схемами заключается в том, что они не увеличивают количество различных сигналов при декартовом произведении. Счет по пальцам, конечно, соответствует побочному продукту, который объединяет различные альтернативы, поэтому считать их как находящиеся в одном алфавите — обман; аналогичные замечания относятся к EOF, который просто указывает по положению, какому элементу счетного копроизведения принадлежит элемент. Поэтому, если мы допускаем прямую теорию комбинаторики, достаточно простого ответа «по крайней мере два символа». (А если у вас нет теории комбинаторики, вы не можете ничего заключить.)
Если вы можете привести аргумент, используя только комбинаторику, обосновывая минимальность двоичного алфавита, а также объяснить, почему это не работает для наивной интуиции счета пальцев (или любой другой унарной схемы), не расширяя свой «математический инструментарий», то вы должны это опубликовать. как ответ, потому что это главный вопрос (а), на который я пришел сюда в поисках ответа.

Ответы (3)

Резюме

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

Чтобы иметь единицу информации, вы должны иметь по крайней мере два возможных состояния дел. Условно мы могли бы описать это положение дел как истинностное значение логического предложения: у нас либо есть А , либо нет-А . Такое бинарное различение — самый грубый и самый элементарный способ различения положений дел в классической (и родственных формах булевой логики). Любая теория информации, вытекающая из такой логики, неизбежно будет склоняться к указанию бивалентного выбора — т . е  . бита — в качестве единицы информации.

Комбинаторика и необходимость алфавитов размера > 1

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

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

Таким образом, мы можем смоделировать алфавит T произвольного размера, просто используя достаточно большое количество символов из меньшего алфавита Σ . Но если вы не используете фиксированный код, в котором по первым n символам вы можете быть уверены, ожидаете ли вы n +1 st символ для завершения сообщения, вы должны использовать строки фиксированной длины.

Мы можем моделировать строки фиксированной длины n - кратным (декартовым) произведением алфавита на себя, Σ n . Проблема с унарным алфавитом Σ  = {1} заключается в том, что Σ n имеет тот же размер, что и сам Σ , что противоречит цели.

Что мешает нам рассмотреть строки переменной длины? Если у нас есть многобуквенные алфавиты, то вообще ничего; но мы должны четко понимать, как мы описываем длину строки — которая, метаданные или нет, по-прежнему является информацией; он определяет, как мы должны интерпретировать сигнал. Например, на жестком диске символ конца файла E на самом деле не означает, что после диска нет никакой информации; только то, что любые данные, которые следуют, не имеют отношения к передаваемой информации (например, к конкретному файлу, на который делается ссылка).

Математически мы можем описать файлы длиной от 0 до n , используя один из символов E для обозначения «конца сообщения», что означает, что две строки, которые совпадают до этого символа, должны рассматриваться как эквивалентные. Например, используя алфавит Σ  = {1,E}, мы бы сказали, что две строки

111E1111 и 111E1EE1

как эквивалентные, поскольку они согласуются до самого левого символа E. Мы бы сократили класс эквивалентности, к которому принадлежат обе эти строки, как 111. Однако нам нужен второй символ, чтобы определить, где заканчивается «информационное содержание» строки, и тем самым указать, какой класс эквивалентности строк мы подразумеваем сообщением. . Это также было бы верно в практическом контексте связи, где протоколы настроены для указания различным устройствам, когда они фактически больше не взаимодействуют с удаленным устройством (вместо того, чтобы интерпретировать случайный шум как данные).

Конечно, мы обычно не описываем строки различной длины в терминах классов эквивалентности строк любой конечной или бесконечной длины. Это, однако, удобство; в повседневной практике, в математике, как и в обычной прозе, у нас есть маркеры конца последовательности, хотя бы в виде пробелов и знаков препинания, которые сами по себе являются отличным сигналом от любой маркировки, такой как 0 или 1; когда я пишу 11 и 101, вы знаете, что это строки длины 2 и 3 соответственно, потому что одна заканчивается пробелом, а другая запятой. Вы не перепутаете их со строками « 11 и... » или « 101, вы знаете...", потому что соглашения нашего письменного языка устанавливают их как потенциальные маркеры конца последовательности для слов или строк символов в целом. То есть они передают эту информацию. Не интерпретируя их таким образом, вы бы не поняли, когда слово или предложение закончилось, и, таким образом, нет места, чтобы ограничить сложность сообщения, которое я посылаю вам.

Тот, кто настаивает (я бы сказал наивно), что может «интуитивно» различать унарные последовательности произвольной длины и, таким образом, передавать разные сообщения со строками 1, 11, 111, 1111, 11111 и т. д., я бы сказал, что это снова падает к той же проблеме, что и алфавит бесконечной длины; метаданные становятся критически важными для решения проблемы различения возможных сигналов, и поэтому, в конце концов, метаданные кодируют сообщение, т.е. метаданные — это сами данные. Я не думаю, что можно сразу уловить разницу между двумя сообщениями 111...1, которые продолжаются на 1000 символов, от одного из 1001 символов; само представление должно содержать подсказки о том, где сообщение начинается и заканчивается, хотя бы в виде пробела в виде покоящегося базового сигнала вместо явного сигнала. Различение того, закончилось сообщение или нет, становится решающим для определения того, где закончилось сообщение.

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

[Отредактировано для добавления замечаний по комбинаторике, унарным схемам]

«Для того, чтобы иметь единицу информации, вы должны иметь по крайней мере два возможных состояния дел». Я не хочу настаивать на этом, но повторение одного состояния дел (унарной схемы) кажется достаточно интуитивно понятным, чтобы быть более минималистичным средством выражения информации. Поэтому я боюсь, что вы повторяете стандартную позицию, считая это слишком очевидным, чтобы требовать обоснования.
@mono: я не понимаю, где вы здесь находите проблему - мне это кажется основным, но я могу что-то упустить. Можете ли вы описать свою « унарную схему , которая является более минималистичным средством выражения информации»?
@mono: я подробно изложил свой ответ. ( Обратите внимание : я не делаю конкретных ссылок на сопутствующие продукты, потому что, хотя я считаю, что это подходящий способ описания выбора между одним или несколькими различимыми элементами, это спорно, если проблема состоит в том, чтобы найти способы различения элементов в первую очередь. )
@NieldeBeaudrap: благодарю за уточнение. Это тот ответ, который я искал. Я нахожу последнее предложение особенно ценным: если длина сообщения неопределенна, каждое сообщение должно содержать, помимо своей длины , заданной самим собой, которая тривиально распознается как полученная, дополнительное различимое, которое явно указывает, какова эта длина. И унарное сообщение может сигнализировать только о своей внутренней длине, а не о том, какая эта длина вдобавок к этому. Для этого требуется маркер и, по крайней мере, двоичный алфавит (и выбор алфавита оправдан минимализмом).
Вы также можете возразить, что, не имея второго символа, унарная схема может создавать только строки, которые, являясь префиксами каждого большего допустимого, сохраняют неоднозначность до тех пор, пока не будет достигнута максимально допустимая длина сообщения (т. е. набор из десяти пальцев на руке). ). Эта строка максимальной длины не является двусмысленной, но является единственным однозначным сообщением, которое может быть когда-либо закодировано в схеме; а если нет максимальной длины (т.е. классический канал связи), то каждое конечное сообщение неоднозначно. Я должен признать, что этот аргумент не так лаконичен, как мне бы хотелось изначально, но его достаточно.
@Mono: я хотел бы сделать ответ более кратким, но если вы найдете резюме неубедительным в свете идеи унарных схем, необходимо уточнить, как унарные схемы полностью не различают положения дел даже при конкатенации. , потому что второй символ требуется даже для того, чтобы сообщить, где заканчивается сообщение.

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

Кроме того, большое значение имеют постоянные факторы. Если я изобрету язык программирования, который содержит предыдущий абзац в виде символа ☆, тогда будет просто постоянная разница в длине программы для выражения вышеуказанного абзаца (примерно в 440 раз), и все же я совершенно не уловил интуитивную информацию об информации, которую Колмогоров предположительно стремился. Если вы не накладываете на себя ограничение на использование компактных вычислительных устройств общего назначения, информационные измерения Колмогорова возвращают бессмысленные результаты. Это также показывает, что вычисление не является фундаментальным для информации. Скорее, это инструмент (который нужно правильно использовать) для анализа.

Тем не менее, я не верю, что вы можете «доказать», что бит является основной единицей информации. Вы, безусловно, можете принять набор аксиом, который включает в себя что-то, что логически эквивалентно тому, что «бит является фундаментальной единицей информации». Большинство текстов по информации Шеннона делают именно это (поскольку они доказывают, что информация Шеннона -p log pявляется правильной † , а наиболее тривиальное с точки зрения вычислений представление * имеет log= log2). Но если вы спросите на более глубоком уровне, я не думаю, что вы сможете показать, что бит имеет фундаментальное значение, а не потенциал действия (или синаптическое высвобождение) с биологической точки зрения; или чем стандартное отклонение(или доверительный интервал) с точки зрения аналоговой статистики. На каком-то уровне они все эквивалентны (но вам нужно довольно много копать, чтобы перейти от одного к другому), и то, что вы предпочитаете, будет зависеть от вашей точки зрения.

† По очень веской причине, как вам подтвердит любой вводный учебник.

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

Ваш ответ пока единственный, который касается того, о чем я спрашивал. С одной стороны, вы указываете другую причину (возможно, более фундаментальную), почему вычисления не кажутся «автономными примитивами», по которым должна определяться информация; Я сосредоточился на обязательной ссылке на входы-выходы, внешние по отношению к понятию вычислений, а вы указали на относительность, связанную с определением Колмогорова (причина размера постоянного члена, который становится незначительным только при описании очень длинных последовательностей, аналогично статистический предел исходного кодирования в теории Шеннона).
С другой стороны, поскольку понятие вычислений включает некоторое «взаимодействие» (т. е. обработку) необработанных строк символов, я предпочитаю использовать термин «сложность» для этих метрик и резервировать «информацию» для обозначения общих строк, т. е. последовательностей. символов «как дано». В этом смысле я хотел иметь краткий аргумент (но полуформальный или, по крайней мере, не чисто эвристический) для идеи, что два символа являются минимальным набором различных значений, достаточных для выражения любой информации. Я не читал ни одной книги по теории информации, где этот вопрос заслуживает отдельного места; это просто "предполагается".
@Mono - Вы ищете что-то более сложное, чем если бы у вас была только одна вещь, нет никаких различий и никакой информации; меньшее, что вы можете добавить к картине, это еще одна вещь, которая дает вам возможность выделиться и получить информацию .
Я был бы очень признателен, если бы вы могли процитировать литературу, в которой установлено, что «самое тривиальное в вычислительном отношении представление - это log = log2». Это, безусловно, «тривиальная проблема» для человека, инициированного в этой области, но не настолько тривиальной, чтобы объяснить ее кому-то другому. Люди спрашивали меня, «почему не унарный, ведь мы считаем пальцами», и в этих случаях мне приходилось указывать на необходимость маркеров в конце каждой строки , что невозможно в односимвольном алфавите, но в целом аргумент всегда казался излишним.
Точно, но не слишком эвристично. Я хочу иметь возможность исключать любые другие, казалось бы, «более простые» схемы (я могу думать только об унарных, но, возможно, там есть что-то еще), не прибегая к излишествам, таким как цитирование теории кодирования (что я и делал). отвечая на вопрос о счете пальцев).
@Mono - я говорю не о двух символах, а о всем пространстве состояний . Вы не можете кодировать унарно с одной вещью; есть только одна вещь, и это все. С пространством состояний из двух вы можете иметь либо одно состояние, либо другое. Это наименьшее возможное невырожденное пространство состояний. Отсюда и бинарность: вы можете представлять свои состояния. Нет действительно веской причины выбирать двоичный, потому что H = -C * sum_i(- p_i log p_i)изменение базы logпросто изменяет константу. Это «самый простой» в том смысле, что пространство состояний из двух является самым простым из возможных, и вы можете выбрать построение из него.
Я не знаю точно, что вы подразумеваете под «пространством состояний». Я могу вспомнить только термодинамические макроскопические диаграммы равновесия и фазовое пространство p vs. x в статистической механике (возможно, потому, что это то место, откуда я пришел в академическом плане). Если бы вы могли подробнее рассказать об этом в своем ответе, было бы интересно прочитать, хотя я не уверен, что это можно было бы квалифицировать как объяснение без излишеств.
@Mono: Давайте перечислим все возможные положения дел: {0}. Ну, это скучно, не так ли? Попробуем еще раз: {0, 1}. Эй, теперь у нас есть информация - какая из двух возможностей это? Это все, что я пытаюсь сказать. Это не очень глубоко, поэтому я не думаю, что есть сильный аргумент в пользу двоичного кода. Если бы тристабильность была действительно распространена, а бистабильность — нет, то мы бы использовали основание 3, а бистабильность была бы вырожденным случаем тристабильности.

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

Вкратце обоснование выглядит так:

а. Какие знания у нас есть, можно систематизировать математически

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

в. самое простое представление в системе счисления по основанию 2

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

Письмо — это форма информации, и если бы не было реального человека , который бы его понимал , это была бы просто последовательность геометрических форм, разделенных пробелами.

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

Какое другое основание для определения информации вы бы выбрали? Есть ли способ получить единицу информации, которая не сводится к различию да/нет?
@deBeaudrap: Почему необходимо уваривать ? Я знаю, почему это делается, добродетели прагматичны; но это не делает такое представление информации фундаментальным . Например, машины Тьюринга работают с бесконечной полосой, отмеченной единицами и нулями, но на самом деле можно использовать и другие алфавиты.
@Ullah: в контексте вопроса «фундаментальный» означает «ничего проще или меньше» как единица информации, согласно ОП. Работать не проще, а минимально.
@DeBeaudrap: я это понимаю. Вот почему я сказал, что самое простое представление было в базе 2. В центре моего ответа было то, почему минимальное представление «неудовлетворительно» и похоже на «переворачивание мира с ног на голову».
Краткий аргумент в пользу фундаментальной роли двоичных цифр как информационных единиц.
СпросиСетьПолитика конфиденциальности1y, 0v