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

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

В этой игре я открыл конфигурации, аналогичные по свойствам конвеевским «планерам», которые я назвал «самолетами» (рис. 3 а, б). Они воспроизводят себя на каждом шагу, сдвигаясь на клетку вдоль оси симметрии (в данном случае — вправо).

Конфигурацию, воспроизводящую себя через два хода (цикл-2), я назвал «пропеллером» (рис.4) — кажется, будто она крутится. Проверить эти свойства читатель легко может самостоятельно. Заметим, что в силу первого правила неизменных конфигураций (кроме бесконечной «белой» плоскости) в данной игре быть не может.

Простую модель автоколебательной среды можно построить на основе автомата с тремя возможными состояниями (0,1 и -1) и следующими правилами:

1. Клетка в состоянии 0 переходит в состояние 1 тогда и только тогда, когда имеет хотя бы одну соседку в состоянии 1.

2. Клетка в состоянии 1 переходит в состояние -1.

3. Клетка в состоянии -1 переходит в состояние 0.

В такой игре существуют разбегающиеся незатухающие волны на плоскости (рис.5; серым цветом обозначено состояние -1).

Простейшим источником таких волн является «генератор» из двух клеток (рис.6), повторяющий себя через каждые 3 хода.

УЖЕ ТРАДИЦИОННОЙ СТАЛА КЛАССИФИКАЦИЯ клеточных автоматов по результатам их поведения. Так, эволюция автоматов первого класса приводит к пространственно-однородным состояниям (например, полному «вымиранию»). Эволюция автоматов второго класса приводит к простым периодическим по времени структурам. Автоматы третьего класса порождают непериодические конфигурации. Наконец, клеточные автоматы четвертого класса демонстрируют довольно сложное поведение с различными локализованными и перемещающимися структурами³. Наиболее интересен для исследователей как раз последний класс, и игра «Жизнь» относится именно к нему.

Однако можно вводить и другие классификации. Например, традиционно называя клетки в состоянии 1 и 0 «живыми» и «мертвыми» соответственно, можно задаться вопросом: насколько «благоприятны для жизни» правила той или иной игры?

В своей работе⁶ автор этих строк ограничивался рассмотрением игр на плоскости при следующих условиях:

1 Каждая клетка может находиться в одном из двух состояний (0 или 1).

2. Новое состояние клетки определяется ее старым состоянием и суммой состояний восьми ее соседей.

3. Если клетка и все ее соседи находятся в состоянии 0, то клетка остается в этом состоянии.

Поскольку обычно эволюция системы существенно зависит от исходной конфигурации, то для «усреднения» этой зависимости используем случайные начальные условия. А именно, пусть в начальный момент каждая клетка плоскости независимо от остальных находится в состоянии 1 с вероятностью р и 0 — с вероятностью 1 -р( где р — число от 0 до 1). Тогда средняя доля «живых» также будет равна р. На следующем шаге она будет равна некой функции f(p), которая вычисляется методами теории вероятности. Теперь можно посмотреть — увеличилась доля «живых» или, наоборот, уменьшилась? Автоматы, где она увеличивается при любом р (кроме, может быть, конечного числа точек), были названы строго благоприятными, где уменьшается — строго неблагоприятными.

К сожалению, большинство игр не попадают ни в одну из этих категорий, поскольку при разных р ведут себя по-разному. Однако «коэффициент размножения» f(p)/p можно усреднить по р от 0 до 1. Так получается более универсальный, количественный, показатель Q В зависимости от того, больше он или меньше единицы, можно назвать игры благоприятными или неблагоприятными в среднем. Например, для игры «Жизнь» получено Q=4/9, и она оказывается неблагоприятной в среднем, но не строго неблагоприятной.

Общее число возможных игр, удовлетворяющих условиям, равно 2¹⁷=131072. Расчеты, проведенные на компьютере, показывают, что 95668 (73%) из них — благоприятны в среднем, 256 (0,2%) — нейтральны в среднем (то есть Q=1) и 35148 (26,8%) — неблагоприятны в среднем. Минимальное Q равно нулю, максимальное 2,829..., среднее 1,414...

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

В ЗАКЛЮЧЕНИЕ СКАЖУ, что каждый читатель может приобщиться к миру клеточных автоматов и попробовать сыграть в одну из описанных выше игр или придумать свою, по

аналогии — для этого не обязателен компьютер, достаточно иметь под рукой карандаш и клетчатую бумагу. Создайте свою собственную вселенную! Задайтесь какой-нибудь исходной фигурой, а потом посмотрите, во что она превратится со временем. Результаты могут быть поистине непредсказуемы... □

ПРИМЕЧАНИЯ

¹ Уолфрэм С. Программное обеспечение научных исследований // В мире науки. 1984. №11. С. 98 — 110. ДьюдниА.К. Построение одномерных компьютеров помогает глубже понять некоторые сложные явления // В мире науки. 1985. №7. С. 108 — 113.

² Курдюмов С. П. и др. Структуры в нелинейных средах // Компьютеры и нелинейные явления. М.. Наука, 1988. С. 5 —43.

³ Малинецкий Г.Г., Ша-каева М.С. Клеточные автоматы в математическом моделировании и обработке информации. М.: ИПМ, 1994.

⁴Тоффоли Т., Марголус Н. Машины клеточных автоматов. М.: Мир, 1991.

⁵Беркович С.Я. Клеточные автоматы как модель реальности: поиски новых представлений физических и информационных процессов. М.: МГУ, 1993.

⁶Лебедев А.В. Вероятностная классификация клеточных автоматов // Фундаментальная и прикладная математика (в печати). ■

ПАТЕНТ НА... МЫШЛЕНИЕ ^

Особенностями американского патентного _Q законодательства уже не раз злоупотребляли. Известна история, когда один остроумный американец чуть было не запатентовал коле- ₀ со. Продолжение следует: глава компании The Brain Хью Харлан запатентовал «код, действие которого имитирует процесс человеческого ^ мышления». Отныне любой процесс, который может быть представлен в виде блок-схемы, ^s где между данными, как-то относящимися гп друг к другу, есть связи, полностью подпадает под это определение, и за его использование в США полагается платить авторские отчисления. Вокруг полно «бесхозных» изобретений. О Скажем, набор печатных букв на бумажном ^ листе(ау, Гуттенберг!) или вот — шнурки на ботинках. Патентовать — не изобретать. J "о

ПЧЕЛ «ЗАВТРАКОМ» КОРМЯТ?

Пчелы существовали за 87 млн лет до по- ° явления цветов. К такому сенсационно- ^ му выводу пришел американский палеобиолог Стефан Хазиотис, нашедший в Ари- ° зоне окаменевший лес, а в нем — сотни zc гнезд, построенных примитивным видом пчел. Несмотря на значительный возраст — ³⁼³ более 200 млн лет — величина и форма гп гнезд, а также расположение ячеек почти идентичны постройкам современных пчел. Чем же они питались? Не обещаниями же j^z Творца создать цветочки «назавтра»... ■ По материалам интернет-изданий подготовил Андрей САМОХИН s:

4

5

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

КЗ