Текст книги "Суперфрактал"
Автор книги: Сергей Деменок
Жанры:
Прочая научная литература
,сообщить о нарушении
Текущая страница: 8 (всего у книги 11 страниц)
Клеточные автоматы
Алекс Беллос, автор книги «Красота в квадрате», пишет:
«Математики любят играть. Одна из специфически математических игр называется „Жизнь“ (Game of Life) – и она действительно специфична: игровое поле расчерчено на бесконечное количество квадратных клеток, каждая из которых может быть мертвой или живой. Далее в зависимости от того, какие у клетки соседи, с ней происходят изменения: она либо выживает, либо умирает, либо рождается, либо остается мертвой. И все. Остается лишь изобразить на поле любую фигуру из живых клеток и следить, что с ними будет дальше. Каждое поколение игровое поле меняется, так как все клетки „обновляют статус“ в зависимости от своего окружения. Казалось бы, ничего особенного, но в действительности подобный клеточный автомат – это целая отдельная вселенная, способная самовоспроизводиться, эволюционировать и развиваться».
Итак, клеточные автоматы – это математические объекты с дискретными пространством и временем. Каждое положение в пространстве представлено отдельной клеткой, а каждый момент времени – дискретным временным шагом или поколением. Состояние каждой пространственной клетки определяется очень простыми правилами взаимодействия. Эти правила предписывают изменения состояния каждой клетки в следующем такте времени в ответ на текущее состояние соседних клеток.
Преобразование системы по правилу «сумма по модулю два»
Например, если пустой клетке присвоено значение 0, а занятой клетке – 1, то правила можно представить, скажем, так: на каждом шаге каждой клетке присваивается значение 0, если две ближайшие к ней клетки либо обе пусты, либо обе заняты. В арифметическом смысле это соответствует правилу, согласно которому новое значение каждой клетки равно сумме значений ближайших к ней клеток по модулю два. Далее такое построение можно автоматически повторять на каждом следующем шаге – отсюда название «клеточный автомат».
Впервые идея таких автоматов появляется в 1940-х годах в работах Джона фон Неймана и Станислава Улама. Улам и фон Нейман были близкими друзьями, эмигрантами из Восточной Европы, выходцами из верхушки среднего класса с еврейскими корнями. Оба очутились в одинаковой политической ситуации и оба обладали выдающимся интеллектом. В 1935 году фон Нейман пригласил Улама в США, а четыре года спустя сделал Уламу, работавшему тогда в Висконсинском университете, более интригующее предложение: перебраться в Нью-Мексико и присоединиться к нему в работе над неизвестным проектом. Улам взял в университетской библиотеке путеводитель по штату Нью-Мексико и увидел, что до него путеводитель брали его коллеги, которые исчезли куда-то без всяких объяснений. Выяснив, в каких областях они работали, он понял, что именно его просят сделать. Так Улам присоединился к Манхэттенскому проекту в Лос-Аламосе.
В ходе разработки термоядерного оружия Улам понял, что если поведение физической системы является слишком сложным, то для того, чтобы его прогнозировать, нужно предоставить компьютеру возможность сделать множество случайных оценок, а затем получить более точные показатели с помощью статистических методов. Во время одной из поездок на автомобиле Улам объяснил этот метод фон Нейману; тогда и было придумано для него название – «метод Монте-Карло». Например, для того чтобы определить вероятность того, что шарик рулетки остановится на черном, игроку не нужно решать уравнение – он может просто подсчитать, сколько раз шарик выпадает на черное после сотен случайных бросков.
Так Улам увлекся теорией игр. Все свое свободное время в Лос-Аламосе он тратил на изобретение игр с одним участником. Эти игры сводились к созданию шаблонов из ячеек решетки. Изменение правил создания таких шаблонов позволяло строить фигуры, которые могли разрастаться и меняться весьма необычными способами. Эти игры вдруг пересеклись с исследованиями, в которых фон Нейман пытался выяснить, что понадобится машине, чтобы воспроизвести себя.
Ему понадобилось посвятить 200 страниц своей книги «Теория самовоспроизводящихся автоматов» доказательству того, что «универсальный строитель» принципиально возможен. Однако он обнаружил, что самовоспроизводиться способна только машина, преодолевшая определенный порог сложности. Это очень важный вывод: качественно новые свойства появляются у системы только тогда, когда она обладает достаточным уровнем сложности.
Улам выдвинул предположение, что для того, чтобы сосредоточиться исключительно на логических аспектах самовоспроизведения, вместо работы с реальной машиной фон Нейману следует проанализировать фигуры, образующиеся на решетке ячеек. В процессе обсуждения этой задачи двое ученых изобрели новую математическую концепцию – «клеточный автомат».
Фон Нейман разработал клеточный автомат, в котором каждая клетка находилась в одном из 29 состояний, и придумал правила, призванные обеспечить самовоспроизведение исходного шаблона, состоящего из 200 000 клеток. Клеточные автоматы не привлекали к себе особого академического интереса до тех пор, пока на них не обратил внимание британский математик с еще более «игривым разумом, чем у Улама».
В 1960-х годах в комнате отдыха математического факультета Кембриджского университета преподаватели и студенты постоянно играли в настольные игры и придумывали новые. Идей было так много, что один преподаватель даже вел файл под названием Games Without Names («Игры без названий») и сопутствующий файл – Names Without Games («Названия без игр»). Здесь Джон Конвей, ливерпульский фанатик игры в нарды и талантливый математик, изобрел свой клеточный автомат на квадратной сетке, которому он дал имя Game of Life («Игра „Жизнь“»).
В этой игре клетка является либо живой, либо мертвой и подчиняется следующим правилам.
• Рождение: мертвая клетка, имеющая три живые соседние клетки, становится живой.
• Выживание: живая клетка, имеющая две или три живые соседние клетки, продолжает жить.
• Смерть от одиночества: живая клетка, у которой нет по соседству живых клеток или есть только одна такая клетка, умирает.
• Смерть от перенаселенности: живая клетка с четырьмя или более соседними клетками умирает.
• Примечание. У каждой клетки есть восемь соседей; к их числу относятся четыре смежные клетки и четыре клетки, с которыми она соприкасается по диагоналям в углах. Перечисленные выше законы применяются по отношению ко всем клеткам одновременно, и каждый раз, когда это происходит, появляется новое поколение клеток.
Вот и все. Простота локальных правил может генерировать невероятно сложное поведение системы. При этом самая увлекательная особенность игры «Жизнь» заключается в том, что она разнообразна и совершенно непредсказуема. Нет другого способа узнать, что произойдет даже с самыми простыми фигурами, кроме отслеживания их жизни на протяжении многих поколений. Конвей и его коллеги делали это вручную. Живые клетки были фишками, которые размещались на доске для игры го с разметкой 19 х 19 линий. Когда для шаблона требовалось больше места, на полу укладывали дополнительные доски. Были найдены новые устойчивые конфигурации, получившие такие названия, как «батон», «корабль», «лодка» и «змея». Иногда исходный шаблон погибал или быстро менялся, превращаясь в одну из известных устойчивых конфигураций, а иногда начинал жить своей жизнью, что приводило всех в сильное волнение. Например, пентамино в форме буквы R состояло всего из пяти клеток, но продолжало эволюционировать на протяжении десятков поколений, пока на 69-м поколении не произошло исключительное событие. Эта конфигурация произвела на свет фигуру из пяти клеток, скользившую по доске.
Новая фигура получила имя «глайдер» (от англ. Glider – «планер», ее поведение проиллюстрировано на рисунке ниже). Через два поколения конфигурация переворачивается на другую сторону, а еще через два снова поворачивается таким образом, что оказывается на одну клетку ниже и на одну дальше от исходной позиции. Глайдер продолжает смещаться на одну клетку вниз и одну вперед каждые четыре поколения. Он будет двигаться в одном и том же направлении по диагонали до бесконечности, если ничто не преградит ему путь.
На мониторах ПК, планшетах или смартфонах появился целый зоопарк «живых» клеточных образований. В 1982 году Джон Конвей выдвинул предположение о том, что если бы решетка игры «Жизнь» была достаточно большой и в исходном состоянии клетки располагались на ней в случайном порядке, то
И если на этом не остановиться, то у разумных клеточных существ могут появиться компьютеры, способные содержать внутри себя новые клеточные автоматы, в которых
Эта идея восходит к работам фон Неймана над машинами, которые были бы способны самостоятельно воспроизводиться. Размышляя над тем, как машина может построить точную копию самой себя, он столкнулся с логической проблемой. Вычисляющие машины, как мы знаем, состоят из аппаратного и программного обеспечения. Аппаратное обеспечение «конструирует» новый аппарат, следуя инструкциям, закодированным в программе. В идеале машина создаст новую машину с точно такой же программой. В этом случае программа должна содержать инструкции по поводу создания новой программы, которая в свою очередь должна содержать инструкции по поводу того, как создать инструкции в отношении построения новой программы, и так далее до бесконечности. В итоге мы получаем бесконечную регрессию инструкций, содержащихся в данной программе, что недопустимо, поскольку программа должна быть конечной. С другой стороны, если программа не включает никакую информацию о себе, машина не сможет себя полностью воссоздать, поскольку в новой машине нет программного обеспечения. Фон Нейман решил эту головоломку следующим образом: для того чтобы машина могла воспроизвести себя, необходимо ввести в систему новый элемент – устройство для копирования программы. Машина-конструктор считывает программу, строит новую машину, совершенную во всех отношениях, кроме одного – в ней нет программы. На последнем этапе устройство копирования создает копию программы и отправляет ее в новую машину. Самовоспроизводящаяся машина фон Неймана использует программу двумя разными способами: машина-конструктор читает ее как набор инструкций, а копировальное устройство создает ее копию.
Только применение программы один раз в качестве инструкции, а другой раз – в качестве объекта копирования позволило решить чрезвычайно трудную проблему бесконечной регрессии.
Теоретическая модель фон Неймана абсолютно точно отображает механизм самовоспроизведения живых организмов.
В каждой клетке есть символический каркас (ДНК), содержащий закодированные инструкции по репродукции новых клеток. Однако в ДНК нет описания самой ДНК. Та ДНК, которая появляется в новой клетке, представляет собой результат копирования (двойная спираль ДНК делится на две части, а ферменты создают две точные копии исходной ДНК). Подобно тому как машина фон Неймана прочитывает макет двумя способами, ДНК также ведет себя по-разному в процессе воспроизводства живой клетки. Она служит инструкцией для построения клеток, а затем делится и воспроизводит свою вторую половину из окружающей среды каждой новой клетки. По сути это означает, что информационная, или символическая, составляющая ДНК настолько активна, что способна создать свой отпечаток в окружающей среде.
Конвей не сомневался в том, что клеточные существа рано или поздно оживут, он ломал голову над тем, как в искусственном мире клеточных существ создать аналог персонального компьютера. Внутренняя схема компьютера на базовом уровне состоит из следующих компонентов: проводники, логические элементы и регистр памяти. Генератор тактовых импульсов порождает электронные импульсы, представляющие двоичные числа. Наличие импульса – это 1, а его отсутствие – 0. Все логические элементы выполняют операции трех базовых типов: НЕ, И и ИЛИ. Конвей сконструировал конфигурации, имитирующие логические элементы для таких операций. Он показал, что можно сделать так, чтобы потоки глайдеров меняли направление движения, что моделировало изгибы проводников. Конвей также продемонстрировал, как сделать потоки глайдеров разреженными, чтобы два потока могли пересечься, избежав при этом столкновения глайдеров, что изображало пересечение проводников. Кроме того, он показал, как сделать регистр памяти из блоков. Каждый блок представляет собой какое-то число, в зависимости от его расстояния от определенной точки. Глайдеры, которые врезаются в блок, перемещают его ближе к этой точке или дальше от нее, меняя значение блока. Конвей доказал, что игра, ставшая его математическим хобби, теоретически способна имитировать любой существующий в нашем мире компьютер. Получив приведенное выше доказательство, Джон Конвей потерял интерес к игре. Однако Пол Чэпмен решил, что работу необходимо продолжить, ведь
На рубеже столетий он построил компьютер внутри игры. Игровая имитация компьютера имела «железо» и «программы». Первое – конфигурация устойчивых фигур, с которыми сталкиваются динамические фигуры, перемешиваются с другими динамическими структурами и перемещаются по всей системе. Процесс напоминает игру в одну из разновидностей бильярда. В регистр входа поступал сигнал, означающий величину 1, и сигнал, означающий величину 2. Система состояла из нескольких миллионов живых клеток и программы, содержащей инструкции по поводу того, как вычислить сумму 1 + 2. В конце концов блок в регистре вывода показывал число 3. Пол Чэпмен был в восторге. Он вспоминал:
Все эти достижения внушают оптимизм, но остаются загадочными сами основы «жизни». Чтобы разобраться в «механике жизни», Стивен Вольфрам первым в восьмидесятых годах глубоко изучил самые простые одномерные клеточные автоматы. Он обладал необычайными математическими способностями, рано начал научную карьеру, опубликовав свою первую исследовательскую работу еще во время учебы в Итоне в 1970-х. Когда ему исполнилось немногим более двадцати лет, он уже работал в Институте перспективных исследований в Принстоне. Вольфрам разработал язык программирования, который лег в основу системы компьютерной алгебры Mathematica – пакета программ, позволяющих чертить кривые и решать уравнения. В настоящее время она широко используется в сфере образования и разных отраслях экономики. С 1987 года Вольфрам возглавил компанию Wolfram Research, которая благодаря успеху системы Mathematica дала ему возможность проводить собственные научные исследования независимо от университетов. Все свое свободное время он посвятил исследованию так называемых линейных автоматов. Линейный автомат – это такой клеточный автомат, полем в котором служит кольцо толщиной в одну клетку. Следующее поколение получается из предыдущего и отображается под всей структурой. Таким образом, мы имеем плоскость, по одной оси которой единственная пространственная координата, а по другой – время, в результате чего мы можем просмотреть всю эволюцию популяции. Правила автомата довольно просты – они похожи на правила «Жизни» в одномерном случае:
• если над исследуемой клеткой количество соседей равно 3, клетка рождается;
• если над клеткой соседей меньше 2, то она «умирает».
Правило жизни в линейном автомате. Показаны восемь возможных комбинаций клетки и двух ее соседей. Под каждой комбинацией изображено состояние клетки после смены поколения. В первой комбинации живая клетка находится в окружении двух живых соседних клеток. Значит, в следующем поколении она умрет. Вторая комбинация содержит живую клетку слева и мертвую справа, стало быть, средняя клетка останется в следующем поколении в живых. Если две соседние клетки одинакового цвета, внизу будет получена белая клетка. Если разного, нижняя клетка будет черной
Начнем фиксировать эволюцию одномерного клеточного автомата с одной живой клетки (поколение 0). Согласно описанным правилам на следующем ряду (поколение 1) мы обнаружим две живых клетки и одну мертвую клетку между ними. Затем, применив это правило к каждой клетке данного ряда, получим следующий новый ряд (поколение 2), и т. д. В процессе развития такой популяции получается структура, идентичная «салфетке Серпинского»!
«Правило 90»: эволюция линейного автомата
Вольфрам определил, что существует 2x2x2 = 8 комбинаций клетки и ее соседей, а также два возможных состояния (живая или мертвая клетка), а значит, есть 28 = 256 разных наборов «генетических правил» для одномерных клеточных автоматов. Эти правила он пронумеровал от 1 до 256. На представленном выше рисунке показано «правило 90», порождающее упорядоченные фигуры. Другие правила, такие, как «правило 30», более причудливы. Это правило, а также конфигурация, которую оно порождает начиная с одной живой клетки, проиллюстрировано на рисунке далее. Данная конфигурация представляет собой совокупность упорядоченных и хаотичных фрагментов. Зигзагообразная корка на левой боковой поверхности демонстрирует упорядоченность. Однако по мере передвижения направо мы видим неупорядоченную бугристую поверхность, состоящую из треугольников самых разных форм и размеров. Когда Вольфрам увидел «правило 30», он был поражен тем, что такое простое правило способно сгенерировать столь сложную конфигурацию, и высказался эмоционально:
Вольфрам был поражен. Он внимательно проанализировал колонку, расположенную под исходной живой клеткой.
«Правило 30»: его генетические законы, его эволюция после 50 поколений и эволюция после более 200 поколений (А. Беллос. «Красота в квадрате. Как цифры отражают жизнь и жизнь отражает цифры») в первом ряду. Если взять за основу то, что живая клетка – это 1, а мертвая – 0, то эта колонка состояла из таких клеток:
1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0...
«Правило 30»: его генетические законы, его эволюция после 50 поколений и эволюция после более 200 поколений (А. Беллос. «Красота в квадрате. Как цифры отражают жизнь и жизнь отражает цифры»)
В этом не было никакой закономерности. К большому удивлению Вольфрама, стандартные статистические тесты показали, что это абсолютно произвольная последовательность. «Правило 30» полностью детерминировано, однако конфигурация ячеек в центральном столбце настолько непредсказуема, что ее невозможно отличить от последовательного подбрасывания монеты. Вольфрам запатентовал «правило 30» как генератор псевдослучайных чисел и применил его в продукте Wolfram Research – Mathematica. Также это правило было предложено для использования как шифратор последовательностей в криптографии. Однако Сиппер и Томассини показали, что «правило 30» плохо проходит тест на критерий согласия Пирсона (критерий χ2) в сравнении с другими псевдослучайными последовательностями, которые были получены при помощи других клеточных автоматов.
Порядок из хаоса. Все начинается с произвольного заполнения первого ряда клеток, которые в процессе работы клеточного аппарата спонтанным образом производят упорядоченные образования с долгосрочными корреляциями (в данном случае фракталы Серпинского). См.: Пол Девис. Новые открытия творческой способности природы к самоорганизации. М., 2011
Вольфрам открыл следующее:
Таким образом, энтропия в процессе эволюции сложного клеточного автомата может сокращаться, а порядок может спонтанно возникать из беспорядка. В этом смысле клеточный аппарат моделирует поведение диссипативных структур Пригожина, в которых порядок появляется из хаоса. Вольфрам и его коллеги утверждают:
Клеточные автоматы – это дискретные математические модели, в которых простые локальные правила генерируют неожиданно сложное поведение в более крупном масштабе. Вольфрам – один из главных сторонников той точки зрения, что клеточные автоматы – не только увлекательная математическая игра, но и способ объяснить сложность физического мира. Мысли Вольфрама по этому поводу изложены в книге «А New Kind of Science» («Новый вид науки»), которую он опубликовал на свои средства в 2002 году. В частности, в ней Вольфрам утверждает, что информация, полученная благодаря анализу «правила 30», открывает новую научную парадигму примирения порядка и хаоса. Правило представляет интерес, потому что оно порождает сложные, во многих отношениях случайные структуры из простых, четко определенных правил. Вольфрам полагает, что клеточные автоматы в целом и «правило 30» в частности – ключ к пониманию того, как простые правила могут порождать сложные структуры и различное сложное поведение разных природных объектов. В своей книге он задается фундаментальным вопросом о структуре Вселенной и дает неожиданный ответ:
Вне пространства и времени существует символическая реальность. В начале книги я говорил, что необходимо изменить наши представления о реальности так, чтобы признать символ столь же реальным и весомым как вещество и действие. Символ существует вне пространства и вне времени, но он структурирует материю и упорядочивает ее поведение в пространстве и времени. Собственно само пространство и само время есть символические качества, которые доступны нам благодаря шестому чувству – сознанию. Сознание – это такое чувство, которое позволяет воспринимать и различать символы. Символы благодаря своему рациональному и чувственному воздействию формируют реальность, которая поддерживает и производит символический строй.
