Оригинал материала находится по адресу www.computerra.ru/think/sentinel/33717/
21.05.2004
Мир в клеточку (о клеточных автоматах)
Есть в информатике такая замечательная штука - клеточный автомат (КА; в английском варианте cellular automata). Несколько упрощая, клеточный автомат можно представить как множество ячеек, каждая из которых может принимать некоторое конечное значение и меняться со временем согласно заранее определённым правилам, находясь в прямой зависимости от состояния соседних ячеек и текущего момента времени. Сформулировал идею клеточных автоматов ещё Джон фон Нейман в середине прошлого века. Помните игру "Жизнь" или популярных одно время тьюрмитов? Это, пожалуй, самые известные примеры КА, но не самые простые: поле "Жизни" двумерно, а есть и одномерные КА. Простейшим образчиком (его ещё называют элементарным) является строка ячеек, хранящих только "нолики" и "единички", состояние которых в каждый последующий момент времени изображается ещё одной строкой ниже - так, как это изображено на следующих рисунках.
В зависимости от правил (первый рисунок) и начального состояния КА форма образующейся структуры может быть чрезвычайно сложной и совсем не обязательно симметричной. Всего из одной точки можно получать фантастические фрактальные узоры, глядя на которые совсем нетрудно поверить, что за внешней простотой идеи клеточных автоматов скрываются невероятная сложность и необозримые и непредсказуемые перспективы. Клеточные автоматы, долгое время остававшиеся математической забавой, подвергли тщательному изучению лишь в конце XX века. Тогда и выяснилось, что всего существующего математического аппарата недостаточно, чтобы описать их поведение.
Демонстрация потенциала клеточных автоматов неразрывно связана с именами классика ИТ Конрада Цузе и нашего современника Стивена Вольфрама (косвенно он знаком каждому из вас - как автор знаменитого пакета Mathematica и (прим. 2015 года) поисковой системы Wolfram Alpha). Их исследования во многом пересекаются, но несмотря на то, что Цузе вёл их на добрых два десятка лет раньше, именно Вольфрам сумел изложить суть изысканий популярно и привлечь к ним внимание широкой общественности своей книгой "A New Kind of Science" (2002).
Так вот, один из самых интересных моментов в теории КА заключается в предположении, что, поскольку предсказать конечное состояние некоторых форм клеточных автоматов математика не в состоянии (необходимо просчитывать каждый шаг их эволюции), то такие образования могут сыграть роль нового инструмента познания мира. Сегодня вся физика основывается на математике, но Вольфрам предполагает, что положив в основу моделей природных систем не системы уравнений, а простые абстрактные системы (читай: клеточные автоматы), можно, тем самым, отыскивать новые подходы к старым и ещё нерешённым научным проблемам и совершать новые открытия.
Идея, прямо скажем, смелая, но не спешите причислять её сторонников к сумасшедшим: попытки практической реализации уже имеются. На днях Пол Рейнерс, исследователь из компании IBM, опубликовал статью, посвящённую написанной им программе Automatous Monk, которая использует клеточные автоматы для генерации нотных последовательностей. Попросту программа Рейнерса транслирует таинственным образом упорядоченные картины, рождаемые КА, в музыку.
По мелодичности такие произведения пока далеки от рукотворных композиций, но Рейнерс точно подмечает: пользователь вправе надеяться наткнуться здесь на новые музыкальные идеи. Automatous Monk - почти чистая реализация предложения Вольфрама. И кто знает, кто станет автором следующей? Возможно, вы?
P.S. В продолжение темы: «Увлекательная жизнь клеточных автоматов, или Как в «Жизни» «Тетрис» запустили» и «Эксперименты с бит-реверсивными паттернами».
клеточный_автомат,тьюрмит,игра,Жизнь,Конрад_Цузе,проблема_останова,машина_Тьюринга