Сон разума. Математическая логика и ее парадоксы
Шрифт:
* * *
Р И NP
Как вы увидели в главе 3, датой символического начала математики XX века считается август 1900 года, когда Гильберт обнародовал свой список из двадцати трех задач на конференции в Париже. Вновь в Париже, но уже сто лет спустя, экспертная комиссия из Института Клэя выбрала семь открытых задач, которые, по ее мнению, обозначили направление математических исследований нового столетия. Четвертая проблема в этом списке, известная как проблема равенства классов Р и NP, заключается как раз в том, чтобы подтвердить, существуют ли задачи класса NP сами по себе или же, напротив, любую задачу, решение которой можно проверить за полиномиальное время, также можно быстро решить, найдя некий хитроумный алгоритм. Того, кто найдет решение этой проблемы, ждет премия в один миллион долларов. Как видите, математика иногда может приносить
* * *
В связи с этим определением сложности возникает еще одно замечание: в подобной трактовке не проводится различие между задачами, для решения которых требуется одинаковое число операций. По нашему определению, запомнить пароль из двенадцати символов — это простая или сложная задача независимо от того, из каких символов состоит пароль, так как для этого неизменно потребуется двенадцать действий: запомнить первый символ, второй, третий и т. д. до двенадцатого.
Однако никто, будучи в здравом уме, не скажет, что запомнить пароли 111111111111 и 6u0yfz3eq85s одинаково просто. Первый пароль можно сжать до слов «12 единиц», а второй пароль можно описать только одним способом — посимвольно. В середине 70-х годов советский математик Андрей Колмогоров на основе этого примера ввел новое определение сложности, предложив заменить число операций на число инструкций. Сложность последовательности символов стала определяться как минимальная длина алгоритма, необходимого для ее генерации.
Представим себе машину Тьюринга, задача которой — записать определенную последовательность нулей и единиц, которую мы назовем s. Как вы увидели из предыдущей главы, машине нужно дать последовательность инструкций вида «Если считано 1, сместиться вправо и перейти к инструкции № 2». В этом упрощенном варианте мы говорим, что сложностью s является натуральное число n, если существует машина Тьюринга, описанная посредством n инструкций, выходным значением которой является s, и если никакая машина не может сгенерировать заданную последовательность за меньшее число инструкций. Таким образом определяется функция К (по первой букве фамилии Колмогорова), которая сопоставляет каждой последовательности нулей и единиц ее сложность. Рассмотрим последовательность 1111… Если подать на вход машины Тьюринга ленту, на которой записаны только нули и единственная инструкция которой гласит «Инструкция № 1: Если считан 0, записать 1 и перейти к инструкции № 1. Если считан 1, сместиться вправо и перейти к инструкции № 1», то в результате мы получим последовательность 1111… Это означает, что заданная последовательность имеет минимально возможную сложность К(s) = 1, так как для ее описания достаточно единственной инструкции.
Живительное следствие этого определения сложности состоит в том, что компьютеры не могут генерировать бесконечные случайные последовательности нулей и единиц. Интуитивно понятно, что последовательность является случайной, когда невозможно предсказать, каким будет ее следующий элемент. Это означает, что описание случайной последовательности не может быть короче, чем сама последовательность.
Иными словами, ее сложность бесконечно велика. Однако все компьютерные программы содержат конечное число инструкций (вспомните определение машины Тьюринга из предыдущей главы). Следовательно, генерируемые ими последовательности нулей и единиц, сколь случайными бы они ни казались, всегда будут иметь конечную сложность. Компьютеры могут воспроизводить только псевдослучайные последовательности, поэтому для генерирования истинно случайных последовательностей многие физики пытаются использовать недетерминированность атомов.
С другой стороны, определение сложности по Колмогорову во многом схоже с парадоксом библиотекаря, о котором мы рассказали в конце главы 2, где рассматривается множество натуральных чисел, которые можно описать пятнадцатью словами. Так как число фраз, состоящих из пятнадцати слов, является конечным, множество таких чисел также будет конечным. Следовательно, среди всех чисел, не принадлежащих этому множеству, можно определить наименьшее. Обозначим его за n. Однако в этом случае n будет «наименьшим числом, которое нельзя описать менее чем пятнадцатью словами» — это описание содержит всего девять слов!
Логично задаться вопросом, не приведет ли введенное нами определение сложности к противоречиям. Ответ удивляет: если бы функция К была вычислимой, то есть если бы существовала машина Тьюринга, способная вычислить для данной последовательности нулей и единиц s сложность К(s), то рассуждения, аналогичные тем, что мы использовали при решении проблемы остановки, позволили бы воспроизвести парадокс библиотекаря на формальном языке арифметики. Следовательно, единственно возможный ответ таков: сложность не является вычислимой, и этого достаточно для разрешения парадокса библиотекаря, который оставался открытым: выражение «описать пятнадцатью словами» некорректно, так как принадлежит не к языку, а к метаязыку.
На предыдущих страницах мы ограничились обсуждением приятия сложности исключительно с точки зрения математики, и читатель убедился, что определение этого понятия сопряжено с многочисленными трудностями. Наша изначальная цель была еще более амбициозной: мы хотели узнать, как измеряется сложность понятий «любовь» и «справедливость». Постепенно все новые и новые математические открытия вдохновили исследователей на создание новой теории сложности, которую можно обобщить фразой «целое больше, чем сумма его частей». Слова «сияние», «рана», «солнце» и «ближайший» имеют четкие значения — мы можем узнать их в словаре. Но когда французский поэт Рене Шар пишет «Сияние — рана, ближайшая к солнцу», из четырех прекрасно знакомых нам слов рождается нечто новое.
Стих представляет собой нечто большее, чем сумму слов, поэтому понять поэзию непросто.
Эта эмерджентность присуща не только языку — она характерна для так называемых общественных насекомых, с ее помощью объясняется успех интернета, и она является одним из ключей к изучению нервных систем живых существ. Представим себе, например, крохотного муравья, который в поисках пищи следует алгоритмам, заложенным в его генах. Мы никогда не смогли бы понять сложную организацию муравейника, способного приспосабливаться к экстремальным ситуациям, если бы рассматривали его исключительно как совокупность отдельных муравьев. Иммунная система также представляет собой нечто большее, чем совокупность клеток, экономика есть нечто большее, чем множество покупателей акций, а интернет — это нечто большее, чем сумма отдельных действий пользователей из разных уголков планеты. Понять, каким образом из относительной простоты отдельных компонентов этих систем возникает сложное единое целое — одна из величайших задач науки начала нынешнего столетия.
Хотя определение сложной системы как системы, в которой целое больше суммы его частей, довольно приблизительно, нет сомнений, что оно весьма точно описывает наш мозг. В этом случае отдельными компонентами системы являются нейроны — клетки, получающие импульсы, обрабатывающие их и передающие их другим нейронам посредством множества отростков. Среди исследователей мозга распространено мнение, согласно которому сеть связей, благодаря которым мозг становится чем-то большим, чем просто совокупностью отдельных нейронов, лежит в основе таких явлений, как восприятие, разум и чувства. А если бы мы могли воссоздать подобную структуру в информатике? Первые попытки математического моделирования нейронов упоминаются в статье, опубликованной в 1943 году, в которой невролог Уоррен Маккалок и логик Уолтер Питтс определили нейрон как функцию, которая на основе ряда входных значений выдает единственное выходное значение.
До этого момента все функции, рассмотренные в этой книге, имели единственное входное значение и преобразовывали его в другое значение посредством ряда операций. Однако в реальной жизни очень и очень немногие явления определяются всего одним параметром. Современная теория искусственных нейронных сетей, созданная на основе идей Питтса и Маккалока, позволяет имитировать работу мозга с помощью функций от нескольких параметров. Предположим, что мы хотим вычислить значение функции f, которое зависит от чисел х1, x2, … хn. Основная идея здесь заключается в том, что программа, в которую передаются эти числа, обрабатывает их подобно тому, как ядро нейрона обрабатывает электрические импульсы, поступающие по отросткам. Так как величина этих импульсов может отличаться, для каждого числа х нужно указать еще одно число, ил, которое называется весом и обозначает важность каждого электрического импульса по отношению к остальным. Например, если w1 и wn намного больше, чем w2, w3 … wn-1 это означает, что на результирующее значение оказывают наибольшее влияние первый и последний импульс. На основе весов импульсов в искусственной нейронной сети рассчитывается взвешенная сумма s = w1x1 + w2x2 + … + wnxn и находится значение функции, как показано на рисунке.