Хавьер Фресан - Том. 22. Сон разума. Математическая логика и ее парадоксы

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

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

С другой стороны, определение сложности по Колмогорову во многом схоже с парадоксом библиотекаря, о котором мы рассказали в конце главы 2, где рассматривается множество натуральных чисел, которые можно описать пятнадцатью словами. Так как число фраз, состоящих из пятнадцати слов, является конечным, множество таких чисел также будет конечным. Следовательно, среди всех чисел, не принадлежащих этому множеству, можно определить наименьшее. Обозначим его за n . Однако в этом случае n будет «наименьшим числом, которое нельзя описать менее чем пятнадцатью словами» — это описание содержит всего девять слов!

Логично задаться вопросом, не приведет ли введенное нами определение сложности к противоречиям. Ответ удивляет: если бы функция К была вычислимой, то есть если бы существовала машина Тьюринга, способная вычислить для данной последовательности нулей и единиц s сложность К( s ), то рассуждения, аналогичные тем, что мы использовали при решении проблемы остановки, позволили бы воспроизвести парадокс библиотекаря на формальном языке арифметики. Следовательно, единственно возможный ответ таков: сложность не является вычислимой, и этого достаточно для разрешения парадокса библиотекаря, который оставался открытым: выражение «описать пятнадцатью словами» некорректно, так как принадлежит не к языку, а к метаязыку.

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

Стих представляет собой нечто большее, чем сумму слов, поэтому понять поэзию непросто.

Эта эмерджентность присуща не только языку — она характерна для так называемых общественных насекомых, с ее помощью объясняется успех интернета, и она является одним из ключей к изучению нервных систем живых существ. Представим себе, например, крохотного муравья, который в поисках пищи следует алгоритмам, заложенным в его генах. Мы никогда не смогли бы понять сложную организацию муравейника, способного приспосабливаться к экстремальным ситуациям, если бы рассматривали его исключительно как совокупность отдельных муравьев. Иммунная система также представляет собой нечто большее, чем совокупность клеток, экономика есть нечто большее, чем множество покупателей акций, а интернет — это нечто большее, чем сумма отдельных действий пользователей из разных уголков планеты. Понять, каким образом из относительной простоты отдельных компонентов этих систем возникает сложное единое целое — одна из величайших задач науки начала нынешнего столетия.

Хотя определение сложной системы как системы, в которой целое больше суммы его частей, довольно приблизительно, нет сомнений, что оно весьма точно описывает наш мозг. В этом случае отдельными компонентами системы являются нейроны — клетки, получающие импульсы, обрабатывающие их и передающие их другим нейронам посредством множества отростков. Среди исследователей мозга распространено мнение, согласно которому сеть связей, благодаря которым мозг становится чем-то большим, чем просто совокупностью отдельных нейронов, лежит в основе таких явлений, как восприятие, разум и чувства. А если бы мы могли воссоздать подобную структуру в информатике? Первые попытки математического моделирования нейронов упоминаются в статье, опубликованной в 1943 году, в которой невролог Уоррен Маккалок и логик Уолтер Питтс определили нейрон как функцию, которая на основе ряда входных значений выдает единственное выходное значение.