SCI-GAMES-CLUB: Scientific American

Занимательный компьютер "В МИРЕ НАУКИ" 1988/#10 "Перемешивающая машина" -- клеточный автомат, моделирующий химические реакции А. К. ДЬЮДНИ Клеточные автоматы -- компьютерные модели, основанные на массивах клеток, волной распространились в физике, математике и других науках. Теперь появилась новая разновидность клеточного автомата, которая сама в буквальном смысле порождает волны. Названная ее изобретателями "перемешивающей машиной" (hodgepodge machine), она моделирует химические реакции с такой точностью, которая редко достигается в других моделях. Реакции, моделируемые этой машиной, происходят в активной химической среде, где два вещества (или больше) могут диссоциировать или рекомбинировать в присутствии катализатора. Если реагирующие вещества имеют различный цвет, то в таких средах можно наблюдать волнообразные структуры, которые, распространяясь постоянно, изменяют фронт с простым или сложным очертанием. Может ли сам по себе автомат послужить адекватным физическим объяснением волнового процесса, действительно наблюдаемого в ходе реакции? Этот вопрос занимает сейчас изобретателей "перемешивающей машины" М. Герхардта и Х. Шустер из Билефельдского университета в ФРГ, а также многих других исследователей из различных университетских центров. Клеточный автомат можно представить в виде бесконечной решетки квадратных клеток, состояние которых меняется со временем в такт дискретным сигналам воображаемого часового механизма. На каждом временном такте каждая клетка находится в одном из конечного множества состояний. Состояние клетки на такте t+1 достаточно несложным образом зависит от состояния клеток в ее непосредственной окрестности на предыдущем такте t. Эта зависимость выражается в виде набора правил, одинаково применимых ко всем клеткам решетки. При последовательном применении правил на каждом такте часового механизма произвольная исходная конфигурация состояний клеток может изменяться и, таким образом, эволюционировать во времени. Иногда в процессе таких последовательных изменений можно наблюдать, как создаются чрезвычайно интересные структуры. В результате возникает убеждение, что при правильной исходной конфигурации клеточный автомат может породить нечто самоорганизующееся, способное к росту и воспроизводству -- короче, нечто "живое". ... Перемешивающая машина представляет собой целое семейство клеточных автоматов. Конкретную версию можно выбрать, указав значения ряда параметров, таких, например, как количество возможных состояний. Если количество состояний равно n+1, то каждое возможное состояние клетки можно представить числом в диапазоне от 0 до n. Герхардт и Шустер расширили метафору Конвея при описании состояний их машины. Клетка в состоянии 0 считается "здоровой", а в состоянии n -- "больной". Все промежуточные состояния соответствуют той или иной степени "зараженности", в зависимости от номера состояния -- чем ближе номер состояния клетки к числу n, тем в большей степени она "заражена". Перемешивающая машина избирательно применяет одно из трех правил к каждой клетке, в зависимости от того, здорова она, заражена или больна. Если клетка здорова (другими словами, находится в состоянии 0), то на следующем такте она перейдет в новое состояние, зависящее от числа зараженных клеток A и числа больных клеток B среди ее непосредственных соседей, а также от двух параметров, которые мы обозначим k1 и k2. Точнее, состояние клетки на моммент времени t+1 определяется следующей формулой: [A / k1] + [B / k2]. Здесь квадратные скобки обозначают операцию округления того дробного числа, которое в них заключено. Если, например, A/k1 окажется дробным 2,725, то квадратные скобки сведут это число к 2. Если формула даст нулевое значение, то клетка, конечно, останется здоровой -- по крайней мере пока. Если клетка заражена, ее состояние со временем обычно ухудщается. Состояние зараженной клетки на момент времени t+1 вычисляется как сумма двух чисел: степени заражения клеток в окрестности на момент t и постоянной величины g, регулирующей скорость распространения инфекции среди клеток. Первая величина -- степень заражения клеток в окрестности -- получается делением числа S, суммы состояний самой клетки и ее соседей, на A -- число зараженных соседей. Таким образом, клетка, зараженная на момент времени t, принимает в момент t+1 состояние, вычисляемое по следующей формуле: [S / A] + g. Однако зараженная клетка не может стать "больнее" n. Если значение, полученное по формуле, превысит n, то в качестве номера следующего состояния клетки принимается n. Наконец, если на момент времени t клетка больна (находится в состоянии n), то она чудесным образом выздоравливает (принимает состояние 0) в момент t+1. ... При заданных трех правилах и определенном типе окрестности клетки клеточный автомат Герхардта--Шустер можно полностью определить, указав значения четырех параметров: n -- числа возможных состояний минус 1; k1 и k2 --"весовых" параметров для здоровья клеток и g -- скорости распространения инфекции. ... В малых значениях параметра g машина не демонстрирует ничего интересного. За исключением нескольких начальных флуктуаций, активные процессы в клетках имеют тенденцию к затуханию, клетки становятся здоровыми и навсегда остаются в этом состоянии. Однако с ростом g автомат начинает вести себя необычно. Среди множества возможных состояний в этом случае можно выделить несколько типичных. Начнем с того, что большинство клеток становятся зараженными и, как правило, они остаются в зараженном состоянии, хотя время от времени возникают случайные во времени и пространстве конфигурации здоровых клеток. Такое поведение автомата Герхардт и Шустер условно назвали поведением типа 1. Следующий тип поведения, который они наблюдали, был обозначен как тип 2. Он характеризуется обычно регулярными последовательностями зараженного состояния, образующими "плато" длительностью примерно 30 циклов, которые неожиданно сменяются появлением большого количества здоровых клеток. (Иногда почти все 400 клеток внезапно выздоравливают, но затем сразу же начинается новая волна инфекции.) По мере дальнейшего роста значений параметра g начинает проявляться поведение третьего типа. Оно характеризуется возникновением весьма регулярного чередования между насыщением и фактическим исчезновением зараженных клеток приблизительно через каждые 20 циклов. И наконец, для четвертого типа поведения характерно то, что после первых нескольких циклов количество зараженных клеток начинает колебаться с некоторой регулярностью около насыщающего значения, равного примерно 75%. ... Для каждого из описанных четырех типов поведения характерны свои волновые структуры... Некоторые типы волн, генерируемые перемешивающей машиной, аналогичны волнам, наблюдаемым в определенных химических системах, в частности, машина порождает волны, являющиеся точной копией волн, которые возникают в ходе известной реакции Белоусова-Жаботинского .., в ходе которой малоновоя кислота окисляется броматом калия в присутствии катализатора, такого как церий или железо. Клетки решетки представляют по существу частицы катализатора, а метафора "зараженного" состояния отражает явление постепенного насыщения поверхностей этих частиц. ... Благодаря взаимодействию между соседними клетками перемешивающей машины у них появляется возможность синхронизировать свою активность. После некоторого начального периода случайной дезорганизации (фазы "перемешивания") в поведении машины начинает проявляться синхронность. То же самое, как можно предположить, справедливо и в отношении реальных химических реакций. Объясняет ли, таким образом, перемешивающая машина появление волн в ходе реакции, которую она моделирует? ... Герхардт и Шустер не утверждают, что все химические реакции имеют клеточную природу. Они рассматривают свой автомат лишь как инструмент, позволяющий получить некое приближение к реальности, как дискретную версию дифференциального уравнения в частных производных. ... Создатели машины хотят показать, что массив "химических осциляторов", взаимодействующих между собой согласно некоторым простым правилам, бедет неизбежно генерировать волны. Предположительно существует лишь небольшое число возможных волновых структур, хотя, по мнению Дж. Тайсона (из Политехнического института), при переходе к трем измерениям они становятся значительно более сложными. В связи с тем что трехмерные волновые фронты значительно труднее наблюдать в лабораторных условиях, компьютерные модели могут помочь химикам в их поисках.