ПОИСК Статьи Рисунки Таблицы Обратимые клеточные автоматы из "Машины клеточных автоматов" Клеточный автомат является детерминированной системой, т.е. для каждого возможного состояния всего клеточного автомата правило определяет одно и только одно последующее состояние. Можем ли мы запустить клеточный автомат в обратном направлении , т.е. по заданному правилу сконструировать новое, которое заставит систему проделать ее шаги в обратном порядке Ясно, что в общем случае это возможно, только если система, определенная исходным правилом, к тому же детерминирована в обратном направлении, т. е. если для каждой возможной конфигурации клеточного автомата существует одна и только одна предшествующая. [c.155] В специальных случаях, тем не менее, возможно достичь практически такого же эффекта обратимости во времени за счет выполнения того же прямого правила, что и при прямом направлении времени, но используя в качестве начального состояния для обратного движения состояние, полученное из конечного состояния при продвижении вперед предписанным преобразованием - процедурой транслитерации . [c.155] Динамический закон, обладающий этим свойством, называется инвариантным к обращению времени относительно заданного преобразования состояний, или просто инвариантным к обращению времени, когда оператор преобразования известен. Таким образом, инвариантность к обращению времени более сильное свойство, чем просто обратимость . [c.155] Теория обратимых клеточных автоматов содержит много открытых проблем [58]. Неизвестна, в частности, общая процедура определения того, имеет ли данное правило обратное (возможно, она неразрешима). Тем не менее для двух заданных наперед правил всегда можно в принципе решить, являются ли они обращениями друг друга. В соответствии с представленным ниже методом конструирования обратимых клеточных автоматов, прямое правило всегда сопровождается обратным ему, так что никогда нет никаких сомнений, относящихся к его обратимости - ни в принципе, ни на практике. [c.156] Вернуться к основной статье