Невозможно доказать, конечное или бесконечное число решений имеет каждое уравнение из семейства алгебраических уравнений: ответ варьирует случайным образом, и, следовательно, не может быть найден с помощью математического рассуждения
ГРЕГОРИ ДЖ.ЧЕЙТИН
ЧТО МОЖЕТ БЫТЬ бесспорнее того факта, что 2 плюс 2 равняется 4? Со времен древних греков математики считали, что более несомненной вещи, чем доказанная теорема, не сыскать. Действительно, математические утверждения, истинность которых может быть доказана, часто считались более надежным основанием для системы мышления, чем любой моральный или даже физический принцип. Немецкий философ и математик XVII в. Готфрид Вильгельм Лейбниц считал возможным создать «исчисление» рассуждений, которое когда-нибудь позволит улаживать все споры с помощью слов: «Давайте вычислим, господа!». К началу нашего столетия прогресс в разработке символической логики дал основание немецкому математику Давиду Гильберту заявить, что все математические вопросы в принципе разрешимы, и провозгласить окончательную кодификацию методов математического рассуждения.
В 30-е годы нашего столетия этот оптимизм совершенно развеялся под влиянием удивительных и глубоких открытий К.Гёделя и А.Тьюринга. Гёдель доказал, что не существует системы аксиом и методов рассуждения, охватывающей все математические свойства целых положительных чисел. Позднее Тьюринг облек остроумные, но сложные гёделевы доказательства в более понятную форму. Как показал Тьюринг, гёделева теорема о неполноте эквивалентна утверждению, что не существует общего метода для систематического принятия решения о том, остановится ли когда-нибудь компьютерная программа, т. е. приведет ли она когда-нибудь компьютер к остановке. Разумеется, если некоторая конкретная программа приводит к остановке компьютера, этот факт легко может быть доказан непосредственным выполнением этой программы. Трудность заключается в доказательстве того, что произвольно взятая программа не останавливается.
Недавно мне удалось сделать еще один шаг по пути, намеченному Гёделем и Тьюрингом. Преобразовав некоторую конкретную компьютерную программу в алгебраическое уравнение такого типа, который был знаком еще древним грекам, я показал, что область чистой математики, известная под названием теории чисел, содержит в себе случайность. Это исследование демонстрирует, говоря словами Эйнштейна, что Бог порой использует целые числа для игры в кости.
Полученный результат, входящий составной частью в то, что было названо алгоритмической теорией информации, не является причиной для пессимизма; он не вносит в математику анархию. (В самом деле, большинство математиков продолжают работать над своими проблемами, как и раньше.) Он означает лишь, что в некоторых ситуациях должны применяться математические законы особого рода — статистические. Подобно тому как физика не в состоянии предсказать, в какой именно момент распадется данный атом радиоактивного вещества, математика порой бессильна дать ответ на некоторые вопросы. Однако физики могут надежно предсказать средние значения физических величин, отнесенные к большому количеству атомов. Математики в некоторых случаях должны, вероятно, ограничиваться таким же подходом.
НЕПРЕДСКАЗУЕМОСТЬ - понятие, знакомое владельцам игорных домов: именно она позволяет им получать прибыль от таких игр, как рулетка. Автор считает, что математики, подобно игрокам, должны приспосабливаться к непредсказуемости, присущей предмету их занятий. Она возникает из-за случайности, присутствующей в решениях даже весьма простых задач теории чисел.
МОЯ РАБОТА служит естественным продолжением работы Тьюринга, однако если Тьюринг анализировал, остановится или нет произвольная программа, я рассматриваю вероятность того, что универсальный компьютер прекратит работу, если его программа выбрана совершенно случайно. Что я имею в виду, говоря «выбрана совершенно случайно»? Поскольку любая программа может быть сведена к последовательности двоичных разрядов — битов (каждый из которых может принимать значение 0 или 1), «считываемых» и «интерпретируемых» компьютером, смысл упомянутой фразы состоит в том, что совершенно случайная программа, состоящая из nбитов, эквивалентна результату nбросаний монеты (где «орел» представляется нулем, а «решка» — единицей, или наоборот).
Вероятность того, что такая совершенно случайная программа остановится (обозначим эту вероятность символом W), выражается вещественным числом, заключенным между 0 и 1. (Утверждение W = 0 будет означать, что никакая случайная программа не остановится, а W = 1 — что всякая случайная программа остановится. Если мы имеем дело с универсальным компьютером, ни одно из этих крайних значений не реализуемо.) Поскольку W — вещественное число, полностью представить его можно лишь как бесконечную последовательность разрядов. В двоичной системе это последовательность нулей и единиц.
Наверное, самым интересным свойством этой бесконечной цепочки является то, что она алгоритмически случайна: она не может быть сжата в программу (рассматриваемую как цепочка битов) длиной, меньшей чем она сама. Это определение случайности, играющее основную роль в алгоритмической теории информации, было независимо сформулировано в середине 60-х годов советским академиком А. Н. Колмогоровым и мною. (Впоследствии это определение мне пришлось подправить.)
Основная идея такого определения проста. Некоторые последовательности битов могут быть сжаты в программы, более короткие, чем сами эти последовательности, потому что они построены по какой-либо схеме или подчиняются какому-либо правилу. Например, 200-битовая последовательность вида 0101010101... может быть сильно сжата, если ее задать как «100 повторений пары 01». Безусловно, такие последовательности не являются случайными. С другой стороны, 200-битовая последовательность, порожденная бросанием монеты, не может быть сжата, поскольку для этого процесса, вообще говоря, отсутствует закономерность в чередовании нулей и единиц; это совершенно случайная последовательность.
Из всех возможных последовательностей битов большинство несжимаемы и, следовательно, случайны. Поскольку последовательность битов можно рассматривать как представление по основанию 2 любого вещественного числа (если допускать бесконечные последовательности), отсюда вытекает, что большинство вещественных чисел на самом деле случайны. Нетрудно показать, что алгоритмически случайное число, такое, как W, проявляет обычные статистические свойства, связанные в нашем представлении со случайностью. Одним из таких свойств является нормальность: каждый возможный разряд появляется в числе с равной частотой. Если речь идет о двоичном представлении, то при стремлении числа разрядов к бесконечности, нулей и единиц будет в точности по 50%.
Для того чтобы W имела смысл, должно выполняться одно техническое условие: программа на входе должна быть самоограничивающейся. Иными словами, информация о ее общей длине (в битах) должна содержаться в самой программе. (Это на первый взгляд малозначительное условие, тормозившее прогресс в данной области в течение почти десятка лет, заставило переопределить понятие алгоритмической случайности.) Существующие языки программирования предназначены для построения самоограничивающихся программ, поскольку в этих языках предусмотрены механизмы начала и окончания программы. Такие конструкции позволяют программе содержать правильно определенные подпрограммы, которые в свою очередь могут включать в себя другие вложенные подпрограммы. Поскольку самоограничивающиеся программы строятся при помощи конкатенации (объединения двух последовательностей, скажем, строк или файлов, в одну. — Ред.) и вложения самоограничивающихся подпрограмм, программа синтаксически полна лишь тогда, когда последняя открытая подпрограмма «закрыта». По сути механизмы начала и окончания программ и подпрограмм функционируют соответственно как левая и правая скобка в математических выражениях. Если бы программы не были самоограничивающимися, их нельзя было бы построить из подпрограмм, и суммирование вероятностей остановки для всех программ дало бы бесконечный результат. Если же вы рассматриваете лишь самоограничивающиеся программы, то W не только ограничена 0 и 1, но ее можно явно вычислить «в пределе снизу». Другими словами, можно вычислять элементы бесконечной последовательности рациональных чисел (выраженных конечной последовательностью битов), каждое из которых ближе к точному значению W, чем предыдущее.
ДАВИД ГИЛБЕРТ (1900):
«Любая определенная математическая задача должна обязательно поддаваться точному решению, либо в виде непосредственного ответа на заданный вопрос, либо в виде доказательства невозможности ее решения и, кроме того, неизбежности неудач всех попыток ее решения. Однако, как бы трудны эти проблемы ни казались нам, и как бы ни были мы беспомощны перед ними, у нас имеется тем не менее твердая уверенность в том, что их решение будет получено в результате конечного числа чисто логических процессов... Мы слышим внутри нас постоянный призыв: вот проблема, ищи решение. Ты можешь найти его с помощью чистого мышления...»
ФУНДАМЕНТАЛЬНАЯ РАЗРЕШИМОСТЬ всех вопросов математики была заявлена Д. Гильбертом (на этом снимке ему около 50 лет). Гильберт считал, что конечной системы аксиом и правил рассуждения достаточно для доказательства истинности или ложности всех теорем.
Один из способов сделать это — систематически вычислять Wn для возрастающих значений n здесь Wn — вероятность того, что совершенно случайная программа длиной до n битов остановится через n секунд, если она выполняется на данном компьютере. Поскольку имеется 2k возможных программ длиной k битов. Wn можно в принципе вычислить: для каждого значения k от 1 до n надо определить, сколько из этих возможных программ на самом деле останавливается через n секунд, умножить это число на 2-k, а затем просуммировать все полученные произведения. Иначе говоря, каждая такая останавливающаяся k-битовая программа вносит свой вклад, равный 2-k, в значение W; вклад программ, которые не останавливаются, равен 0.
Если бы мы каким-то чудом узнали значение W с k точными разрядами, мы могли бы вычислять последовательность Wn, пока не получили бы значение, равное данному значению W. Тогда мы бы нашли все останавливающиеся программы размером меньше k; это по существу означало бы, что решена поставленная Тьюрингом проблема остановки для всех программ размером меньше k битов. Конечно, для разумного значения k требуемое для вычисления время было бы огромным.
ФУНДАМЕНТАЛЬНАЯ НЕРАЗРЕШИМОСТЬ математических вопросов была доказана К. Гёделем. На этом снимке, сделанном А. Ньюменом, ему около 50 лет. Гёдель опубликовал свое доказательство в 1931 г.; в ту пору ему было 25 лет, а Гильберту - 70.
КУРТ ГЁДЕЛЬ (1944):
«Оказалось, что решение некоторых арифметических задач требует использования предложений, по существу выходящих за рамки арифметики. Разумеется, в подобных обстоятельствах математика может потерять часть своей «абсолютной истинности», но под влиянием современной критики оснований это происходило не раз...»
ДО СИХ ПОР при обсуждении проблемы остановки я обращался исключительно к ее компьютерно-программной интерпретации, но в свете работы Дж.Джоунса из Университета в Калгари и Ю.В.Матиясевича из Ленинградского отделения Математического института им. Стеклова АН СССР в этой проблеме появляется новое «измерение». Исследования упомянутых авторов дают метод, позволяющий представить эту проблему в виде утверждений о диофантовых уравнениях определенного класса. Эти алгебраические уравнения, составленные при помощи операций над целыми числами — умножения, сложения и возведения в целую степень, названы по имени греческого математика Диофанта Александрийского, жившего в III в. н.э.
Выражаясь точнее, метод Джоунса и Матиясевича позволяет отождествить утверждение о том, что некоторая конкретная программа не остановится, с утверждением о том, что одно из уравнений из определенного класса диофантовых уравнений не имеет решений в целых числах. Как и в оригинальной версии проблемы остановки для компьютеров, здесь, если решение существует, это легко доказать: все, что требуется, — это подставить правильные числа и проверить, равными ли получились левая и правая части уравнения. Доказать же несуществование решения (если оно действительно отсутствует) намного сложнее.
Класс уравнений строится исходя из базового уравнения, которое содержит конкретную переменную k, называемую параметром и принимающую значения 1, 2, 3 и т. д. Таким образом, имеется бесконечно большой класс уравнений (по одному уравнению на каждое значение параметра k ), которые можно получить из одного базового уравнения для каждой программы из «семейства» программ. Математическое утверждение о том, что диофантово уравнение с параметром k не имеет решения, равносильно утверждению, что k-я компьютерная программа никогда не остановится. С другой стороны, если k-я программа останавливается, то соответствующее уравнение имеет в точности одно решение. В некотором смысле истинность (или ложность) утверждений этого типа является математически неопределенной, поскольку она изменяется непредсказуемым образом, когда параметр k принимает различные значения.
«КЛАСС» УРАВНЕНИИ порождается путем придания параметру k базового уравнения различных целочисленных значений.
Мой подход к непредсказуемости в математике подобен этому, но он приводит к гораздо более высокой степени случайности. Вместо «арифметизации» компьютерных программ (которые могут или не могут останавливаться) как класса диофантовых уравнений, я применяю метод Джоунса и Матиясевича для арифметизации единственной программы вычисления k-го разряда Wn.
ЭТОТ МЕТОД основан на любопытном свойстве четности биномиальных коэффициентов, которое было замечено Э.Люка сто лет назад, но до сих пор оставалось неоцененным по достоинству. Биномиальные коэффициенты представляют собой множители при степенях хk в разложении выражений вида (х + 1)n. Эти коэффициенты легко вычисляются с помощью так называемого треугольника Паскаля.
ТРЕУГОЛЬНИК ПАСКАЛЯ (вверху) служит для вычисления коэффициентов разложения выражений вида (х + 1)". Начав с треугольника из единиц, вычисляют значения на каждом последовательном уровне путем сложения соседних чисел; последней ставят единицу. Таким образом можно определить, например, что (х + 1)n = 1х4 + 4х3 + 6х2 + 4х1 + 1х0. Этот треугольник можно превратить в привлекательный фрактальный узор, если заменить нечетные коэффициенты единицами, а четные - нулями (внизу). Узор демонстрирует свойство коэффициентов, применяемое при «арифметизации» компьютерных программ, которая преобразует их в алгебраические уравнения.
В теореме Люка утверждается, что коэффициент при xk в разложении (х + 1)n нечетен только тогда, когда каждый разряд в двоичном представлении числа k меньше или равен соответствующему разряду в двоичном представлении числа n (сопоставление начинается с правых элементов). Это можно выразить проще, сказав, что коэффициент при хk в разложении (х + 1)n нечетен, если для каждого разряда k, равного 1, соответствующий разряд n тоже равен 1; в противном случае коэффициент четен.
Например, коэффициент при х2 в разложении бинома (х + 1)4 равен 6, т. е. четный. Соответственно единица двоичном представлении двойки (10) не стоит на том же месте, что и единица в двоичном представлении четверки (100).
Хотя идея арифметизации проста и изящна, выполнение этого построния представляет собой громоздкую программистскую задачу. Тем не менее мне казалось, что это может быть интересным. Поэтому я разработал программу «компилятор» для получения уравнении из программ для «регистровой машины». Регистровая машина представляет собой компьютер, состоящий из небольшого множества регистров для хранения чисел произвольной величины. Разумеется, это абстракция, поскольку любой реальный компьютер имеет регистры ограниченного объема.
Подав на вход реального компьютера, имеющего программу-компилятор, программу регистровой машины, которая выполняет инструкции на языке Лисп, получим через несколько минут на выходе уравнение длиной около 200 страниц, содержащее примерно 17 000 неотрицательных целых переменных. Итак, я могу вывести диофантово уравнение с параметром k, кодирующее k-й разряд Wn, путем простой подстановки программы на Лиспе (в двоичной форме), предназначенной для вычисления k-го разряда Wn, в 200-страничное уравнение. Для любой заданной пары значений k и n диофантово уравнение имеет в точности одно решение, если k-й разряд Wn равен 1, и не имеет решения, если k-й разряд Wn равен 0.
Поскольку это верно для любой пары значений k и п, можно, вообще говоря, зафиксировать k и систематически увеличивать значение n, вычисляя k-й разряд Wn для каждого значения n. Для малых значений n k-й разряд Wn будет беспорядочно флуктуировать между 0 и 1. В конце концов, однако, он станет равным 1 или 0, поскольку для очень больших значений n он должен быть равен k-му разряду W, который неизменен. Следовательно, диофантово уравнение в действительности имеет бесконечное число решений для конкретного значения своего параметра k, если k-й разряд и оказывается равным 1, и лишь конечное число решений, если k-й разряд W оказывается равным 0. Таким образом, вместо того чтобы выяснять, имеет ли диофантово уравнение решения для каждого значения своего параметра k, я узнаю, имеет ли оно бесконечно много решений.
НА ПЕРВЫЙ взгляд может показаться, что мы мало выигрываем, спрашивая «имеет ли уравнение бесконечно много решений», вместо «имеет ли оно вообще решения». Но на самом деле это очень важное различие: ответы на эти вопросы логически независимы. Два математических утверждения считаются логически независимыми, если одно нельзя вывести из другого, т. е. если ни одно из них не является логическим следствием другого. Это понятие независимости обычно отличают от понятия независимости, используемого в статистике. Последнее заключается в том, что два случайных события называются независимыми, если исход одного из них не оказывает влияния на исход другого. Например, результат бросания монеты никоим образом не влияет на результат следующего бросания: эти результаты статистически независимы.
Я использую оба понятия независимости. Ответ на мой вопрос для одного значения k логически независим от ответа на этот вопрос для другого значения k. Причина заключается в том, что конкретные разряды W, определяющие ответ, независимы статистически.
Легко доказать, что примерно для половины значений k число решений конечно, а для другой половины число решений бесконечно, однако не существует способа «сжать» эти ответы в формулу или набор правил: они как бы «подражают» результатам бросания монеты. Поскольку W алгоритмически случайна, то даже знание ответов для 1000 значений k не поможет найти правильный ответ для 1001-го значения k. Устанавливая, имеет ли конкретное уравнение конечное или бесконечное число решений, математик находится в положении игрока, бросающего монету. Какие бы аксиомы и доказательства мы ни применяли для диофантова уравнения с одним значением k, они будут неприменимы для того же самого уравнения при другом значении k.
Математическое рассуждение оказывается в этом случае в принципе бесполезным, поскольку нет логических взаимосвязей между полученными таким способом диофантовыми уравнениями. Будь ты хоть семи пядей во лбу, выведи длиннейшее доказательство, используй сложнейшие математические аксиомы, построенный бесконечный ряд предложений, устанавливающий, конечно или бесконечно число решений диофантова уравнения, окажется бесполезным, если k увеличить. Итак, даже в элементарных разделах теории чисел, связанных с диофантовыми уравнениями, возникают случайность, неопределенность и непредсказуемость.
АРИФМЕТИЗАЦИЯ W выполняется путем подстановки двоичного представления конкретной программы для вычисления k-го разряда Wn (в двоичной форме) вместо переменной в уравнение, полученное из программы для универсального компьютера. Wn является n-й аппроксимацией W - вероятности остановки компьютера при условии, что биты, составляющие его программу, определены случайным образом, например при помощи бросания монеты.
НО КАКИМ ЖЕ образом теорема Гёделя о неполноте, проблема остановки Тьюринга и моя работа влияют на математику? Большинство математиков не обращают внимания на эти результаты. Конечно, в принципе они согласны, что любая конечная система аксиом неполна, но на практике они игнорируют этот факт, как непосредственно не относящийся к их работе. Но иногда, к сожалению, его нельзя игнорировать. Хотя в исходном виде теорема Гёделя казалась применимой лишь к необычным математическим предложениям, не имеющим практического интереса, алгоритмическая теория информации показала, что неполнота и случайность являются естественными и распространенными повсюду свойствами. Это подсказывает мне, что следует более серьезно относиться к возможности поиска новых аксиом относительно целых чисел.
Тот факт, что многие математические проблемы оставались веками и даже тысячелетиями нерешенными, похоже, подтверждает мою точку зрения. Математики непоколебимо стоят на том, что причина неудач в решении подобных проблем заключена только в самих проблемах, но не заключается ли она в неполноте системы их аксиом? Например, вопрос о том, существуют ли нечетные совершенные числа, не поддается решению со времен древних греков. (Совершенным называется число, равное сумме своих делителей, исключая само это число. Например, 6 — совершенное число, поскольку 6 = 1 + 2 + 3.) Не может ли быть так, что утверждение «Не существует нечетных совершенных чисел» недоказуемо? Если это так, то не лучше ли принять его за аксиому?
Большинству математиков это предположение может показаться смехотворным, но для физика или биолога оно не выглядит столь уж абсурдным. Для тех, кто работает в эмпирических областях науки, основным критерием, позволяющим судить о том, следует ли рассматривать некоторое суждение как основание теории, служит полезность этого суждения, а вовсе не обязательно его «самоочевидная истинность». Если имеется много догадок, которые можно обосновать обращением к некоторой гипотезе, ученые-эмпирики принимают эту гипотезу. (Из несуществования нечетных совершенных чисел, по-видимому, не следует важных выводов, и, согласно этому критерию, такая аксиома не является полезной.)
На самом деле в некоторых случаях математики в своей работе опираются на недоказанные, но полезные предположения. Например, так называемая гипотеза Римана, хотя она никогда не была доказана, часто считается верной, потому что на ней основано много важных теорем. Более того, эта гипотеза была эмпирически проверена с помощью самых мощных компьютеров, и ни один опровергающий ее пример не был найден. Компьютерные программы (которые, как я уже сказал, эквивалентны математическим утверждениям) проверяются таким же способом - тестированием некоторого числа вариантов, а не строгим математическим доказательством.
СУЩЕСТВУЮТ ЛИ проблемы в других областях науки, для решения которых был бы полезен этот экскурс в основания математики? Я думаю, алгоритмическая теория информации может применяться в биологии. Регуляторные гены развивающегося зародыша являются по существу вычислительной программой построения организма. «Сложность» этой биохимической компьютерной программы можно, как мне думается, определить в терминах, аналогичных тем, что я развил при квантификации информационного содержания W.
Хотя W совершенно случайна (или бесконечно сложна) и никогда не может быть вычислена точно, ее можно аппроксимировать с произвольной точностью, если в распоряжении имеется бесконечный отрезок времени. Мне кажется, что «сложность» живого организма может быть приближена таким же образом. Последовательность Wn, аппроксимирующую W, можно рассматривать как метафору эволюции, и, возможно, она содержит зерно математической модели, описывающей эволюцию «сложности» биологического организма.
В конце своей жизни Дж. фон Нейман призвал математиков заняться созданием абстрактной математической теории происхождения и эволюции жизни. Эта фундаментальная проблема, подобно большинству проблем такого масштаба, бесконечно трудна. Возможно, алгоритмическая теория информации позволит найти путь, по которому следует идти.
В МИРЕ НАУКИ - 1990 № 3
Клод Е. Шеннон - незаурядный жонглер и выдающийся ученый
КЛОД Е. Шеннон не может сидеть на одном месте. Мы находимся у него дома, в викторианском особняке с лепными украшениями, с видом на озеро, к северу от Бостона. Я пытаюсь заставить его вспомнить, каким образом он пришел к теории информации. Но Шеннон в свои 73 года по-юношески стройный, с пышной копной седых волос и озорной улыбкой устал распространяться о своем прошлом. Может быть, мне лучше посмотреть его игрушки?
Не дожидаясь ответа и не взирая на мягкие возражения жены, Бетти, он вскакивает со стула и исчезает в соседней комнате. Когда я настигаю его там, он с гордостью показывает мне свои семь шахматных машин, цирковой шест с пружиной и бензиновым двигателем, складной нож с сотней лезвий, двухместный одноколесный велосипед и множество других чудес. Некоторые из его личных творений - такие как жонглирующий манекен и компьютер под названием THROBAC, выполняющий расчеты в римской системе счисления, - выглядят порядком запыленными и к тому же сломаны, но Шеннон, кажется, пребывает в восторге от всех этих игрушек, как десятилетний мальчишка, радующийся рождественским подаркам.
Неужели это тот человек, который еще молодым инженером, работая в компании Bell Laboratories, в 1948 г. написал «Великую хартию» эры информации: «Математическую теорию связи»? Ни его ли труд Р. Лаки, возглавлявший программу научных исследований в той же фирме, назвал величайшей работой «в анналах технической мысли»? Разве не его «интуицию первооткрывателя» член научного общества IBM P. Ландауэр сравнивает с гением Эйнштейна? Да, все это о нем. Но это еще и человек, который изобрел летающий диск на ракетном двигателе и который жонглировал, катаясь на одноколесном велосипеде по коридорам Bell Laboratories. «Я всегда следовал своим интересам, не думая ни о том, во что они мне обойдутся, ни об их ценности для мира, - говорил Шеннон. - Я потратил уйму времени на совершенно бесполезные вещи».
С детских лет Шеннона привлекали, с одной стороны, детальность технических конструкций, а с другой - общность математических принципов. Выросший в Гэйлорде (шт. Мичиган), он постоянно возился с детекторными приемниками и радионаборами, которые приносил ему отец, помощник судьи, и решал математические головоломки, которыми снабжала его старшая сестра Кэтрин, ставшая впоследствии профессором математики. Будучи студентом Мичиганского университета, он специализировался одновременно в электротехнике и математике.
То, что он был знаком сразу с двумя областями науки, помогло ему добиться первого крупного успеха, когда он был еще аспирантом Массачусетского технологического института. В своей диссертации он показал, как с помощью алгебры, изобретенной в середине XIX в. английским математиком Джорджем Булем, - которая оперирует такими понятиями, как «если событие Х или Y имеет место, a Z нет, то в результате наступает событие Q - можно представить работу переключателей и реле в электрических схемах.
Работа Шеннона имела очень важное значение: теперь инженеры в своей повседневной практике, создавая аппаратуру и программы для компьютеров, сети телефонной связи и другие системы, постоянно пользуются булевой алгеброй. Шеннон преуменьшает свою заслугу в этом открытии. «Просто случилось так, что никто другой не был знаком с этими обеими областями одновременно»,- говорит он. И после минутного размышления добавляет: «Мне всегда нравилось это слово - булева».
ТЕСЕЙ - механическая мышь, вместе со своим изобретателем Клодом Е. Шенноном на фотографии, сделанной в 1952 г. в Bell Laboratories. Мышь «учится» находить выход из лабиринта с помощью магнита, управляемого электрической схемой под полом лабиринта.
В 1941 г., через год после защиты докторской диссертации в Массачусетском технологическом институте, Шеннон поступил на работу в Bell Laboratories. Во время второй мировой войны он занимался разработкой криптографических систем, но в свободное время вынашивал идеи, которые позже вылились в теорию информации. Сначала Шеннон задался простой целью: улучшить процесс передачи информации по телеграфному или телефонному каналу, находящемуся под воздействием электрических возмущений, или шума. Он пришел к выводу, что наилучшее решение заключается не в техническом усовершенствовании линий связи, а в более эффективной упаковке информации.
Что такое информация? Оставляя в стороне вопрос о содержании этого понятия, Шеннон показал, что это измеримая величина: количество информации, содержащейся в данном сообщении, есть функция вероятности, что из всех возможных сообщений будет выбрано данное. Он определил общий потенциал информации в системе сообщений как ее «энтропию». В термодинамике это понятие означает степень случайности (или, если угодно, «перемешанности») системы. (Однажды Шеннон сказал, что понятием энтропии ему посоветовал воспользоваться великий математик Джон фон Нейман, указавший, что, так как никто не знает, что это такое, у Шеннона всегда будет преимущество в спорах, касающихся его теории.)
Шеннон определил основную единицу количества информации, названную потом битом, как сообщение, представляющее один из двух вариантов: «орел» - «решка», например, или «да» - «нет». В битах можно закодировать огромное количество информации, аналогично тому, как в старой игре в «20 вопросов» можно быстро выйти на правильный ответ, умело задавая вопросы. Бит можно представить как 1 или 0, или как присутствие или отсутствие тока в цепи.
На этом математическом фундаменте Шеннон затем показал, что любой канал связи имеет свою максимальную пропускную способность для надежной передачи информации. В действительности он доказал, что, хотя можно приблизиться к этому максимуму за счет искусного кодирования, достичь его невозможно. Этот максимум получил известность как предел Шеннона.
Каким образом можно приблизиться к пределу Шеннона? Первый шаг заключается в том, чтобы воспользоваться избыточностью кода. Подобно тому как влюбленный мог бы лаконично написать в своей любовной записке «я лбл в», путем эффективного кодирования можно сжать информацию, представив ее в наиболее компактной форме. С помощью специальных методов кодирования, позволяющих производить коррекцию ошибок, можно гарантировать, что сообщение не будет искажено шумом. Например, такое кодирование с коррекцией, применяемое к последовательности чисел, может быть основано на полиномиальной функции, на график которой должны попадать все числа. Дешифратор на принимающем конце линии связи знает, что числа, отклоняющиеся от графика функции, были искажены во время передачи.
Идеи Шеннона были слишком провидческими, чтобы иметь немедленный практический эффект. Схемы на вакуумных электронных лампах просто не могли еще вычислять сложные коды, требовавшиеся для того, чтобы приблизиться к пределу Шеннона. На самом деле только в начале 70-х годов с появлением быстродействующих интегральных микросхем инженеры начали в полной мере пользоваться теорией информации. В наше время идеи Шеннона играют важную роль почти во всех системах, хранящих, обрабатывающих или передающих информацию в цифровой форме, от лазерных дисков до компьютеров, от факсимильных машин до .автоматических космических станций, таких как «Вояджер».
Теория информации помимо связи проникла также и в другие области, в том числе в лингвистику, психологию, экономику, биологию и даже в искусство. В подтверждение приведем, например, такой факт: в начале 70-х годов в журнале «IEEE Transactions on Information Theory» была опубликована редакционная статья под названием «Теория информации, фотосинтез и религия». С точки зрения самого Шеннона, применение информационной теории к биологическим системам вовсе не является таким уж неуместным, поскольку, по его мнению, в основе механических и живых систем лежат общие принципы. Когда его спрашивают, может ли машина мыслить, он отвечает: «Конечно, да. Я машина и вы машина, и мы оба мыслим, не так ли?»
В действительности Шеннон был одним из первых инженеров, высказавших мысль о том, что машины можно запрограммировать так, чтобы они могли играть в игры и решали другие сложные задачи. В 1950 г. он изобрел механическую мышь Тесей, которая будучи управляема магнитом и сложной электрической схемой, скрытой под полом, обучалась находить выход из лабиринта. Под влиянием этого изобретения Институт инженеров по электротехнике и радиоэлектронике учредил конкурс «микромышь», в котором в настоящее время принимают участие тысячи студентов технических вузов со всех концов света.
Он построил машину, «читающую мысли» и играющую в «монетку», - игру, в которой один из играющих пытается угадать, что выбрал другой играющий, «орел» или «решку». Коллега Шеннона, также работавший в Bell Laboratories, Дэвид У. Хейджелбарджер построил опытный образец; машина запоминала и анализировала последовательность прошлых выборов оппонента, пытаясь отыскать в них закономерность и на ее основе предсказать следующий выбор. Поскольку человеку почти невозможно избежать таких закономерностей, машина выигрывала более чем в 50% случаев. Затем Шеннон построил свою собственную версию и вызвал Хейджелбарджера на легендарную дуэль. Машина Шеннона выиграла.
В 1956 г. Шеннон покинул Bell Laboratories, став профессором в Массачусетском технологическом институте. После того как в 1978 г. он официально ушел на пенсию, его величайшим увлечением стало жонглирование. Он построил несколько жонглирующих машин и разработал то, что можно было бы назвать объединенной теорией поля для жонглирования:
если В равно количеству мячиков, Н - число рук, D - время, которое каждый мячик находится в руке, F - время полета каждого мячика и Е - время, в течение которого рука пуста, то В/Н = (D + F)/(D + Е). (К сожалению, эта теория так и не помогла Шеннону побить свой личный рекорд - жонглирование четырьмя мячами.) Он разрабатывал также различные модели биржи акций и опробовал их в действии (по его словам, успешно) на своих собственных акциях. Он даже попробовал свои силы в поэзии: среди прочих его стихотворных произведений - «Рубрика на кубик Рубика», выдержанная в стиле «Та-ра-ра-бум-би-я».
Однако с конца 50-х годов Шеннон опубликовал очень мало работ по теории информации. Некоторые из его бывших коллег по Bell Laboratories поговаривали, что Шеннон «перегорел» и ему надоела созданная им самим теория, но Шеннон отрицает это. Он говорит, что продолжал изучать различные проблемы теории информации, по крайней мере на протяжении 60-х годов, но, с его точки зрения, результаты были не настолько интересными, чтобы их публиковать. «Большинство великих математиков написали свои лучшие работы, когда были еще молодыми», - говорил он.
В 1985 г. Шеннон и его жена внезапно решили посетить Международный симпозиум по теории информации, состоявшийся в английском городе Брайтоне. В течение многих лет он не принимал участия в конференциях, и сначала его никто не заметил. Затем участники симпозиума стали перешептываться: скромный седоволосый джентльмен, который то приходил, то уходил из залов, где слушались доклады, это Клод Шеннон. На банкете Шеннон сказал несколько слов, немножко пожонглировал тремя мячами и подписал множество автографов инженерам, выстроившимся в длинную очередь. Как вспоминает Р. Макилис из Калифорнийского технологического института, «это воспринималось так, как будто Ньютон появился на конференции, посвященной проблемам физики».
Дж. Хорган
В МИРЕ НАУКИ •1987 No1
История числа
ФИЛИП МОРРИСОН
Жорж Ифра. От ЕДИНИЦЫ до НУЛЯ:
ВСЕОБЩАЯ ИСТОРИЯ ЧИСЛА
FROM ONE то ZERO: A UNIVERSAL HISTORY OF NUMBERS, by Georges Ifrah. Translated by Lowel Bair. Viking Penguin Inc. ($ 35)
АВТОР КНИГИ считает, что письмо было изобретено «хозяйственниками», или экономами, которым приходилось иметь дело с предметами, столь многочисленными и разнообразными, что их названия невозможно было удержать в памяти.
Время действия - 50 веков назад, место действия - города Урук в Древнем Шумере на Евфрате и Сузы в Эламе, к востоку от Тигра. Первые из известных нам документов - это глиняные таблички. Покуда глина была мягкой, заостренной палочкой на них наносились знаки. Среди этих записей мы видим пиктограммы финиковой пальмы и бараньих ног вместе со знаками, служившими для обозначения чисел. Знакомимся мы и с прародителем этой «бухгалтерской книги»: приблизительно за два столетия до того существовали глиняные «конверты», напоминающие по форме и размеру теннисный мяч. Такой «конверт» содержал набор небольших глиняных фигурок, предшественниками которых, судя по всему, были счетные камешки. (В книге приводится рентгеновский снимок одного из таких образцов, хранящегося в Лувре.) Эти фигурки служили для обозначения цифр: так, небольшой шарик символизировал «десять». Печать на внешней стороне «конверта» подтверждала подлинность документа.
За последнее десятилетие многочисленные французские экспедиции и отдельные исследователи шаг за шагом проследили зарождение цифрового письма и его последовательное развитие на протяжение нескольких столетий. Сперва «конверт» сам стал документом: его «цифровое содержание» дублировалось в виде знаков на наружной стороне, поэтому разрушать «конверт» было необязательно. Затем он превратился в испещренные знаками счетные таблички, текст которых также скреплялся печатью. В Уруке между 3200 и 3100 гг. до н.э. появился новый тип табличек, на которые знаки наносились с помощью печаток. Эти печатки иногда объединяли в себе числовые символы, предшественниками которых были фигурки, служившие для счета, с новыми символами для обозначения считаемых предметов. Подчас эти символы весьма реалистичны, например фигурка птицы, а иногда совершенно абстрактны, например перечеркнутый кружок означал овцу. Хотя письменность уже появилась, она еще была далека от полноты настоящего письменного языка: экономы должны быть «экономными».
Любопытнейшая иллюстрация воспроизводит то, что позволило расшифровать шумерские цифровые знаки: писцы имели обыкновение записывать общую сумму на обратной стороне таблички. Изображенная на иллюстрации табличка представляет собой список товаров, в числе которых 15 мешков ячменя, 30 мешков пшеницы и т. п. Общая сумма была записана на обратной стороне глиняного «листа» и составляла 145 мешков. Множество подобных табличек давали уникальный материал для расшифровки.
Эта интереснейшая книга, написанная талантливым и увлеченным своей темой преподавателем математики (к тому же и полиглотом) из Франции, содержит 30 глав, охватывающих всю историю систем счисления, как нашедших, так и не нашедших письменного выражения. Пытаясь проследить историю происхождения цифр, автор приводит некоторые из них в своем собственном написании: единый почерк помогает выявить элементы сходства, однако при этом знаки, принятые для обозначения чисел в различных языках, к сожалению, теряют свою индивидуальность.
Можно сказать, что вся история числа представляет собой постепенный переход от простого повтора к сложившейся позднее системе. Хорошо известны факты соответствия чисел и частей тела: это не только 10 пальцев, к которым восходят все известные системы счисления (за исключением машинных языков), но и способы счета, использовавшиеся, скажем, в районе Торресова пролива, где локти, колени, бедра и т. п. служили наглядным представлением чисел вплоть до 33. Таблица названий первых десяти чисел на двух десятках индоевропейских языков, от санскритского dvi и tri до исландского tveir и prir, выдает их родство. Эти слова сохранили лишь одно значение - численное, но кто знает, может быть и они когда-то обозначали части тела?
Основание системы счисления - величайшее изобретение древних. Роль анатомии в его рождении очевидна. Однако остается неясным происхождение основания 60. Оно используется для измерения времени и при вычислении углов, которое по нашим представлениям впервые стали производить вавилонцы и их предшественники шумеры. Вместе со вспомогательным основанием 10 оно упростило запись чисел. Ведь если число 10 звалось «у», а 60 - «геш», вполне естественно записывать 600 как «геш-у».
Но почему именно 60? Гипотезам (ныне устаревшим), пытавшимся дать ответ на этот вопрос, Ифра посвящает целую страницу. Греческий автор Теон впервые предложил объяснение, которым удовлетворялись многие поколения математиков: 60 - уникальное число по количеству делителей. Другое предположение, выдвинутое в 1904 г., состоит в том, что два народа, один из которых пользовался шестеричной, а другой - десятеричной системой счисления, объединившись, создали основание 60. Еще один аргумент основывался на том, что вавилонскому часу (двенадцатой доле суток) соответствует дуга, в 60 раз большая углового диаметра Солнца.
Кантор, основатель теории множеств, полагал, что причину следует искать в округленном значении длительности года - 360, и уже впоследствии простота гексагонального деления круга, при котором хорда равняется радиусу, «помогла» числу 60 прочно укрепиться в качестве основания. Однако, подвергшись критике оппонентов, утверждавших, что не следует связывать систему счисления ни с астрономией, ни с геометрией, Кантор отказался от своих аргументов. Сегодня, зная, что некогда в Китае делили окружность не на 360, а на 365 1/4 градусов, мы не можем не пожалеть, что Кантор так легко сдался. По всей видимости, в далекой древности мало кому, кроме астрономов, приходилось оперировать большими числами. Уже на первых табличках используется стандартная смешанная шумерская система с основанием как 10, так и 60.
Вавилонским экономам мы обязаны первой системой записи чисел, в которой место цифры указывает на порядок величины (позиционная система счисления), а также введением нуля. Числа в их «бухгалтерских книгах» записаны уже в шестидесятеричной системе, в которой за основание принято число 60, хотя все числительные - это простые комбинации из знаков для обозначения 1 и 10 (например, 32 записывается тремя знаками для 10 и двумя для 1). Чтобы написать 610, на месте шестидесяти нужно было поставить обозначение 10 и такой же знак на месте единиц. Здесь писцу приходилось особенно аккуратно наносить знаки: слишком близко поставленные, они выглядели бы, как 20. Потребовалось еще около 1000 лет для усовершенствования техники записи чисел: необходимый пробел стали заполнять специальным знаком разделения, обычно использовавшимся в двуязычных текстах для пометки перехода от одного языка к другому. В «бухгалтерских книгах» этот знак использовался лишь для обозначения нуля в середине числа (но не в начале и не в конце).
Остается неясным, подразумевался ли под этим знаком абстрактный нуль, скажем, результат разности 20 минус 20. Авторы некоторых текстов прибегают взамен к более конкретной формулировке, например «зерно кончилось». Такова предыстория нашего нуля, появление которого относят к IV в. до н.э.
Цифры современной десятичной системы носят название арабских, поскольку европейцы заимствовали их у арабов. Однако, по всей вероятности, их родина - южная Индия. Они встречаются во множестве индийских документов, относящихся к VI-IX вв. В этих документах уже используется десятичная система записи числа с ее простыми и удобными в написании цифрами (некоторые из них, хотя и не все, можно узнать и сейчас). Так что арабские цифры, «этот единственный универсальный язык нашего времени», ведут свое происхождение из Индии, хотя не исключено, что сама система счисления заимствовала кое-что из древнего Вавилона. Последнее остается неясным: возможно, что вся система - целиком индийское изобретение, а предшественником ее были обычные счеты.
Автор уделяет большое внимание документальным свидетельствам и различным гипотезам. Сама идея знака, обозначающего ничто, затронула воображение европейцев, словно в нем было заключено нечто магическое. Отголосок этой таинственности мы до сих пор слышим в слове «шифр», которое восходит к арабскому sifr - «пустота».
Книга отличается полнотой и ясностью изложения, кроме того, она содержит немало еще не разгаданных головоломок с цифрами и знаками, которые бросают вызов любителям подобных задач.