Коллайдер из клеточного автомата производит вычисления

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

Одним из наиболее интересных объектов, возникающих в игре "Жизнь", двухмерном клеточном автомате, являются глайдеры - совокупности клеток, которые перемещаются как единое целое. Движение глайдеров можно рассматривать как передачу информации (информация в данном случае - конфигурация глайдера). В результате столкновений других конфигураций клеток с глайдерами первые могут смещаться либо уничтожаться, или могут образовываться устойчивые конфигурации (например, глайдерные пушки, которые "стреляют" новыми глайдерами). Все эти операции можно рассматривать, как вычисления, и у математиков не заняло много времени доказательство равносильности "глайдерных" вычислений машине Тьюринга.








Глайдерная пушка

Эта идея привлекала внимание многих компьютерщиков и математиков. Известный ученый, создатель программы Mathematica Стефан Вольфрам (Stephen Wolfram) описал способности клеточных автоматов к вычислениям в своей книге "Новый тип науки" ("A New Kind of Science"), в которой он высказывает идею, что исследование клеточных автоматов может стать отдельной научной дисциплиной.

В последнее время интерес к клеточным автоматам несколько поутих. Но вот недавно Генаро Мартинез (Genaro Martinez) из Университета западной Англии, Бристоль, вместе с коллегами объявил о создании целого глайдерного "циклотрона", который может производить довольно сложные вычисления.


Пример столкновения двух глайдерных "частиц" с рождением третьей. По горизонтали - состояния клеток, по вертикали - временная развертка.

Ученые работают с одномерным клеточным автоматом, пространство которого замкнуто в кольцо. Клетки, как и в игре "Жизнь", могут находится в одном из двух состояний: либо занятым "частичкой", либо свободном. Подчиняясь правилам перехода, клетки и их конфигурации смещаются, образуя глайдеры, обладающие различной скоростью. Именно на движении и столкновении этих частиц, которые могут образовывать сложные циклические структуры, и основаны вычисления в новой модели. Авторы показали, что их система способна производить базовые операции со строками (строкой является набор глайдеров): добавление одной строки в конце другой, инвертирование строки и др.

В чем же преимущество подобных вычислений, стоит ли ими заниматься?

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

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

Авторы считают, что глайдерные "циклотроны" можно реализовать в реальных физических и химических системах, таких как цепочки реакций полимеризации, и уже принялись за ее реализацию.