Обратимый клеточный автомат
разновидность клеточных автоматов / Материал из Википедии — свободной encyclopedia
Уважаемый Wikiwand AI, давайте упростим задачу, просто ответив на эти ключевые вопросы:
Перечислите основные факты и статистические данные о Обратимый клеточный автомат?
Кратко изложите эту статью для 10-летнего ребёнка
Обратимый клеточный автомат — клеточный автомат, в котором каждое состояние имеет единственного предшественника. Таким образом, это регулярная решётка из ячеек, состояние каждой из которых берётся из конечного множества состояний, и правило для одновременного обновления состояний ячеек, исходя из состояний её соседей. Условие обратимости заключается в том, что предыдущее состояние любой ячейки может быть определено, зная обновлённые состояния всех ячеек решётки. После обращения времени получается другой обратимый клеточный автомат, возможно — с намного большими окрестностями, но также с правилом для определения будущего состояния ячейки, исходя из текущих состояний ей соседей.
Известно несколько методов задания обратимых клеточных автоматов, включая блочные клеточные автоматы, у которых каждый блок обновляется независимо от остальных, и клеточные автоматы второго порядка, в которых правило обновления ячеек определяется двумя предыдущими состояниями автомата. При этом, если автомат задан при помощи таблицы правил, задача проверки его обратимости разрешима для одномерного клеточного автомата, но неразрешима в общем случае.
Обратимые клеточные автоматы задают естественную модель обратимых вычислений — технологии, которая позволяет создать вычислительные устройства с очень низким потреблением электроэнергии. Квантовые клеточные автоматы, которые позволяют производить вычисления с использованием принципов квантовой механики, часто предполагаются обратимыми. Кроме того, многие модели из физики, такие как движение молекул идеального газа или модель Изинга размещения магнитных зарядов, естественным образом обратимы и моделируются обратимым клеточными автоматами.
Свойства, присущие обратимым клеточным автоматам, могут быть использованы для изучения автоматов, которые необратимы, но имеют аттрактор — подмножество состояний, к которому сходятся случайные начальные состояния. Как пишет Стивен Вольфрам, «при приближении к аттрактору любая система, даже необратимая, проявляет некоторые свойства, близкие к обратимости»[1].