Что такое математика?
Это гаечный ключ. Инструмент, с помощью которого легко можно сделать то, что потребовало множество усилий и времени, если бы вы решили, например, закрутить гайку вручную.
В зависимости от назначения гаечные ключи бывают разными. Есть простые, есть громоздкие. Есть и такие, которые существуют только в воображении теоретика. Откручивающие или закручивающие, скажем, одиннадцатимерную гайку.
В любом случае, чтобы гаечный ключ появился и выполнял какую-нибудь полезную (пускай, воображаемую) функцию, необходимо интеллектуальное усилие. Нужно думать.
Устройствами, изобретение которых было бы невозможно без математики, мы пользуемся ежедневно. Сложные математические расчёты позволяют запускать космические корабли, придумывать новые лекарства, выращивать большие урожаи, автоматизировать и оптимизировать массовое производство бессчётного числа товаров, удовлетворяющих нашим растущим аппетитам.
Несмотря на это, многие люди не спешат приобщиться к математическим знаниям. Увы, наблюдаемый уровень практических умений в этой области редко превышает стандартные школьные навыки. Скромность познаний большинства людей подталкивает сравнить их со своеобразными «математическими нищими».
В информационном обществе получение и переработка значительных объёмов информации – не фактор успеха, а условие выживания. Недостаточно барахтаться в информационном водовороте – нужно уметь плавать. Это означает владение, хотя бы в минимальной степени, математическим инструментом.
Полагаю, роль прикладной математики в жизни массового человека будет возрастать. Речь не о науке. Имеются в виду вполне прозаичные дела. Постройка дома, ведение бизнеса, забота о собственном здоровье – любая творческая работа потребует изучения геометрии, логарифмического дифференцирования, теории вероятностей.
Производство всё более мощных компьютеров в данном случае мало облегчает жизнь. Не следует путать интеллектуальную работу с вычислениями. Решения останутся человеку. Т.е. придётся выделять главное, сравнивать, обобщать и делать выводы. Подспорьем станет не логика и не «здравый смысл», а математика.
Торжество информационного мира хорошо иллюстрируется положениями математической теории информации. Это именно научная теория, потому что предлагает внятное и глубокое объяснение происходящих процессов. Кроме того, следствия математической теории информации могут быть подвергнуты строгой проверке.
Почти каждый житель планеты слышал о смартфонах и Стиве Джобсе, но не имеет никакого представления о Джоне фон Неймане и Клоде Шенноне. Между тем, благодаря во многом этим учёным появились компьютеры, айфоны, айпады. Сначала потрудились математики, потом явились технологии.
Так было и прежде. В 1833 году (за 7 лет до создания аппарата Морзе) физик и инженер Вильгельм Вебер (Wilhelm Weber) сконструировал первый в Германии электромагнитный телеграф – устройство для передачи информации. Излишне говорить, насколько прорывной была эта технология в XIX веке.
Однако Вебер не добился бы успеха, если не сотрудничал с гениальным учёным Иоганном Гауссом (Johann Gauss). Его математические работы оценивались и тогда, и сейчас чрезвычайно высоко. Гаусса назвали Mathematicorum Princeps, «Принцем математики»1.
Математические теории и практика информационных технологий связаны неразрывно. Математика помогает прояснить сущность информации и позволяет регулировать информационный обмен. Технические устройства предоставляют вычислительные мощности для математических расчётов.
Желающим преуспеть в наши дни следует оставить навсегда пренебрежительное отношение к математике. Отказаться от сладкого бремени математического невежества. Знанием таблицы умножения и теоремы Пифагора отделаться, увы, не удастся. Придётся вникнуть, скажем, в комплексные числа и теорию хаоса.
В информационном обществе мало знать, что гаечные ключи существуют и их где-то можно достать. Надо представлять, как они выглядят и как именно применяются.
Дерзайте, и, возможно, именно вам суждено преобразиться, став новыми «математическими принцами».
Учёные любят парадоксы. Это не игра на публику, а способ решить актуальную научную проблему. Не все научные парадоксы разгаданы, но в тех случаях, когда это удаётся, человечество делает ещё один шаг по пути познания.
В 1867 году физик и математик Джеймс Максвелл (James Maxwell) предложил знаменитый мысленный эксперимент с «демоном».
Допустим, резервуар наполнен газом, молекулы которого друг с другом не взаимодействуют. Тогда, согласно Второму началу термодинамики, следует ожидать, что более горячие молекулы со временем мигрируют в менее нагретую часть резервуара, и установится тепловое равновесие.
Однако, по мысли Максвелла, если в резервуаре окажется некий хитрый механизм или таинственное существо (тот самый демон), то всё пойдёт не так. Более того: случится нечто противоположное. Демон (исключительно из присущего ему от рождения вредного характера) начнёт сортировать пролетающие мимо молекулы. Горячие отправит к таким же горячим, а холодные – к холодным. В результате одна половина резервуара со временем будет нагреваться, а другая – охлаждаться. Очевидно, Второе начало термодинамики (фундаментальный закон Природы, как-никак) нарушается22.
Что хотел показать Максвелл этим парадоксом? Он привлёк внимание к вероятностной природе теплового обмена. Никакого демона, конечно, нет, зато есть вероятность того, что горячие молекулы соберутся в одной половине резервуара, а холодные – в другой. Расчёты показывают, что она ничтожна мала, но не является нулевой. Раз так – значит, вредный демон может существовать и нарушать законы мироздания.
Парадокс потребовал значительного интеллектуального напряжения. Лишь спустя 62 года он был успешно объяснен физиком Лео Силардом (Leo Szilard). Ключ к объяснению состоит в том, что демон рассматривается не как часть резервуара с газом, а как часть системы «резервуар – внешняя среда». При этом, чтобы выполнять свою работу, он должен что-то «кушать». Т.е. получать энергию из внешней среды. Тогда, увеличивая температуру внутри резервуара, демон уменьшает её за его пределами. Таким образом, действие Второго начала термодинамики сохраняется30.
«Демон Максвелла» обнажил ограниченность научных знаний. Гипотетический эксперимент показал, что значение информационного обмена в законах Природы следует переосмыслить.
Как вообще возможен демон Максвелла? Откуда берётся, пускай, бесконечно малая вероятность самопроизвольного (без внешнего подвода энергии) нагревания газа в резервуаре?
Совершенно не случайно для демонстрации парадокса Максвеллом был выбран образ демона. Демон – мыслящее существо. Или, как сказали бы мы сейчас, существо информационное.
Чтобы делать свою работу правильно, демон должен обладать информацией. Т.е. уметь определять, какие молекулы горячие, а какие – холодные. Молекул в газе много, и работы у демона много. Каждая операция сортировки, каждое вмешательство демона – новая порция информации для него. Когда работа демона будет окончена, температура в резервуаре станет максимально высокой, а сам он – переполнен максимальным количеством информации. Следовательно, между энергией и информацией есть какая-то связь.
Именно это имел в виду Максвелл, когда воображал своего демона. Мера информации связана с энергетическим обменом. Чем больше информации, тем больше энергии. И наоборот. Чтобы описать систему с высокой температурой (т.е. там, где молекулы движутся очень быстро), нужно создать много информации. Описание системы, содержащей мало энергии, требует минимального количества информации. В любом случае получается, что информация – это такая же фундаментальная сущность, как и энергия.
Максвелл был очень продуктивным учёным. Сегодня он больше известен своими фундаментальными работами по классической электродинамике. На разработку теории информации, где он мог достичь не меньших высот, вероятно, просто не хватило времени. Однако вывод о глубокой взаимосвязи информации и энергии – первый важный шаг в понимании истинной природы информации – не был забыт.
Через девять лет после «демона Максвелла» мир побеспокоил «демон Лошмидта». Случилось это при следующих обстоятельствах.
Выдающийся учёный, профессор математики Людвиг Больцман (Ludwig Boltzmann) в 1872 году опубликовал свою знаменитую H-теорему. Её суть сводилась к тому, что в любой замкнутой системе со временем энтропия (неупорядоченность) возрастает и достигает максимума в состоянии равновесия. Строго говоря, теорема относилась к термодинамическим системам, т.е. описывала поведение материи и энергии на макро-уровне (например, объём любого газа или жидкости). Взаимодействие между элементами системы на микро-уровне (между атомами и молекулами газа или жидкости) не учитывалось. Это допущение было обозначено как гипотеза молекулярного хаоса2. Такое же предположение сделал Максвелл, когда придумывал своего демона.
Больцман обоснованно полагал, что вероятность того, что термодинамическая система будет вести себя так, как будто в неё вселился демон Максвелла, крайне мала. Поэтому его H-теорема вполне могла претендовать на некий универсальный закон Природы – закон возрастания энтропии3. Позже была предложена формула для этого закона:
S = k × logP
(здесь S – энтропия системы, k – постоянная Больцмана, P – вероятность термодинамического состояния системы).
Публикация вызвала бурные споры в научном сообществе. Физик Иоганн Лошмидт (Johann Loschmidt) в 1876 году заметил: что же получается – на макро-уровне одни законы Природы, а на микро-уровне – другие? Пренебрегать взаимодействием между частицами системы нельзя! Процессы движения материи и энергии должны быть одинаковы на любом уровне наблюдения, и, что ещё важнее, они должны быть обратимыми23.
В термодинамической системе, описанной Больцманом, молекулы, сталкиваясь и передавая друг другу энергию, могут это делать так, что их неупорядоченность будет убывать. Т.е. вместо того, чтобы равномерно распределиться в полном беспорядке, они возьмут и выстроятся, например, в форме конуса. Почему? Потому что могут. Потому что существует, опять-таки ничтожно малая вероятность такого развития событий. И тогда «универсальный» закон возрастания энтропии будет нарушен. Гипотетическое существо, которое могло бы учинить сие безобразие, назвали «демоном Лошмидта».
Парадоксы множились, а удовлетворительного их объяснения не находилось. Больцман попросту отмахнулся от критики. Ему приходилось отражать атаки и на других научных фронтах.
Великий французский математик Жюль Анри Пуанкаре (Jules Henri Poincare) в 1890 году сформулировал теорему о возвращении. Одним из её следствий был вывод о том, что в закрытой системе через очень большой промежуток времени молекулы газа, находившиеся вначале в упорядоченном состоянии, а потом (согласно Второму началу термодинамики) – в хаотическом состоянии, в итоге снова выстроятся в упорядоченную структуру.
Другой великий математик Эрнст Цермело (Ernst Zermelo), опираясь на эту теорему, предположил, что энтропия в замкнутой системе подчинена периодическому закону33. В таком случае Второе начало термодинамики – универсальное правило для всего и вся, в т.ч. и для Вселенной. Получалось, что Клаузиус был прав: нас всех неминуемо ждёт глобальная «тепловая смерть».
Людвигу Больцману крайне не нравилась идея монотонного дрейфа к всеобщему термодинамическому армагеддону. Но, с другой стороны, сам он был автором «универсального» закона возрастания энтропии. «Демон Лошмидта», безусловно, тревожил его.
Учёный выдвинул альтернативную концепцию. Он, как и все в то время, разделял мнение, что обратимость природных процессов – непреложный закон (на что указал Лошмидт, критикуя его H-теорему). Но, если большинство учёных считали, что вся Вселенная катится к естественному и закономерному концу, то Больцман предположил, что конец уже наступил.
Вселенная мертва: она находится в состоянии термодинамического равновесия. В текущем состоянии, утверждал Больцман, система мироздания обладает в среднем очень высоким уровнем энтропии. А мелкие островки упорядоченности (например, планета «Земля») – просто-напросто случайность. Жизнь – незначительная в масштабе Вселенной флуктуация, которая компенсируется где-то в другом месте. Где энтропия выше среднего. У нас – Порядок и «нормальное» течение времени. А там – наоборот: Хаос и стрела времени, обращённая вспять.
Если такая картина миропорядка покажется вам чересчур… экстравагантной, то надо сказать, что примерно то же представление о Вселенной имели, например, Макс Планк и Альберт Эйнштейн. Почему? Потому что концепция многое объясняла.
Космологическая теория Больцмана преследовала важную цель. Не опровергая, ставшее почти священным, Второе начало термодинамики, учесть неудобные статистические вероятности, неизбежно возникающие в такой сложной динамической системе, как Вселенная.
Замысловатая концепция Больцмана не могла не породить очередной парадокс.
В XX веке большинство физиков пришло к мнению, что пространство Вселенной евклидово, т.е. имеет нулевую кривизну. Переводя на человеческий язык, это означает, что расширение Вселенной будет продолжаться бесконечно, постоянно при этом замедляясь. Короче говоря, Вселенная будет существовать вечно.
«Вечно» – это как-то очень долго, не так ли? За этот период времени, согласно интерпретации Больцмана, может произойти бесконечное число флуктуаций. Включая разумную жизнь. Такой объект полуиронично назвали «больцмановский мозг» (boltzmann brain) 12.
Если мы с вами решим прогуляться по вечной Вселенной, то постоянно будем натыкаться на плавающие повсюду «больцмановские мозги», поглядывающие на нас свысока. Ведь мы – продукт нудной эволюции и единственные в своём роде (этакие «белые вороны»), а они – результат бессчетного числа случайностей (по их мнению, закономерностей) и их много. Уверен, «супер-мозги» непременно устроили бы нам серьёзную взбучку.
Сегодня благодаря достижениям квантовой физики и солидному багажу научных фактов противоречивые концепции прошлого, казалось бы, забыты. Однако для становления научного понимания информации идеи Людвига Больцмана имели огромное значение.
Формула Больцмана, абсолютно верная для описания поведения молекул газа или жидкости, но всё же не абсолютный закон всего – это черновой набросок формулы вычисления информации. Основная мысль здесь: связать степень упорядоченности системы со статистической вероятностью обнаружения её элементов. Идею подхватили другие учёные: Джозайя Гиббс (1902 год) и Макс Планк (1925 год), опубликовавшие работы, в которых догадка Больцмана обрела строгую математическую форму8,18.
Для того, чтобы сделать логический переход – от термодинамики к информационному обмену – надо было вообразить, что частица является не только носителем энергии, но и информации. Такой шаг был сделан создателями математической теории информации полвека спустя.
«Демон Лошмидта», спор Больцмана и Цермело, заострил внимание других математиков на проблеме статистической меры информации. Заставил размышлять – при каких условиях сохраняется смысл информации, а в каких – наступает информационный хаос?
Эмиль Борель (Emile Borel) – блестящий учёный, основные труды которого посвящены проблеме меры в математике и теории вероятностей. Он решил разобраться, какие факты, с т. зр. математики, можно считать возможными и какие – иллюзорными. Его интерес был не только академическим, но и вполне практическим (Борель занимался политикой). Когда, например, следует учитывать мнение людей по тому или иному вопросу, а когда этим можно пренебречь.
Борель полагал, что существует настолько маловероятные события, что со всей категоричностью их можно назвать невозможными. В качестве одного из примеров таких событий он в 1913 году предложил т.н. «дактилографическое чудо»10.
Допустим, обезьяна оказалась за пишущей машинкой. Она начинает в беспорядке ударять по клавишам устройства, и на белом листе бумаги появляется некая последовательность знаков. Возможно ли, что когда-нибудь обезьяна напечатает что-нибудь стоящее? Научное или литературное произведение? Например, текст трагедии Уильяма Шекспира «Гамлет»?
Возможно. Хотя вероятность данного события чрезвычайно мала.
Пример с борелевской обезьяной растиражирован во многих художественных и научных публикациях, и я не буду утомлять читателя собственными подсчётами. Сошлюсь на профессора Массачусетского технологического института Сета Ллойда (Seth Lloyd). В своей книге «Программирование Вселенной» (Programming the Universe, 2006 год) он рассказывает – чтобы «дактилографическое чудо» произошло, необходимо выполнение ряда условий. Во-первых, обезьян должно быть 1018 штук. Во-вторых, их нужно тщательно подготовить: скорость печатания должна быть не менее 10 букв в секунду. В-третьих, период деятельности трудолюбивых обезьян-машинисток должен составить чуть больше 30 миллиардов лет (напомню, что уточнённая к настоящему продолжительность существования Вселенной составляет около 13,5 миллиардов лет). Это без учёта времени, которое им следует выделить на заслуженное поедание бананов и сон. Но даже в случае успешной реализации перечисленных условий, всё, что смогут напечатать обезьяны (точнее говоря – только одна из всех), будут слова: «Гамлет. Акт I. Сцена 1».
Пример, приведённый Борелем, можно с легкостью интерпретировать неправильно. Не увидев истинной предпосылки, сделать поспешные выводы.
Кажется, что самоотверженный труд обезьян показывает нам, насколько сложна Вселенная, жизнь, человеческий разум, и чтобы создать такую сложность, нужна, как минимум, такая же сложная структура.
Отсюда два традиционных умозаключения:
1. Идеалистического характера: здесь потрудился Сверх-Разум (бог, зелёные человечки и т.д.).
2. Материалистического свойства: всё сущее – результат случайной флуктуации (космологическая концепция Больцмана).
Оба ответа не верны. Потому что ошибочна начальная предпосылка. Механизм создания Вселенной – не пишущая машинка. Он одновременно проще и сложнее. И более напоминает компьютер. Простое устройство, способное делать сложные вещи. А с чем работает компьютер? Он работает с информацией.
В таком случае «дактилографическое чудо» всего лишь демонстрирует неэффективный способ переработки информации.
Борель показал ничтожную вероятность некоторых событий в реальной жизни. Ту же мысль он пояснял, рассуждая о неограниченном информационном запасе в алфавитных разложениях. Любой алфавит – набор знаков – содержит потенциально огромное количество информации14. Ряды знаков, напечатанных обезьянами-машинистками, практически бесконечны. В груде бесполезных текстов (превышающих объём известной нам Вселенной) есть только крупица смысла. Ради этой капли организованной информации десятки миллиардов лет трудятся квинтиллион героических обезьян.
Можно ли облегчить их работу? Как быть с кипами бумажных листов, содержащих абракадабру вместо бессмертных строчек Шекспира? Как отделить полезное от бесполезного? Можно ли не эмпирически, не «на глазок», а математически описать меру информации, имеющей смысл?
Как видим, размышление о борелевской обезьяне вплотную подводит к законам информационного обмена. Ещё немного, и они были сформулированы.
История открытий в области теории информации удивительно напоминает эволюцию взглядов на происхождение человека. Как известно, сначала доминировала идеалистическая точка зрения, затем – материалистическое понимание. Применительно к динамике осмысления информации заметно, что вслед за блужданием в почти мистическом тумане («демоны» и «супер-мозги») наступил «естественно-научный» (борелевская обезьяна), а затем и строго научный этап4. Пришло время для прояснения объективных закономерностей, выраженных математическими формулами, и создания полезных устройств.
Замечательный инженер, прекрасно разбиравшийся в математике, Гарри Найквист (Harry Nyquist) в середине 20х гг. прошлого века опубликовал ряд специальных работ, посвященных проблемам телеграфной связи. Найквиста интересовало, каким образом можно быстро и точно передавать информацию.
Поскольку потоки информации в естественных (природных) условиях непрерывны, то хорошо бы их разделить на части – отдельные порции. Для этого надо выбрать определённую частоту, которая будет обозначать границы информационных порций. Найквист обнаружил: эта частота должна составлять не более половины частоты работы передающего и принимающего устройства. В противном случае информация может быть искажена или потеряна25,26. Данную величину впоследствии предложено назвать «частотой Найквиста» (Nyquist rate).
Ральф Хартли (Ralph Hartley), не менее талантливый инженер и более сильный математик, в 1928 году представил научную работу, где предложил формулу для количественной оценки информации20.
С первых строк статьи автор призвал очистить понятие информации от психологического содержания. Информация – физическая величина и точка.
Хартли указывал, что во время коммуникации каждый последующий выбор символа в цепочке делает сообщение более точным. Например, в предложении «Apples are red» первое слово исключает из нашего представления какие-либо другие фрукты («говорю о яблоках»), второе – заостряет внимание на свойствах данной категории фруктов («говорю о свойствах яблок»), третье – накладывает ограничение на мысль о других цветах и оттенках («говорю о красных яблоках»). Таким образом, чтобы высказывание обрело смысл, который мы хотим передать, надо сделать три последовательных шага. Взять первое слово, затем – второе и потом – третье. Если использовать только одно слово или расставить все слова в неправильном порядке, смысл исказится. Алгоритм нарушать нельзя.
Это общее рассуждение. Можно ли к этой логике применить математику? Хартли посчитал, что можно. Количество информации (мера Хартли) – это число последовательных шагов, которое нужно предпринять, чтобы сообщение обрело нужный смысл:
I = log2N
(здесь I – количество информации, N – количество всех возможных комбинаций).
Под «всеми возможными комбинациями» в приведённом выше примере понимается сочетание слов apples, are, red в любом порядке и в любом долевом количестве. Т.е. сообщение может быть таким: red are apples. Или: apples apples apples. Число возможных комбинаций – 27. И только одно из них обладает тем смыслом, который мы хотим передать. Напоминает творчество борелевских обезьян, не так ли?
Сыграем в игру. Она похожа на игру «да-нет» (вариант – «съедобное-несъедобное»), когда продвигаешься к ответу, отсекая лишние варианты.
У нас есть три слова (are, red, apples). Это заданная длина сообщения. Нам нужно найти фразу, имеющую смысл. Сделаем допущение: мы немного разбираемся в английском языке, и знаем, что сначала должно стоять подлежащее, затем – сказуемое, и замыкает фразу определение. И ещё одно допущение: фразы с повторяющимися словами не отражают нужный нам смысл.
Итак,
1. убрать варианты, где слова повторяются. Таких 21. Остаётся 6;
2. убрать варианты, где первое слово не apples. Таких 4. Остаётся 2;
3. убрать вариант, где второе слово не are. Остаётся один вариант.
Сравним с результатом вычислений по формуле Хартли. I = logN = log27, т.е. округленно 4,8 единиц информации. Или почти пять последовательных операций для преобразования информации из абракадабры в имеющую смысл. Но в нашей игре «да-нет» нам для этого понадобилось всего три шага. Формула Хартли неточна?
Да, это так. Но это не значит, что идея ошибочна. Напомню, что в примере со словами мы сделали несколько допущений, облегчив себе поиск истины.
Возьмём числа (с ними всегда проще и понятнее, чем с буквами и словами) и снова подвергнем формулу проверке.
Допустим, некто загадал число от 1 до 100. Я должен его угадать, использовав минимальное количество вопросов. Согласно формуле Хартли: I = logN = log100, т.е. примерно 6,6 шагов-вопросов мне понадобится. Округлим до 7.
Итак,
1. число больше 50? Ответ: нет.
2. число больше 25? Ответ: нет.
3. число больше 12? Ответ: нет.
4. число больше 6? Ответ: нет.
5. число больше 3? Ответ: да.
6. число больше 5? Ответ: нет.
7. это число 5? Ответ: нет. Значит, загаданное число: 4.
Теоретическое вычисление и практический результат совпали. Формула Хартли доказала свою состоятельность.
Надеюсь, читатель обратил внимание на то, что формула Хартли удивительно напоминает формулу Больцмана для определения величины энтропии термодинамической системы. Это не случайно.
Смысл меры Хартли состоит в том, что она отражает затраты, которые необходимо предпринять, чтобы перевести информацию из неупорядоченной в упорядоченную. И не просто затраты, а затраты минимальные.
И в примере с яблоками, и в примере с числами мы могли бы просто перебирать варианты. В первом случае нам понадобилось бы 27, во втором – 100 шагов (представьте, сколько бы сил и времени занял поиск текста «Гамлета» в творческой куче, которую сотворили обезьяны-машинистки!).
Мы поступили по-другому. Оказалось, что для любой информации есть короткий путь измерения её смысла или ценности, какой бы объёмной они ни была. У всякой информации есть цена. Формула Хартли вычисляет её.
По сути, теоретические работы Найквиста и Хартли – начала информационной теории. Информация, «очищенная от психологических факторов», становится физическим явлением, для которого впервые предложен математический способ измерения.
Широкой публике гениальный математик Алан Тьюринг (Alan Turing) известен, вероятно, как человек, разгадавший шифр «Энигмы»21. Благодаря чему цивилизованный мир победил нацистов. Если даже это и правда, то не вся. Главная заслуга Алана Тьюринга перед человечеством состоит в другом. В своих работах он описал то, что сегодня мы называем компьютером.
В год, когда Ральф Хартли предложил свою формулу для вычисления меры информации, великий математик Давид Гильберт (David Hilbert) сформулировал проблему разрешения (Entscheidungsproblem). Её суть сводится к тому, что у любой задачи (которую можно выразить с помощью букв или цифр) должен существовать алгоритм (порядок шагов для её решения). Если алгоритма нет (никто не может придумать), то задача не является разрешимой. Однако это не означает, что задача не может быть решена в принципе11.
Поясним сказанное на примере. Возьмём два числа: 25 и 100. Каков их наибольший общий делитель? Пойдём не интуитивно, а строго математически. От большего числа будем отнимать меньшее. В результате трёх последовательных вычитаний получим число, которое соответствует наименьшему числу, выбранному изначально (25). Тогда можно сказать, что наибольший общий делитель для 100 и 25 есть число 25. Или: 25 – наибольшая общая мера выбранных чисел. Принято говорить, что 100 и 25 – соизмеримые величины.
Приведённый порядок вычисления – известный ещё со времен Евклида (Euclid) алгоритм для поиска наибольшего общего делителя. Но что, если существуют задачи, для которых алгоритм указать нельзя?
Вообразим два других числа. Очень больших. Длиною в миллиарды миллиардов знаков. Попробуем найти их наибольший общий делитель. (Представляю, как вы чертыхаетесь).
Ну, хорошо – предоставим это компьютеру. Пусть попотеет. Сможет ли он выполнить порученную работу? Допустим, что сможет. Возникает вопрос: сколько времени это займёт? Ответ: неизвестно.
Это так называемая «проблема остановки». Мы не знаем, как долго будет работать вычислитель (человек или машина) над решением некоторых (математически сложных) проблем. Другими словами, мы не можем для них предложить алгоритм – порядок шагов, которые нужно предпринять, чтобы получить точный ответ.
В 1931 году математик Курт Гёдель (Kurt Gödel) доказал, что во всякой сложной (с т. зр. логики и математики) умозрительной системе есть недоказуемые утверждения9. Т.е. они содержат такие величины, для которых невозможно придумать алгоритм. Это невычислимые величины.
При этом теория может быть верной. И величину можно вычислить в принципе. Но указать алгоритм вычисления нельзя. Способ Евклида для очень больших чисел работает плохо. Не исключено, что результата придётся ждать вечность.
Все эти математические ухищрения кажутся играми разума. Однако, критерий вычислимости (или, как говорят математики, алгоритмической неразрешимости) крайне важен в обычной жизни. Его существование позволяет метеорологам сохранять лицо и надёжно защищать персональные данные7.
Алан Тьюринг много размышлял над точным определением понятия «алгоритм». Ведь на проблемы, поставленные Гильбертом и Гёделем, можно посмотреть под другим углом6. Что такое вообще «алгоритм»? Можно ли его точно описать? И какие задачи можно решить с его помощью?
В 1936 году Тьюринг в работе «О вычислимых величинах применительно к проблеме разрешения» (On Computable Numbers, with an Application to the Entscheidungsproblem) описал универсальное вычислительное устройство (universal computing machine) 31. Подробная схема работы этого гипотетического устройства есть во многих книгах по математике13. Я расскажу о сути.
Допустим, вы располагаете какой-либо информацией. Её можно представить в форме последовательности знаков (букв или цифр). Вам нужно преобразовать информацию – что-то вычислить или сделать так, чтобы эту информацию было удобно передать. Тьюринг показал, что, получив от нас алгоритм (или, выражаясь современным языком, «компьютерную программу»), его устройство сделает эту работу.
Например, укажем универсальному вычислительному устройству, как переводить буквы английского алфавита в числа в двоичной системе счисления (напишем команды «Переведи a в 110 0001», «Переведи p в 111 0000» и т.д.). Т.е. дадим машине алгоритм. Если на входе у нас слово apples, то на выходе устройство выдаст: 110 0001_111 0000_111 0000_110 1100_110 0101_111 0011.
Теоретически существует алгоритм для любой задачи, какую только мы способны вообразить. Перемножить 100-значные числа. Предсказать завтрашнюю погоду. Выиграть в рулетку.
Однако «способны» не значит «можем».
То, что может, и есть «машина Тьюринга» (Turing machine). Абстрактная математическая модель, описывающая, тем не менее, реальный способ отделить вычислимость от невычислимости.
Позже был сформулирован тезис (принцип) Тьюринга-Чёрча (Church-Turing thesis or principle): всякая вычислимая функция вычислима машиной Тьюринга. Иначе говоря: если для определенной задачи можно создать алгоритм, по которому машина Тьюринга будет работать, то задача выполнима17.
Последствия конструирования схемы универсального компьютера были огромны. Математики получили точное представление об алгоритме как об универсальном способе преобразования информации. Инженеры могли перейти к созданию практических устройств, способных решить любую вычислительную задачу. А машины, пользуясь единым языком, могли бы не только обрабатывать данные, но и «общаться» между собой. Т.е. обмениваться информацией.
Джон фон Нейман (John von Neumann) – один из крупнейших математиков XX века. К его достижениям, например, принадлежит строгая математическая формулировка принципа неопределённости – базового тезиса квантовой теории. Формулировки Вернера Гейзенберга (Werner Heisenberg) и Эрвина Шрёдингера (Erwin Schrödinger) – гуру квантовой механики – стали частными случаями интерпретации фон Неймана24.
Если Тьюринг подробно описал, что такое компьютер, то фон Нейман придумал, как именно он должен работать. Он предложил законы, по которым должно существовать современное вычислительное устройство.
В 1946 году в небольшой брошюре «Предварительное рассмотрение логической конструкции электронного вычислительного устройства» (Preliminary Discussion of the Logical Design of an Electronic Computing Instrument), написанной совместно Артуром Бёрксом (Arthur Burks), Германом Голдстайном (Herman Goldstine) и Джоном фон Нейманом, были изложены принципы компьютерной архитектуры (или, как говорили тогда, машинной организации) 15:
1. «Языком» компьютера является двоичная система счисления (0 и 1).
2. Компьютер работает по программе – алгоритму указаний или команд.
3. И команды, и данные хранятся на одних и тех же элементах машины – т.е. информация, записанная в двоичном коде, может использоваться и в качестве указаний, и в качестве памяти для компьютера.
4. Наличие «внутренней классификации» – информация (команды и данные) разбита на единицы, каждая из которых пронумерована и доступна для извлечения в любой момент времени.
5. Команды исполняются строго последовательно – нельзя перейти к следующей команде, пока не выполнена предыдущая.
6. Алгоритм необязательно должен быть линейным – в зависимости от входных данных последовательность выполнения команд может меняться.
Фактически первый электронный цифровой компьютер был сконструирован за несколько месяцев до выхода упомянутой брошюры – в конце 1945 года. Его назвали «ENIAC» (Electronic Numerical Integrator and Computer).
В 1950 году при непосредственном участии фон Неймана группа метеорологов произвела на ENIAC первый успешный численный прогноз погоды. Всего на сутки, и вычисления заняли почти 24 часа, так что практическая польза от такого прогноза оказалась невелика16. Но лиха беда начало.
Летом 1951 году было презентовано новое устройство – IAS-машина или «машина фон Неймана» (учёный возглавлял проект). Размер памяти этого компьютера вмещал 1024 слова. Однако, «машина фон Неймана» работала в 240 раз быстрее, чем ENIAC. Эволюция современных компьютеров началась.
Архитектуру фон Неймана ещё называют «принстонской», поскольку над IAS-машиной учёный и его коллеги трудились в Институте перспективных исследований, расположенном в Принстоне.
Другая группа исследователей и конструкторов под руководством инженера Говарда Эйкена (Howard Aiken) работала в Гарвардском университете. Принципы организации вычислительных устройств, предложенные Эйкеном, называют «гарвардской архитектурой».
Гарвардская архитектура отличается от архитектуры фон Неймана тем, что данные и команды хранятся на разных элементах компьютера. С одной стороны, это увеличивает скорость обработки информации. С другой стороны, требуется больше деталей – резко увеличивается себестоимость устройства.
Поэтому в последующие годы возобладала более простая принстонская архитектура. Большинство современных компьютеров – потомки ENIAC, сконструированного по заветам Джона фон Неймана.
С использованием транзисторов в качестве переключателей вместо электронных ламп и электромеханических реле производство компьютеров значительно удешевилось. Начиная с 1960х гг. электронные вычислительные устройства удостоились наивысшей оценки, какую только способны дать люди вещам. Они стали массовым товаром.
Вернёмся немного назад во времени. За 20 лет до того, как Тьюринг придумал концепцию устройства, перерабатывающего информацию, и за 30 лет до того, как фон Нейман обосновал принципы работы этого устройства, в небольшом городке на берегу живописного озера Мичиган родился Клод Элвуд Шеннон (Claude Elwood Shannon).
Застенчивый и любознательный паренёк с детства любил возиться с техникой. Собирал авиамодели и модели радиоуправляемых лодок, чинил радиостанции для жителей провинциального Гейлорда.
Его совсем не занимали вопросы политики или религии. Он был одиночкой, не слишком разговорчивым даже с коллегами по научной работе. По словам жены, Шеннон «спал, когда хотел спать, и часто проводил часы за кухонным столом, обдумывая идеи». Вместе с тем, он постоянно что-то придумывал и изобретал5.
Одним словом, Шеннон был мыслителем-универсалом, виртуозно владевшим математической теорией и применявшим её для решения разнообразных практических вопросов. Причём внешняя оценка его не волновала. Ему просто нравилось думать.
С 1940 по 1941 год Клод Шеннон работал в принстонском Институте перспективных исследований (Institute for Advanced Study, сокр. IAS), где встречался и беседовал с Джоном фон Нейманом. Именно он, к тому времени уже маститый профессор, посоветовал молодому аспиранту рассмотреть понятие энтропии применительно к информации.
В те годы кафедру Массачусетского технологического института (Massachusetts Institute of Technology, сокр. MIT) возглавлял Норберт Винер, уже снискавший в научном мире авторитет благодаря работам по теории вероятностей, статистике, теории чисел и др. Винер сформулировал понятие о новой науке, рассматривающий информационный обмен в сложных системах, – кибернетике. В 1941 году Шеннон защитил докторскую диссертацию в MIT и позже, конечно, внимательно следил за работами Винера, где рассматривались вопросы движения информации32.
В 1943 в США прилетел Алан Тьюринг, чтобы обменяться с союзниками наработками в деле расшифровки немецких военных кодов. Он встретился с Шенноном и, в частности, показал свою работу, посвященную универсальной машине.
Спустя три года впервые в литературе появляется термин «bit» (сокращение от англ. binary digit) как единица измерения информации – в научный обиход его ввёл математик Джон Тьюки (John Tukey).
Вот краткая хронология событий, предшествовавших появлению в 1948 году знаменитой статьи Клода Шеннона «Математическая теория связи» (A Mathematical Theory of Communication) 27,29. Усилия многих учёных (в основном – математиков), иногда действовавших совместно, иногда конкурировавших друг с другом, привели к рождению того, что мы называем теорией информации. Без всякого преувеличения этот факт можно сравнить с появлением теории эволюции Дарвина и общей теорией относительности Эйнштейна.
До этой работы об информационном обмене рассуждали исключительно с утилитарных позиций. Считалось, например, что передача информации полностью зависит от свойств канала коммуникации. Если канал слишком «шумный», то передать сообщение невозможно. Поэтому надо работать над «информационной проводимостью» линий передачи, учитывая характеристики металлических сплавов и т. д. О свойствах собственно информации почти никто не задумывался.
Шеннон взялся за решение проблемы, сначала рассмотрев общие вопросы. Он ввёл понятие «информационной энтропии», предложив формулу:
H = – (p1log2 p1 + p2log2 p2 + … + pnlog2 pn)
(где H – информационная энтропия, p – вероятность того, что именно данный знак или последовательность знаков будет выбрана, n – количество всех возможных выборов).
Математик высказал гениальную догадку, что информационная энтропия играет центральную роль в теории информации как мера (критерий) информации, выбора и неопределенности.
Формула Шеннона похожа на формулу Хартли, не так ли? Так и есть. Преемственность идей не вызывает никаких сомнений.
Но что означает «минус» в формуле Шеннона? В формуле Больцмана и в формуле Хартли никакого «—» нет. Откуда он взялся?
Простое математическое объяснение заключается в том, что p (вероятность) всегда меньше единицы. Значит, логарифм (в какую степень нужно возвести 2, чтобы получилось p) всегда будет отрицательным числом. Для удобства расчётов информационной энтропии на практике Шеннон ввёл «‒», чтобы полученная формально отрицательная величина превратилась в положительную. Строго говоря, по формуле Шеннона вычисляется модуль информационной энтропии.
Допустим, мы располагаем всего двумя различающимися знаками (a и b) и хотим составить сообщение длиною в десять знаков. Если мы используем в сообщении один знак (пусть это будет b), а другой (a) не используем, то вероятность встретить первый знак – 100% или 1,0, а второй знак – 0% или 0,0. Тогда сообщение, включающее знак a, не существует (количество информации и информационная энтропия для сообщения со знаком a равны нулю). Есть только ряд: bbbbbbbbbb.
Мы решили разнообразить однородную последовательность: появляется знак a. Вероятность встретить его в нашем сообщении увеличивается. Скажем, возьмём семь b и три a: вероятность встретить a составит 0,3. Одновременно увеличится количество информации: с помощью двух знаков, очевидно, можно передать больше смысла. И также увеличится энтропия сообщения: количество комбинаций из a и b будет нарастать. В какой-то момент их станет максимальное число. Когда это произойдёт? Тогда, когда мы используем пять a и пять b. Т.е. при условии, что вероятность встретить a составит 0,5.
Действительно, располагая равным количеством разных знаков и комбинируя их в любом порядке, мы можем получить наибольший набор последовательностей. Неупорядоченность текста максимальна (представьте обезьян-машинисток на пике творческого аврала).
Пойдём дальше. Начнём использовать знак a чаще, чем b. Вероятность возрастает, число a увеличивается, но энтропия уменьшается. Почему? Потому что, располагая, например, семью a и тремя b, мы можем составить меньше комбинаций – следовательно, меньше смысла, зато он становится более определенным. Информация упорядочивается.
Наконец, когда текст состоит из одних a (вероятность встретить её в сообщении равна 1,0), смысл может только один – никаких кривотолков и отклонений. «aaaaaaaaaa» и всё тут. Информационная энтропия снова равна нулю. Но количество информации для сообщения со знаком a максимально (10 из 10 в последовательности).
Клод Шеннон предложил считать информационную энтропию и собственно информацию в битах.
Может показаться, что использование бинарного кода – ненужная сложность. Напротив, это очень удобно.
Когда, например, говорят, что общий информационный объём (абсолютная энтропия) сообщения равен 10 битам, это означает, что существует 1024 возможных комбинаций символов, из которых может быть составлено сообщение. Допустим, чтобы составить какое-либо сообщение, имеющее смысл, нам достаточно информации в количестве 4 бита (фактическая энтропия). Это значит, что всего есть 16 (24) комбинаций, необходимых для того, чтобы собеседники понимали друг друга. Все остальные комбинации символов – бесполезная белиберда.
Как вычислить эту белиберду? Шеннон нашёл простое решение: из абсолютной энтропии надо вычесть фактическую. Это и будет избыточностью (redundancy) данного сообщения. Таким образом, математик предложил объяснение буквенно-фонетической избыточности, которую мы обсудим в следующей главе.
Исследования Гарри Найквиста, обосновывающие порционную (дискретную) обработку информации, получили продолжение в работах Клода Шеннона и были обобщены им в теорему дискретизации (sampling theorem). Идее о том, что любую информацию из непрерывного потока можно превратить в дискретные (например, цифровые) сигналы, а потом – восстановить обратно, Шеннон придал строгую математическую форму28.
Процедура цифровой обработки сигналов (digital signal processing), ставшая в наши дни рутинной, целиком подчинена теореме дискретизации. А все системы связи конструируются с учётом положений теории информации.
Идеи Клода Шеннона послужили триггером для некоторых научных теорий, включая, например, теорию Колмогрова-Арнольда-Мозера или просто КАМ (Kolmogorov-Arnold-Moser (KAM) theory) – в чём честно признавался один из её авторов19.
Рядовой международный симпозиум, состоявшийся в 1985 году в Брайтоне и посвященный проблемам информационного обмена, не предвещал никаких сюрпризов. Инженеры, программисты, математики собрались обсудить текущие научные вопросы. Но деловой настрой развеялся, когда внезапно на форуме был замечен Клод Шеннон.
Преодолев неприязнь к публичным мероприятиям, создатель теории информации всё-таки появился в профессиональном сообществе. Симпозиум мигом преобразился в его бенефис. Вежливо, но настойчиво расталкивая друг друга, информационщки пробивались к скромной фигуре выдающегося математика. Чтобы взять автограф. Чтобы пообщаться и улыбнуться тому, кто открыл новый путь и сделал по нему первые шаги. Этот путь – научное познание информации.
Меньше, чем за сотню лет, был проделан путь, наполненный парадоксами и гениальными догадками. Венец пути – теория информации как «математическое доказательство» бытия информационного человека.
«Демон Максвелла»: информация – такая же фундаментальная величина, как и энергия.
H-теорема Больцмана: логарифмическая зависимость энтропии от вероятности обнаружения элемента системы.
«Дактилографическое чудо» Бореля: проблема различения полезной и бесполезной информации.
Частота Найквиста: предположение о соотношении полезной информации и шума в канале передачи.
Формула Хартли: мера информации – количество шагов, которые необходимо сделать, чтобы отразить минимальный смысл.
Машина Тьюринга: концепция вычислительного устройства, эффективно перерабатывающего любую информацию в соответствие с алгоритмом.
Архитектура фон Неймана: принципы работы вычислительного устройства, включая двоичный код как систему записи информации.
Математическая теория информации Шеннона: расчёт объёма информации и информационной энтропии, понятие избыточности языковых систем.
Хорошая теория порождает хорошие инструменты. Математическая теория информации выдержала проверку временем. По моему мнению, её прямыми и косвенными следствиями являются:
1. Мы сами и всё вокруг нас – информация.
Всякое сложное явление (природное, социальное) может быть рассмотрено как информационная система или как взаимодействие таких систем.
2. Информацию можно посчитать и организовать.
Всякое количество информации характеризуется степенью упорядоченности, которую можно вычислить.
3. Информацию можно сжать.
В любом объёме информации присутствует избыточность, устранение которой помогает выделить смысл. Чем больше смысла можно вместить в единицу объёма за единицу времени, тем выше скорость передачи информации.
4. Бытие информационных систем сопровождается рождением смысла.
Системообразующим фактором информационной системы является такая переработка информации, при которой она из неупорядоченной формы преобразуется в упорядоченную.
Фундаментальное значение математической теории информации может быть оспорено. Критики не готовы переосмыслить новое содержание термина «информация», которое следует из предложенного здесь математического объяснения. Нелегко отказаться от привычки думать по-старому. Как приучили школьные учителя, как вещают маститые эксперты и модные публицисты.
Ограниченное толкование информации может и должно быть преодолено. «Всё проходит, и это пройдёт».
Что такое современный мир с точки зрения теории информации? Это мир борелевских обезьян. Мир, в котором вычислительные устройства (компьютеры и люди) рождают не столько новые смыслы, сколько бессмысленные информационные объёмы.
Как перестать быть борелевскими обезьянами? Надо выбросить пишущие машинки и взяться за компьютеры. Но не за те машины, которыми пользуются сейчас, и чьи вычислительные возможности относительно скромны. А за устройства, организованные по принципам, описанным современной наукой. Например, квантовые компьютеры.
Что случится с обезьяной, пересевшей за такое устройство? С его помощью она создаст больше полезной информации и будет обмениваться ею с другими информационными существами. Возникнут предпосылки для качественной трансформации как окружающего мира, так её собственной природы.
Тогда, возможно, она перестанет быть обезьяной и станет кем-то другим.