Сотовые автоматы

Изучение клеточных автоматов является захватывающим новым направлением математических и научных исследований.

Факт, в «Новом виде науки» математик Стивен Вольфрам утверждает, что исследование сложности, возникающее в результате рассмотрения клеточных автоматов, является отправной точкой для новой научной революции. Хотя я не пошел бы так далеко, я нахожу их захватывающими.

Клеточный автомат (CA) — это набор ячеек с состояниями, которые развиваются в соответствии с набором детерминированных правил. Простейшие клеточные автоматы имеют ячейки с двумя возможными состояниями, включенными и выключенными, и развиваются по очень простым правилам, обычно с участием соседних клеток. Вольфрам исследовал все 256 одномерных клеточных автоматов с двумя состояниями, которые развиваются по правилам ближайшего соседа. Затем он разделил эти машины на четыре класса в зависимости от типа поведения, которое они демонстрируют. Сотовые машины класса 1 в конечном итоге переходят в состояние, когда все ячейки выключены или включены. Сотовые машины класса 2 эволюционируют в предсказуемый паттерн, то есть чередуются на и на клетках. Клеточные аппараты класса 3 показывают случайное поведение. Наконец, сотовые машины класса 4, которые являются наиболее интересными, эволюционируют в состояния, демонстрирующие неслучайную, но, тем не менее, непредсказуемую структуру. Вольфрам считает, что сотовые машины класса 4 похожи на машины Тьюринга и поэтому могут обладать универсальными вычислительными возможностями.

Самым известным СА является игра жизни Конвея. Это двумерный CA с двумя состояниями, играемый на бесконечной квадратной сетке. Правила очень просты. Ячейка с двумя или тремя из восьми ближайших соседей остается в следующем поколении, в противном случае она отключается, а в следующем поколении она отключается вместе с тремя ближайшими соседями, в противном случае она остается выключенной. Эти простые принципы создают удивительно сложные структуры, включая натюрморты (шаблоны, которые не меняются), осцилляторы (шаблоны, которые повторяются), космические корабли (модели, которые движутся) и множество сложных моделей, которые испытывают регулярный неограниченный рост. В 1982 году Конвей показал, что Game of Life поддерживает машины Тьюринга, а первая была построена в 2002 году.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock
detector