Техника - молодёжи 2001-05, страница 20

и

П Р А К

И К

И Г

Алексей ЛЕБЕДЕВ, кандидат физико-математических наук

ВИМЙНЕ

НЛЕШВНЫЙ

Всем известны игры для двух или более игроков. Существуют и игры для одного — например, пасьянс. А возможны ли игры совсем без игроков? Оказывается, да! В них все происходит «само собой». Точнее говоря, человек может принять участйе в такой игре, но только для выбора исходной позиции, а далее — как простой исполнитель правил (последнее можно поручить и компьютеру).

К «ИГРАМ БЕЗ ИГРОКОВ» ОТНОСЯТСЯ так называемые «клеточные автоматы», о которых и пойдет речь в дальнейшем. Чтобы понять смысл этого научного термина,, представим себе плоскость, расчерченную на одинаковые клетки (вроде бесконечной тетрадной страницы). Каждая клетка может быть в нескольких состояниях — в простейшем случае их два: нуль и единица, белое и черное. Клетка автоматически меняет свой цвет (состояние) в соответствии с изначально заданными правилами игры, обычно в зависимости от состояний «соседок» (то есть ближайших к ней восьми клеток). Время предполагается дискретным, то есть выражается целым числом «шагов», или «ходов», как это обычно и бывает в играх. Все клетки меняют свои состояния одновременно.

Уже классическим примером клеточного автомата стала игра «Жизнь», изобретенная Джоном X. Конвеем, математиком Кембриджского университета. Правила у нее такие:

1. Если клетка «белая», то она становится «черной» тогда и только тогда, когда три ее соседки «черные».

2. Если клетка «черная», то она становится «белой» тогда и только тогда, когда меньше чем две или более чем три ее соседки «черные».

В 1969 г. Конвей открыл в своей игре небольшую устойчивую конфигурацию, которую он назвал «планером» (рис.1). Эта фигура принимает свою исходную форму каждые 4 хода, сдвигаясь на одну клетку по диагонали. На экране компьютера планер выглядит, как маленький зверек, который ползет, виляя хвостиком.

Позже, в 1970 г., студент Массачусетсского технологического института РГос-пер открыл «катапульту» — конфигурацию из клеток, «стреляющую» планерами через каждые 30 ходов.

В игре «Жизнь» существуют также конфигурации, совсем не меняющиеся во времени или меняющиеся

шпмиш

периодически (не двигаясь с места) — последние именуются «циклами» Простейший из них (рис.2) обычно называют «семафором».

С тех пор придумано множество различных автоматов подобного рода (задаваемых набором правил), поведение которых оказывается интересным и разнообразным в большей или меньшей степени.

Рассматриваются и одномерные автоматы, которые задаются уже не на плоскости, а на полосе (толщиной в одну клетку) Новое состояние клетки при этом может зависеть не только от двух ближайших, но и от более удаленных ее соседок.

ИНТЕРЕС УЧЕНЫХ К КЛЕТОЧНЫМ АВТОМАТАМ — не просто забава для ума или праздное любопытство. Такие игры, например, имеют прямое отношение к разработке электронных схем компьютеров будущего. В частности, доказано, что игра «Жизнь» эквивалентна (в некотором смысле) универсальной вычислительной машине. Потоку двоичной информации можно поставить в соответствие поток «планеров», следующих один за другим. Наличие очередного «планера» в потоке означает единицу, отсутствие — нуль. Можно также составить конфигурации, выполняющие все основные логические операции.

Полагают также, что наблюдения за клеточными автоматами помогут лучше понять такие явления, как турбулентность в потоках жидкости или газа, рост кристаллов и др.¹. Фундаментальные исследования в этой области обогащают теорию самоорганизации и структур в нелинейных средах². С помощью клеточных автоматов можно моделировать различные физические, химические, биологические и информационные процессы³.

Так, Г.Г. Малинецко-му и М.С. Шакаевой удалось смоделировать (на качественном уровне) автоколебательные химические реакции типа знаме

нитой реакции Белоусова — Жаботин-ского и, в частности, получить решения типа «спиральных волн». Такие волны реально наблюдаются в тонком слое реакционной смеси (раствор периодически меняет цвет с синего на красный). Заметим также, что колебательные реакции являются основой всех биологических ритмов, включая биение сердца и волны мозговой активности.

Что касается упоминавшихся выше применений в вычисли-_ тельной технике, то уже сконструированы некоторые ЭВМ, по своей архитектуре напоминающие клеточные автоматы. В числе первых можно назвать машину, созданную Т.Тоффоли и Н.Марголусом⁴. По скорости вычислений она сравнима с компьютерами типа Cray-1.

Клеточные автоматы можно использовать и как аргументы в философских дискуссиях. Например — может ли возникнуть порядок из хаоса? Оказывается — да! Во многих играх из первоначального хаотического состояния со временем образуются упорядоченные, стабильные или периодические структуры. Очевидно, источником порядка здесь служат сами правила игры, своего рода «законы природы» клеточного мира, однако они могут быть очень просты, а структуры, порождаемые ими, — весьма сложны и заранее не известны.

Некоторые мыслители заходят еще дальше. Так, С.Я. Беркович развивает теорию⁵, согласно которой вся Вселенная представляет собой большую игру многомерный клеточный автомат, в котором элементарные частицы суть аналоги конвеевских «планеров» и т.п. При всей экстравагантности подобного взгляда на мир, все же не будем отвергать его с порога. В конце концов, квантовая механика — тоже довольно странная штука, к которой в свое время весьма скептически относился сам Эйнштейн...

ОДНАКО ВЕРНЕМСЯ К НАШИМ ПРОСТЫМ ИГРАМ на плоскости, вполне доступным не только корифеям науки, но и простым читателям.

Много лет назад, впервые увлекшись клеточными автоматами и рисуя их на страницах тетрадей в клеточку я придумал свою игру с более простыми, чем у Конвея, правилами. Вот они:

1. Если клетка «черная», то она становится «белой».

ТЕХНИКА-МОЛОДЕЖИ 5 200 1

18