Обратимые клеточные автоматы

Обратимые клеточные автоматы [c.155]

Теория обратимых клеточных автоматов содержит много открытых проблем [58]. Неизвестна, в частности, общая процедура определения того, имеет ли данное правило обратное (возможно, она неразрешима). Тем не менее для двух заданных наперед правил всегда можно в принципе решить, являются ли они обращениями друг друга. В соответствии с представленным ниже методом конструирования обратимых клеточных автоматов, прямое правило всегда сопровождается обратным ему, так что никогда нет никаких сомнений, относящихся к его обратимости - ни в принципе, ни на практике. [c.156]

Первый общий метод, который мы рассмотрим для получения обратимых клеточных автоматов, включает создание систем второго порядка, являющихся инвариантными к обращению времени. Пример этого метода был дан в разд. 6.2, естественным продолжением которого является настоящее обсуждение. [c.156]

Не следует делать вывод, что обратимые клеточные автоматы менее интересны, чем необратимые. Это всего лишь означает, что в этих системах, как и в физике, ничего особенно интересного не может возникнуть, если начать с максимально неупорядоченного состояния. [c.164]

Обратимые клеточные автоматы 155 [c.277]

Более полное рассмотрение обратимости в клеточных автоматах будет дано в гл. 14 в частности, теоретическое обоснование приведенного выше примера дается в разд. 14.2. [c.53]

Многое из недавних достижений в этом направлении проистекает из взаимодействия двух факторов. Что касается технологии, то сейчас доступны компьютеры, которые могут достаточно эффективно выполнять команды для модели на клеточном автомате. С идейной стороны, мы начинаем понимать, как конструировать дискретные, распределенные модели, которые способны отразить существенные черты физической причинности, такие, как микроскопическая обратимость. [c.151]

Оказывается, что можно конструировать нетривиальные клеточные автоматы, которые проявляют полную обратимость (в этом отношении они свободны от погрешностей, вызванных аппроксимациями, столь частыми в традиционном численном моделировании). Тем самым можно получить модели, хотя и очень далекие от реальности в других отношениях, но полностью сохраняющие эту фундаментальную особенность физического процесса. [c.154]

Для локально взаимодействующих систем, таких как клеточные автоматы, имеющих конечное количество информации на одно место, обратимость эквивалентна второму закону термодинамики. [c.154]

В физике обратимая система, имеющая и степеней свободы, обладает 2п-1 сохраняющимися величинами, часть из которых (например, энергия, импульс и т. д.) имеет особое значение ввиду их связи с фундаментальными симметриями физических законов [33]. Соображения, которые приводят к этим законам сохранения, могут быть обобщены на клеточные автоматы. Основная идея состоит в том, что произвольное данное состояние кодирует всю информацию, необходимую для определения частной динамической траектории, на которой оно лежит. Если система обратима, то эта информация не теряется в процессе эволюции. [c.154]

Теперь мы обсудим метод порождения обратимых правил более целенаправленным и очевидным способом, а именно рассматривая клеточные автоматы на разбиении, некоторые примеры которых приводились в гл. 10 и 12. [c.160]

По приведенным выше причинам почти всякое правило, которое можно записать, дает необратимый клеточный автомат (действительно, еще несколько лет назад была известна только горстка обратимых правил, но и те были чрезвычайно тривиальны [58]). [c.161]

В приложениях, обсуждаемых в следующих главах, мы будем широко использовать этот метод обновления блоков. Стимулом для его разработки послужило изучение обратимых моделей вычислений, а в действительности его первым применением была реализация на клеточном автомате компьютеров из биллиардных шаров (см. гл. 18). [c.162]

Клеточный автомат можно представлять себе как распределенное в пространстве устройство, эволюция которого управляется системой взаимосвязанных уравнений число уравнений равно числу клеток. Проблема определения этих уравнений таким образом, чтобы система была глобально обратимой, в общем случае является очень сложной (ее трудность аналогична той, которая возникает при изучении обратимости больших матриц), но она упрощается, если характер соединений подчиняется некоторым подходящим ограничениям. Конкретнее, если за время данного шага устройство фактически разбивается на совокупность небольших независимых областей, то шаг в целом обратим, если и только если его действие по отношению к каждой отдельной области обратимо. Последнее является локальным свойством, и поэтому его легко добиться. [c.163]

Представленная здесь модель вычислений основана на обратимых механизмах такого рода, которые рассматриваются в классической механике (последняя в действительности еще не является настоящей физикой, а только ее полезной идеализацией). Мы также реализуем эту модель в виде клеточного автомата. При этом мы докажем, что (а) с помощью клеточного автомата можно легко моделировать некоторые физические явления и (Ь) даже когда наложены ограничения микроскопической обратимости, эти модели достаточно мощны, чтобы проявлять сколь угодно сложное поведение. [c.228]

Обратимый компьютер на основе клеточного автомата [c.232]

Вопрос о том, могут ли клеточные автоматы моделировать непосредственно законы физики, а не только общие феноменологические аспекты нашего мира, был вновь поставлен Э. Фредкином, который проявлял активность и в более традиционных областях исследований клеточных автоматов (см. [3]), и Т. Тоффоли [55]. Основной целью настоящего исследования является рмулировка компьютероподобных моделей в физике, сохраняющих информацию, а значит и одно из наиболее фундаментальных свойств микроскопической физики, а именно обратимость [17, 58, 35]. [c.14]

Некоторые основные черты физических законов, такие как однородность и локальность, присущи клеточным автоматам по построению с другой стороны, обратимость не получается автоматически и должна быть представлена программно. Еще совсем недавно никто не знал, как это делать систематически. Было даже подозрение, что обратимость можно ввести лишь за счет утраты других свойств (таких как вычислительная и структурная универсальность), существенных для общецелевого моделирования. [c.154]

В клеточных автоматах на разбиении, с другой стороны, благодаря специальной дисциплине информационного потока существует непосредственная связь между обратимостью всей динамической системы и обратимостью отдельных вентилей, которые образуют массив. Поэтому обратимость может быть прямо запрограммирована, что иллюстрируется использованием окрестности Марголуса (см. гл. 12), одной из простейших схем разбиения. [c.161]

Справочник химика 21

Химия и химическая технология