ПОИСК Статьи Рисунки Таблицы Метод разбиения из "Машины клеточных автоматов" Обратимость систем второго порядка, вроде обсуждавшихся в предыдущем разделе, выглядит несколько неожиданно. Отметим, что в (14.2) функция т может быть выбрана произвольно если с являются вещественными числами, то т может использовать, скажем, возведение в квадрат и округление - операции, которые отбрасывают часть информации. Несмотря на это, полученная в результате динамика обратима, что означает отсутствие потери информации. Создается впечатление, что проведен сеанс математической магии. [c.160] Теперь мы обсудим метод порождения обратимых правил более целенаправленным и очевидным способом, а именно рассматривая клеточные автоматы на разбиении, некоторые примеры которых приводились в гл. 10 и 12. [c.160] В обычных клеточных автоматах устройство, которое порождает за один шаг новую конфигурацию из текущей, можно представить как массив логических вентилей, по одному на клетку, единообразно расположенных в пространстве и времени. На схеме, приведенной на рис. 14.1а (где для ясности представлено только одно пространственное измерение), каждый вентиль имеет несколько входных линий, соответствующих соседям клетки, но лишь одну выходную линию, в которой возникнет новое состояние клетки. В общем случае функция, вычисляемая вентилем этого вида, не может быть инвертируемой, поскольку лишь часть информации, имеющейся на входах, может появиться на выходе, а часть информации будет утерями. Верно, конечно, что некоторая часть входной информации каждого вентиля просматривается и соседними вентилями, и поэтому существует возможность, что потерянное в данном месте может сохраниться в каком-то виде где-либо еще. [c.160] Однако чтобы гарантировать, что никакая часть информации не потеряется где-нибудь во время работы клеточного автомата, необходимы очень хитроумные предписания. [c.161] По приведенным выше причинам почти всякое правило, которое можно записать, дает необратимый клеточный автомат (действительно, еще несколько лет назад была известна только горстка обратимых правил, но и те были чрезвычайно тривиальны [58]). [c.161] В клеточных автоматах на разбиении, с другой стороны, благодаря специальной дисциплине информационного потока существует непосредственная связь между обратимостью всей динамической системы и обратимостью отдельных вентилей, которые образуют массив. Поэтому обратимость может быть прямо запрограммирована, что иллюстрируется использованием окрестности Марголуса (см. гл. 12), одной из простейших схем разбиения. [c.161] ДЛЯ всего блока из четырех клеток и осуществляет общий контроль над ним. Если отдельный вентиль обратим, то глобальный процесс также обратим. Если вентиль теряет информацию, то ни один из его соседей не будет в состоянии восполнить эти потери, и процесс заведомо будет необратим. [c.162] Легко проверить, что полная таблица правил HPP-GAS (см. разд. [c.162] В приложениях, обсуждаемых в следующих главах, мы будем широко использовать этот метод обновления блоков. Стимулом для его разработки послужило изучение обратимых моделей вычислений, а в действительности его первым применением была реализация на клеточном автомате компьютеров из биллиардных шаров (см. гл. 18). [c.162] Это обсуждение может быть легко обобщено на большее число измерений, состояний клетки и более сложные изменения правил и схем разбиения. Основные рассуждения могут быть подытожены следующим образом. [c.163] Клеточный автомат можно представлять себе как распределенное в пространстве устройство, эволюция которого управляется системой взаимосвязанных уравнений число уравнений равно числу клеток. Проблема определения этих уравнений таким образом, чтобы система была глобально обратимой, в общем случае является очень сложной (ее трудность аналогична той, которая возникает при изучении обратимости больших матриц), но она упрощается, если характер соединений подчиняется некоторым подходящим ограничениям. Конкретнее, если за время данного шага устройство фактически разбивается на совокупность небольших независимых областей, то шаг в целом обратим, если и только если его действие по отношению к каждой отдельной области обратимо. Последнее является локальным свойством, и поэтому его легко добиться. [c.163] Чтобы отменить шаг, отмените преобразование каждой отдельной области. [c.163] Чтобы отменить всю эволюцию во времени, отмените отдельные шаги от последнего до первого. [c.163] Вернуться к основной статье