Аннотация: Что есть информация? Энтропия двоичных комбинаций.
О структуре случайности. Часть первая.
Я спрашиваю вас: если в каждой ячейке памяти компьютера (или любой другой памяти) содержатся только "нули", то хранит ли эта память какую-нибудь осмысленную информацию, способную повлиять на наши решения?
Я тоже до недавнего времени думал, что не хранит. Но это может быть и не так. Давайте разберемся с этим вопросом. Но вначале расскажу об одном эксперименте, проведенном в бытность розыгрыша спортивных лотерей "5 из 36". Играющим в лотерею предлагалось заполнить билет комбинацией 1-2-3-4-5 (еще лучше комбинацией 17-18-19-20-21, подумайте, почему?). Разумеется, никто не соглашался. Примерный ответ был такой: "Не держи меня за идиота - такая комбинация никогда не выпадет".
Но мы то с вами знаем, что если лототрон выбрасывает шары с равной вероятностью, то предлагавшаяся комбинация цифр ничуть не менее вероятна, чем любая иная. Это лишь наша психика приписывает какие-то особенности комбинациям с подряд идущими цифрами. На самом деле все комбинации цифр совершенно равноправны.
Нечто подобное происходит и тогда, когда мы наблюдаем за состоянием некоторой памяти. Выделение "нулевого" состояния памяти из всех других (при решении вопроса о наличии в ней или отсутствии информации) - это чисто эмоциональное решение. Покажем, что это действительно так. Но вначале, в связи с определенной неудовлетворенностью по поводу предыдущего изложения мной материала по теме "Информация" (см. http://www.hot.ee/markal/inf.htm), сделаем дополнение к этой теме.
Термин "информация", как уже отмечалось, употребляют в разных смыслах. На самом деле, эти словоупотребления содержат в себе два разных представления о том, что есть информация. Общим для этих представлений является следующее.
Всякая незамкнутая система взаимодействует с окружающим миром посредством испускания (и поглощения) каких-либо частиц, полей и т.п. Эти носители энергии назовем информационными символами. Внутренняя структура систем (объектов) разная, и статистика генерируемых ими символов зависит от этой структуры. В частности, как крайние представители, есть, во-первых, детерминированные источники информационных символов, когда испускание очередного символа полностью предсказуемо. Во-вторых, существуют объекты, которые генерируют те или иные символы независимо друг от друга в то или иное время с определенной вероятностью. Есть, разумеется, и промежуточные варианты, когда источник обладает внутренней памятью, и вероятности испускаемых символов зависят от ранее испущенных символов.
Информационные символы, испущенные источником, попадают на другие объекты - приемники информационных символов. В качестве крайних представителей и здесь можно представить себе, во-первых, такие приемники, которые не имеют внутренних устойчивых состояний, и под воздействием информационных символов меняют только свои энергетические показатели (скорость и т.п.). Во-вторых, есть приемники, которые обладают достаточной памятью, и запоминают все принятые информационные символы.
----------------------------------
["Память" - это любое (механическое, электрическое, биологическое и т.д.) устройство с некоторым целым (большим единицы) числом устойчивых состояний. Если число таких состояний равно n, то информационная емкость I памяти составляет I = logn бит. (Логарифм по основанию 2).
Что касается термина "устойчивое состояние" (неизменность состояния во времени), то относительно него можно высказать следующие противоположные суждения.
Первое. Любой реальный объект не меняет свое состояние во времени, если он не подвергается воздействию никаких внешних и внутренних сил.
Второе. Для того чтобы состояние объекта не менялось во времени, необходимо воздействие на него определенных внешних и/или внутренних сил.
Какое из них верно? Предпочтение следует, по-видимому, отдать второй формулировке. Посудите сами. С одной стороны, нет объектов, которые не подвергались бы внешнему воздействию. С другой стороны, даже в замкнутой (невзаимодействующей) системе с течением времени энтропия, как правило, возрастает, то есть состояние системы меняется со временем, и для его неизменности требуется вмешательство определенных сил.]
---------------------------------
Теперь обсудим разницу в двух представлениях о том, что такое информация.
Первое представление таково. Информация - это неопределенность, имевшая место быть при ожидании появления символов от источника, и устраненная благодаря появлению этих символов. Короче: информация - это устраненная неопределенность. Ее мерой служит энтропия источника. Чем больше энтропия источника, тем больше информации получают от него.
Вот пример. Пусть источник информации генерирует 32 символа русского алфавита (символы "е" и "ё" полагаем совпадающими). При этом возможны следующие варианты.
1. Символы выбираются источником случайным образом с равной вероятностью выбора любого из них. Тогда каждый очередной символ содержит 5 бит информации.
2. Источником информации может быть человек, читающий лекцию студентам. Тогда, учитывая избыточность русской речи, количество получаемой информации равно в среднем одному биту на каждый воспроизведенный символ. [Эта избыточность составляет 80%, поэтому на один символ в среднем приходится не 5 бит, а один. (Е.Седов, Одна формула и весь мир. М. Знание,, 1982, с. 46, 49, 56)]
3. Источником информации является магнитофон (или любое иное воспроизводящее устройство), который озвучивает известное нам стихотворение на русском языке. Тогда любой очередной символ предсказуем с достоверностью и, значит, не содержит в себе информации вообще. [ Подобный пример отсутствия передачи информации от источника, когда последний вычисляет значения очередного разряда числа "пи", приведен в работе К. Шеннон. Математическая теория связи. В кн.: Работы по теории информации и кибернетике. М., 1963, с.273]
Второе представление. Информацией называют запись информационных символов в некоторой памяти.
В приведенном выше примере в первом варианте для запоминания последовательности, состоящей из n символов, требуется память в 5n бит. Во втором случае (при подобранном соответствующим образом кодировании символов) для запоминания последовательности, состоящей из n символов, требуется память примерно в n бит (чем больше n, тем ближе значение емкости памяти к величине n). Для третьего варианта память не нужна вовсе. Тем не менее, даже в этом случае, если производить запись в память, эту запись считают информацией. Так что информация при втором представлении - это запись любых символов, поступивших от любых источников, в некоторой памяти (запись музыкальных произведений, компьютерных программ и пр.).
Нетрудно видеть, что рассмотренные представления отличаются друг от друга принципиально. В первом случае не известно, какой символ будет испущен источником в очередной момент времени, и именно обнаружение конкретного символа есть факт возникновения информации (подчеркнем особо, что согласно первому представлению обнаружение известного символа не есть получение информации).
Во втором случае все символы, записанные, например, на лазерном диске или в хромосомах клеток живых организмов, не возникают вновь, а уже существуют, они уже известны и, тем не менее, мы называем их тоже информацией.
Кроме того, информация по первому представлению, несмотря на то, что она является классическим (со времен Шеннона) вариантом определения и может быть измерена путем вычисления энтропии источника, является субъективным понятием. Действительно, третий вариант приведенного примера свидетельствует о том, что количество генерируемой информации зависит от того, известно ли стихотворение или не известно.
Как видим, ситуация с определением информации явно неудовлетворительная, так как мы имеем не только совершенно разные представления о ней, но и в дополнение к этому как будто бы субъективное определение в первом варианте, что недопустимо.
Чтобы исключить упомянутые недостатки, в понятие информации следовало бы включить две компоненты: энтропийную (случайную) и базовую (известную). На самом деле для определения информации обе эти составляющие необходимы, так как без первой нет новизны, а без второй невозможно адекватно интерпретировать первую. Посмотрим, как это можно сделать.
Пусть имеется источник информации, который генерирует десятичные цифры, вероятности появления которых не известны. Сколько информации мы получаем от него?
Прежде всего, обратим внимание на одно очень важное обстоятельство: мы уже ограничили внутреннюю структуру источника информации требованием генерации только десятичных цифр. Иначе говоря, мы уже обладаем некоторой базовой информацией о структуре источника. Полное отсутствие такой (начальной) информации означало бы попросту, что мы имеем дело не с конкретным источником информации, а со всей Вселенной, способной преподнести нам любой сюрприз.
Пусть первая цифра, которую мы получили от источника, равна единице. Пока ничего нельзя сказать о количестве полученной информации, потому что нам неизвестна вероятность возникновения цифры 1. Если бы наш источник информации создавал все цифры с равной вероятностью, то полученная информация составила бы
I = - SUM(P i * log P i) = - 10(0,1 * log 0,1) = 3,32 bit ,
где P i - вероятность появления цифр, log - логарифм по основанию "два" и суммирование ведется по всем возможным вариантам i.
Пусть вторая полученная от источника цифра равна двум. Мы вновь не можем ничего однозначного сказать ни о количестве полученной информации, ни о внутренней структуре источника.
Пусть третья полученная цифра равна "три", а четвертая - "четыре". Тогда возникает подозрение: не генерирует ли наш источник последовательно все цифры подряд, начиная с единицы? Ответ на этот вопрос и любые иные предположения может дать только эксперимент. Проведем его. Пусть следующие четыре цифры есть 7111, следующая четверка - 4481, затем 2251, потом 8931, еще 2586 и, наконец, 6252.
И вновь у нас могут возникнуть только предположения по поводу количества получаемой информации и внутренней структуры источника. Можно обнаружить, например, что наш источник не выдает цифру 0, и в связи с этим сделать определенные выводы по поводу его структуры. Однако слишком мало количество полученных цифр, чтобы делать какие то значимые выводы. Тогда "запускаем" источник вновь. Следующие тетрады цифр оказываются такими: 8334 5758 и это укрепляет нас в вере в то, что источник выдает нам не все цифры. Однако уже следующие тетрады опровергают наше мнение: 3990 и 0794. Уж что-то подозрительно мало нулей! Видимо, получаемые нами цифры не случайны, и поэтому нам не определить точно, сколько же информации мы получаем от источника.
Но продолжим эксперимент. Следующие тетрады таковы: 9553 0224 3385 8834 0661 0262 6884 8737 4327 8413 и так далее. Никаких закономерностей обнаружить не удается, и поэтому разумным предположением следует признать то, что наш источник действительно является генератором последовательности случайных цифр. Поэтому получаемая от него информация составляет примерно 3,32 бита на каждую цифру. Единственное, что надо было бы еще сделать, так это получить побольше цифр от источника и проверить, не существует ли каких-нибудь взаимных зависимостей между генерируемыми цифрами или длинных циклов.
И вот только мы облегченно вздохнули - с нашим источником все ясно! - как к нам подошел какой-то "умник", и сказал: "господа, обратите внимание на следующее обстоятельство. Если в полученной вами последовательности взять первую цифру, затем четвертую, седьмую, десятую и так далее через три цифры, то у вас получится, если иметь в виду запятую после первой цифры, не что иное, как квадратный корень из двух". Разумеется, мы тут же стали проверять последовательность, состоящую из второй, пятой, восьмой и т.д. цифр, а также из третьей, шестой, девятой и следующих. Оказалось, в первом случае получается основание натурального логарифма "е", а во втором случае - число "пи".
Конечно, это могло оказаться просто совпадением. Но при таком количестве полученных цифр это крайне маловероятно. Однако если "запустить" наш генератор для получения дальнейшей последовательности цифр, и при этом обнаружится, что мы и далее получаем разряды "корня из двух", а также чисел "е" и "пи", то можно будет говорить почти достоверно о том, что наш источник не выдает случайные цифры, а вычисляет разряды известных чисел. Поэтому получаемая от него информация равна нулю (согласно первому представлению об информации). Куда же она делась? Без "умника" мы получали информацию от источника, а после его замечания перестали ее получать - это ли не субъективность?
На самом деле информация никуда не делась. Просто теперь мы получаем ее меньше, чем раньше, как раз на величину вновь приобретенных знаний. Теперь мы почти все знаем об источнике, и получаем при генерации им очередных цифр незначительную дополнительную информацию, уточняющую наши знания о нем (это могут быть сведения о сбоях и т.п.).
Таким образом, можно думать, что информация ниоткуда не берется и никуда не исчезает вновь, если только включить в это понятие две составляющие: энтропийную (случайную) и структурную (известную, базовую). Далее можно говорить об информационном обмене между объектами, когда в зависимости от конкретного выбора объектов происходит количественное перераспределение этих составляющих. Например, слушая одного и того же лектора, студент и школьник объективно получают разное количество информации, но не столько потому, что их восприятие субъективно, сколько потому, что их базовые знания различны.
Итак, разницу между рассмотренными представлениями понятия "информация" можно сформулировать следующим образом.
Согласно первому представлению количество информации, поставляемой источником, равно его реальной энтропии, согласно второму - количеству его структурной информации. То есть в первом случае информация - это "устраненная" энтропия источника, во втором - это "упорядоченность" внутреннего состояния источника. Сумма этих составляющих определяет информацию, участвующую в информационном обмене между источником и приемником.
В частности, любую память можно представить себе как некий источник информации, который генерирует одно и то же информационное слово, соответствующее состоянию памяти. Энтропия такого источника равна нулю, и все генерируемые им символы, являются известными (избыточная информация по терминологии К. Шеннона).
Вернемся к вопросу о хранении во всех ячейках памяти одного и того же символа.
Один и тот же символ во всех ячейках памяти - это одно из возможных состояний памяти и в этом смысле комбинация, состоящая из всех нулей, ничем не отличается от других. Более того, конкретная информация извлекается из памяти не в связи с той или иной комбинацией нулей и единиц, а в связи с тем устройством, которое эти комбинации интерпретирует. (Вспомним, что одна и та же таблица из нулей и единиц, размещенная в памяти компьютера, может быть и рисунком, и музыкальной фразой и т.д. одновременно - все зависит от интерпретации). Поэтому и сплошные нули могут содержать в себе определенную информацию.
Пусть, например, есть память в 16 бит, хранящая 16 нулей. С помощью этой информации дежурный по станции может передать своему сменщику 16 сообщений. Например, если первый разряд памяти находится в "нуле", то вагон с углем надо поставить на седьмой путь (если бы он был в "единице", - то на девятый) и т.д. Сменщик, обнаружив в памяти все "нули", не придет в отчаяние: он будет точно знать, что вагон с углем надо поставить на седьмой путь и т.д. При передаче сообщений, таким образом, важны не конкретные переданные символы, которые в частном случае могут быть только нулями, а возможность их изменения, которая была у передающей стороны. Если говорить более точно, главным при передаче сообщений является неопределенность обнаружения тех или иных символов принимающей стороной, а также наличие договоренностей (базовой информации), необходимой для интерпретации полученных символов. [Наличие базовой информации абсолютно необходимо. Иначе любые сочетания нулей и единиц, записанные, например, в памяти компьютера, превращаются в бессмысленность. Так происходит, например, когда теряется адрес команд.] Собственно, это давно известный факт: информация - это, согласно первому определению, устраненная неопределенность. И это становится особенно прозрачным в случае передачи информации символами, которые содержат только нули.
Итак, мы можем рассматривать информацию, содержащуюся в некоторой памяти, как одно из возможных информационных слов, сгенерированных некоторым источником, и записанное в память. Тогда считывание этого слова из памяти не дает новой информации и сама память, рассматриваемая теперь уже как новый источник, обладает нулевой энтропией (нам известна внутренняя структура памяти).
Однако можно также рассматривать самое информационное слово, хранящееся в памяти, как самостоятельный источник информационных символов. При таком подходе разные информационные слова, хранящиеся в памяти, уже не равноправны и не обязательно содержат одинаковое количество информации.
Пусть, например, есть последовательность шестидесяти четырех нулей подряд. Такая последовательность может быть "сжата", то есть записана с использованием меньшего числа бит без потери информации. В данном случае можно, например, договориться (базовая информация) о том, что количество нулей будет представлено двоично-десятичным кодом, следом за которым будет указан символ, имеющийся в последовательности. То есть 64 нуля подряд запишутся так: 011001000. Зная правила расшифровки, мы можем понять, что этими девятью битами записана последовательность нулей в 64 бита. Если же я предложу вам "сжать" другую комбинацию 64-х нулей и единиц, например, такую
то это окажется невозможным, потому что эта комбинация содержит максимальное количество информации (энтропия - беспорядочное расположение нулей и единиц этой комбинации - максимальна). Действительно, путем произвольной выборки из данной комбинации каждый раз не более 64-х разрядов, расположенных подряд, можно получить 3838 различных чисел , что является максимально возможным значением. [Из 64 разрядной комбинации, состоящей только из нулей, можно извлечь описанным способом ровно 64 разных числа. То есть такие числа, как, например, "0" и "00", считаем разными.] Попытайтесь отыскать еще хотя бы одну 64-разрядную комбинацию, которая имеет максимальную энтропию, то есть "порождает" 3838 различных чисел (комбинация должна иметь совершенно другую структуру, и не должна быть получена инверсией, отражением или сдвигом разрядов имеющейся комбинации). [Хочу предостеречь тех, кто попытается поручить поиски компьютеру, задав ему программу перебрать все комбинации. Такая процедура заняла бы у современного мощного компьютера не менее 500 миллиардов лет, то есть во много раз больше времени существования Вселенной.]
Для величины максимальной энтропии Е "n"-разрядного двоичного числа мне удалось найти удивительно красивую формулу:
Е = n^2 - nm +2^(m+1)-2,
где m целое и m = k max в неравенстве 2^k < n. (k целое)
А если бы вам удалось найти простой алгоритм поиска комбинаций, удовлетворяющих максимуму энтропии, то вы получили бы идеальный генератор случайной последовательности нулей и единиц. Ведь любой иной генератор случайных последовательностей случайно может сгенерировать "неслучайную" последовательность (то есть такую последовательность, в которой нет максимального беспорядка расположения нулей и единиц). Именно последнее замечание говорит о том, что, по-видимому, такого алгоритма не существует. Иначе говоря, у нас нет возможности заглянуть "в лицо" случайности.