Клеточный автомат
Материал из Википедии — свободной энциклопедии
Кле́точный автома́т — набор клеток, образующих некоторую периодическую решетку с заданными правилами перехода, определяющими состояние клетки в следующий момент времени через состояние клеток, находящимися от нее на расстоянии не больше некоторого, в текущий момент времени. Как правило, рассматриваются автоматы, где состояние определяется самой клеткой и ближайшими соседями. В качестве решетки обычно рассматривается кубическая решетка. Один из самых интересных примеров клеточного автомата — игра «Жизнь».
Основное направление исследования клеточных автоматов — алгоритмическая разрешимость тех или иных проблем. Также рассматриваются вопросы построения начальных состояний, при которых клеточный автомат будет решать заданную задачу.
11-го ноября 2002 года Пауль Чепмен (Paul Chapman) построил образец Жизни, который является РММ (Регистровой Машиной Минского). Фактически РММ эквивалентна машине Тьюринга. Первая версия образца была большой (268,096 живых ячеек на площади 4,558 x 21,469 клеток) и медленной (20 поколений/сек при использовании Life32 Иогана Бонтеса (Johan Bontes) на 400MHz AMD K6-II). Таким образом, в игре Жизнь можно выполнить любой алгоритм, который можно реализовать на современном компьютере.
