Ритм Вселенной. Как из хаоса возникает порядок

К тому же архитектура тесного мира, возможно, оказалась бы предпочтительным вариантом в других случаях, когда приходится обеспечивать быстрое продвижение информации по чрезвычайно сложной системе. Следующий случай, который мы решили изучить, представляет собой классическую задачу компьютерной науки, которая называется «проблемой классификации плотности для одномерных двоичных автоматов»[248]

. Попробуем сформулировать ее более простым языком. Представьте себе кольцо из 1000 лампочек. Каждая из этих лампочек может быть либо включена, либо выключена. На очередном временно

м шаге каждая из этих лампочек смотрит на трех своих соседей по обе стороны от себя и с помощью некоторого правила (которое еще предстоит определить) решает, в каком состоянии (включена или выключена) ей нужно пребывать в следующем цикле. Задача заключается в том, чтобы разработать правило, которое позволит такой сети решить определенное вычислительное задание. Поначалу это задание кажется до смешного простым: решить, было ли большинство этих лампочек поначалу включено или выключено. Если более половины лампочек было поначалу включено, то предполагается, что повторное выполнение этого правила приведет всю сеть к конечному состоянию, в котором все лампочки включены (и наоборот, если поначалу большинство этих лампочек было выключено, то предполагается, что конечное состояние соответствует всем выключенным лампочкам).

Эта задача оказывается тривиальной при наличии центрального процессора – «всевидящего ока», которое способно контролировать такую систему в целом и определять, было ли большинство лампочек поначалу включено или выключено. Однако нужно учитывать, что в данном случае речь идет о децентрализованной системе. «Всевидящего ока», которое обладало бы глобальным знанием, в этой системе нет. Лампочки страдают близорукостью: по определению, каждая из них может видеть лишь трех своих соседей по левую и по правую сторону от себя. Именно это и делает нашу задачу столь непростой: как может такая система, пользуясь неким локальным правилом, решить задачу, которая по своему характеру является фундаментально глобальной?

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

Никому до сих пор не удалось найти правило, которое срабатывало бы каждый раз. Мировой рекорд поставило правило, которое позволяло получить правильный результат примерно в 82 % случаев – то есть оно правильно классифицировало примерно 82 % всех исходных условий как «большинство лампочек включено» или «большинство лампочек выключено», уложившись в заданное время. Первое правило, которое могло бы показаться вам подходящим для проверки – «правило большинства», согласно которому каждая лампочка подражает тому, что делает большинство ее соседей, – совершенно неработоспособно. Сеть замыкается в неком «полосатом» состоянии, в котором блоки включенных смежных лампочек перемежаются с блоками выключенных лампочек. Такой результат совершенно неприемлем для нас, как неприемлемо жюри суда присяжных, которое неспособно вынести вердикт по причине разделения мнений. Предполагается, что такая сеть должна сойтись к единодушному вердикту, когда все лампочки либо включены, либо выключены.