Просмотр кода страницы Обратимый клеточный автомат

[[Файл:Rectangular band cellular automaton.svg|thumb|upright=1.35|Одномерный обратимый клеточный автомат с 9 состояниями. На каждом шаге ячейка принимает форму своего левого соседа и цвет — правого.{{якорь|изображение примера}}]]
'''Обратимый клеточный автомат''' — [[клеточный автомат]], в котором каждое состояние имеет единственного предшественника. Таким образом, это регулярная решётка из ячеек, состояние каждой из которых берётся из конечного множества состояний, и правило для одновременного обновления состояний ячеек, исходя из состояний её соседей. Условие обратимости заключается в том, что предыдущее состояние любой ячейки может быть определено, зная обновлённые состояния всех ячеек решётки. После обращения времени получается другой обратимый клеточный автомат, возможно — с намного большими окрестностями, но также с правилом для определения будущего состояния ячейки, исходя из текущих состояний ей соседей.

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

Обратимые клеточные автоматы задают естественную модель [[Обратимые вычисления|обратимых вычислений]] — технологии, которая позволяет создать вычислительные устройства с очень низким потреблением электроэнергии. [[Квантовый клеточный автомат|Квантовые клеточные автоматы]], которые позволяют производить вычисления с использованием принципов [[Квантовая механика|квантовой механики]], часто предполагаются обратимыми. Кроме того, многие модели из физики, такие как движение молекул [[Идеальный газ|идеального газа]] или [[модель Изинга]] размещения магнитных зарядов, естественным образом обратимы и моделируются обратимым клеточными автоматами.

Свойства, присущие обратимым клеточным автоматам, могут быть использованы для изучения автоматов, которые необратимы, но имеют [[аттрактор]] — подмножество состояний, к которому сходятся случайные начальные состояния. Как пишет [[Вольфрам, Стивен|Стивен Вольфрам]], «при приближении к аттрактору любая система, даже необратимая, проявляет некоторые свойства, близкие к обратимости»<ref>{{harvtxt|Wolfram|2002}}, [http://www.wolframscience.com/nksonline/page-1018g-text p. 1018] {{Wayback|url=http://www.wolframscience.com/nksonline/page-1018g-text |date=20160304190819 }}.</ref>.

== Примеры ==

=== Элементарные клеточные автоматы ===
{{Основная статья|Элементарный клеточный автомат}}
Простейшие клеточные автоматы имеют одномерный массив ячеек, каждая из которых содержит 0 или 1, при том что окрестность ячейки состоит из неё самой и по одному соседу с каждой стороны; такие клеточные автоматы называются '''''элементарными'''''<ref>{{harvtxt|Schiff|2008}}, p. 44.</ref>. Если функция перехода никогда не меняет состояние ячейки, всегда заменяет его на противоположное, заменяет его на состояние соседа (всегда одного и того же — слева или справа) или применяет комбинацию из последних двух операций, то такой элементарный клеточный автомат обратим. Несмотря на свою простоту, функция перехода, присваивающая каждой ячейке значение её соседа, играет важную роль в [[Символическая динамика|символической динамике]], где она известна как [[оператор сдвига]]<ref>{{harvtxt|Blanchard|Devaney|Keen|2004}}, [https://books.google.com/books?id=HHTwiL_Ul4sC&pg=PA38 p. 38]: «The shift map is without doubt the fundamental object in symbolic dynamics.»</ref>.

Элементарные клеточные автоматы необратимы, не считая упомянутых выше тривиальных случаев, в которых каждая ячейка определяется состоянием только одного из своих соседей. Однако близко к обратимым [[правило 90]], в котором будущее состояние каждой ячейки является [[Сложение по модулю 2|суммой по модулю 2]] (также известным как исключающее «ИЛИ», {{lang-en|XOR}}) текущих состояний её двух соседей. Хотя правило 90 необратимо, каждая его конфигурация имеет ровно четыре предшественника, а также правило 90 '''''локально обратимо''''', то есть любая последовательность подряд идущих состояний имеет хотя бы одного предшественника<ref name="s91">{{harvtxt|Sutner|1991}}.</ref>.

=== Другие одномерные примеры ===
Немного более сложный пример получается так: пусть состояние каждой ячейки является [[Упорядоченная пара|упорядоченной парой]] (''l'',''r''), а функция перехода берёт левую часть нового состояния у соседа слева, а правую — справа. При этом мы предполагаем, что левая и правая части берутся из двух различных конечных множеств возможных значений. Пример изображён [[#изображение примера|на иллюстрации]] в начале статьи: левая часть состояния — это форма фигуры, а правая — это её цвет. Такой автомат обратим, поскольку можно взять левую часть предыдущего состояния у ячейки справа, а правую — слева.

Другой пример обратимого одномерного клеточного автомата производит умножение на 2 или 5 в [[Десятичная система счисления|десятичной записи]]. Каждая цифра при таком умножении зависит только от двух предыдущих разрядов, а потому окрестность, определяющая следующее значение, конечна, что и необходимо для клеточного автомата. Вообще говоря, умножение или деление числа в [[Позиционная система счисления|позиционной записи]] на натуральное число n задаётся клеточным автоматом тогда и только тогда, когда все [[Простое число|простые множители]] числа n входят в основание системы счисления. Такой автомат одномерен и обратим, поскольку можно поделить или умножить соответственно на то же число. И, например, умножение на 3 в десятичной записи не задаётся клеточным автоматом, поскольку может произойти [[Перенос (арифметика)|перенос]] через сколь угодно большое число разрядов: при умножении 333334*3=1000002 происходит перенос через 5 разрядов<ref>{{harvtxt|Wolfram|2002}}, [http://www.wolframscience.com/nksonline/page-1093c-text p. 1093] {{Wayback|url=http://www.wolframscience.com/nksonline/page-1093c-text |date=20160220134447 }}.</ref>.

=== Криттеры ===
{{Основная статья|Криттеры}}
[[Файл:Critters block automaton.png|thumb|300px|Планеры распространяются из центрального региона, заданного случайным образом.]]
[[Жизнь (игра)|Игра «Жизнь»]], один из наиболее известных клеточных автоматов, не является обратимым: например, многие конфигурации вымирают. Также в нём существуют [[Сад Эдема (конфигурация клеточного автомата)|Сады Эдема]] — конфигурации без предшественников. Взамен [[Тоффоли, Томмасо|Томмасо Тоффоли]] и [[Марголус, Норман|Норман Марголус]] изобрели '''''«Криттеров»''''' — обратимый клеточный автомат с динамическим поведением, во многом схожим с «Жизнью»<ref name="critters"/>.

«Криттеры» — [[блочный клеточный автомат]], в котором ячейки разделены на блоки 2 × 2, обновляющиеся отдельно от остальных. При этом после каждого шага разделение на блоки меняется: они сдвигаются на одну ячейку по горизонтали и вертикали. Функция перехода «Криттеров» меняет состояние каждой ячейки на противоположное, если число живых ячеек в блоке не равняется двум, и вращает на 180° блок целиком, если это число равняется трём. Поскольку число живых ячеек меняется на число мёртвых, а функции перехода при каждом значении числа ячеек обратимы, такой клеточный автомат обратим на каждом блоке, а потому обратим в целом<ref name="critters"/>.

Если начать с небольшого количества случайных ячеек внутри бо́льшего региона мёртвых ячеек, то из центрального региона распространится много маленьких шаблонов, подобных [[Планер (конфигурация клеточного автомата)|планеру]] из игры «Жизнь», которые будут сложным образом взаимодействововать. При этом «Криттеры» допускают сложные [[Космический корабль (конфигурация клеточного автомата)|космические корабли]] и осцилляторы с бесконечным числом различных периодов<ref name="critters">{{harvtxt|Toffoli|Margolus|1987}}, section 12.8.2, «Critters», pp. 132—134; {{harvtxt|Margolus|1999}}; {{harvtxt|Marotta|2005}}.</ref>.

== Конструкции ==
Известно несколько общих методов построения обратимых клеточных автоматов.

=== Блочные клеточные автоматы ===
{{Основная статья|Блочный клеточный автомат}}
[[Файл:Margolus block neighborhood.svg|thumb|left|[[Окрестность Марголуса]] для блочных клеточных автоматов. Правило преобразования по очереди действует на блоки 2 × 2, ограниченные голубыми линиями, и блоки 2 × 2, ограниченные пунктирными красными линиями.]]
'''''Блочный клеточный автомат''''' — клеточный автомат, ячейки которого поделены на равные блоки, а функция перехода применяется к каждому блоку по отдельности. Обычно такой автомат по очереди использует несколько разбиений на блоки<ref name="block">{{harvtxt|Toffoli|Margolus|1987}}, Section 14.5, «Partitioning technique», pp. 150—153; {{harvtxt|Schiff|2008}}, Section 4.2.1, «Partitioning Cellular Automata», pp. 115—116.</ref>. Типичным примером такой схемы является [[окрестность Марголуса]], в которой ячейки [[Квадратная решётка|квадратной решётки]] поделены на блоки 2 × 2 вертикальными и горизонтальными прямыми, а после каждого шага разделение на блоки сдвигается на одну ячейку по горизонтали и вертикали; таким образом, все четыре ячейки любого блока оказываются в разных блоках на следующем шаге<ref>{{harvtxt|Toffoli|Margolus|1987}}, Chapter 12, «The Margolus Neighborhood», pp. 119—138.</ref>. «Криттеры», [[#Криттеры|рассмотренные выше]], используют окрестность Марголуса.

Чтобы блочный клеточный автомат был обратимым, необходимо и достаточно обратимости функции перехода на каждом блоке, что делает возможной проверку обратимости блочного клеточного автомата при помощи [[Полный перебор|полного перебора]]. При этом обратный клеточный автомат тоже является блочным с такой же структурой разбиений на блоки, но [[Обратная функция|обратной]] функцией перехода<ref name="block"/>.

=== Моделирование необратимых автоматов ===
Любой <math>d</math>-мерный клеточный автомат можно вложить в <math>(d + 1)</math>-мерный обратимый: при этом каждое состояние нового автомата хранит всю историю эволюции старого. Используя это вложение, Тоффоли показал, что многие свойства необратимых клеточных автоматов переносятся на обратимые, например, они могут быть [[Полнота по Тьюрингу|полны по Тьюрингу]]<ref>{{harvtxt|Toffoli|1977}}</ref>.

Увеличение размерности в такой конструкции не случайно: при некоторых слабых ограничениях (вроде инвариантности вложения относительно [[Параллельный перенос|параллельных переносов]]) доказано, что любое вложение клеточного автомата с «[[Сад Эдема (конфигурация клеточного автомата)|Садом Эдема]]», то есть конфигурацией без предшественников, в обратимый клеточный автомат должно увеличивать размерность<ref>{{harvtxt|Hertling|1998}}</ref>.

Однако, при наличии '''''состояний покоя''''' ({{lang-en|quiescent states}}), то есть состояний, которые не меняются при условии, что соседние состояния также не меняются{{как?}}, возможно моделирование конечной конфигурации клеточного автомата в [[Блочный клеточный автома|блочном]] обратимом клеточном автомате той же размерности<ref>{{harvtxt|Morita|1995}}</ref>. Информация, которая должна была бы быть потеряна на следующем шаге, взамен хранится в бесконечном регионе из клеток, находящихся в состоянии покоя. При этом время, необходимое для моделирования части конфигурации, пропорционально её размеру. Тем не менее, такая конструкция позволяет доказать существование обратимого одномерного клеточного автомата, полного по Тьюрингу<ref name="kari05">{{harvtxt|Kari|2005}}.</ref>.

== Примечания ==
{{примечания|2}}

== Литература ==
{{refbegin|colwidth=30em}}
* {{citation
 | last1 = Amoroso | first1 = S.
 | last2 = Patt | first2 = Y. N.
 | doi = 10.1016/S0022-0000(72)80013-8
 | journal = [[Journal of Computer and System Sciences]]
 | mr = 0317852
 | pages = 448–464
 | title = Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
 | volume = 6
 | year = 1972}}.
* {{citation
 | last1 = Béal | first1 = Marie-Pierre
 | last2 = Carton | first2 = Olivier
 | last3 = Prieur | first3 = Christophe
 | last4 = Sakarovitch | first4 = Jacques
 | doi = 10.1016/S0304-3975(01)00214-6
 | issue = 1
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | mr = 1964625
 | pages = 45–63
 | title = Squaring transducers: an efficient procedure for deciding functionality and sequentiality
 | volume = 292
 | year = 2003}}.
* {{citation
 | last1 = Blanchard | first1 = Paul
 | last2 = Devaney | first2 = Robert L. | author2-link = Robert L. Devaney
 | last3 = Keen | first3 = Linda | author3-link = Linda Keen
 | editor-last = Williams | editor-first = Susan G.
 | contribution = Complex dynamics and symbolic dynamics
 | doi = 10.1090/psapm/060/2078845
 | location = Providence, RI
 | mr = 2078845
 | pages = 37–60
 | publisher = American Mathematical Society
 | series = Proceedings of Symposia in Applied Mathematics
 | title = Symbolic Dynamics and its Applications
 | volume = 60
 | year = 2004}}.
* {{citation
 | last = Boykett | first = Tim
 | doi = 10.1016/j.tcs.2004.06.007
 | issue = 2
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | mr = 2086738
 | pages = 215–247
 | title = Efficient exhaustive listings of reversible one dimensional cellular automata
 | volume = 325
 | year = 2004}}.
* {{citation
 |last1        = Boykett
 |first1       = Tim
 |last2        = Kari
 |first2       = Jarkko
 |author2-link = Jarkko Kari
 |last3        = Taati
 |first3       = Siamak
 |issue        = 2
 |journal      = Journal of Cellular Automata
 |mr           = 2394641
 |pages        = 115–122
 |title        = Conservation laws in rectangular CA
 |url          = http://pub.math.leidenuniv.nl/~taatis/articles/conslaws06.pdf
 |volume       = 3
 |year         = 2008
 |access-date  = 2017-10-01
}} {{Wayback|url=http://pub.math.leidenuniv.nl/~taatis/articles/conslaws06.pdf |date=20150930172501 }}.
* {{citation
 | last1 = Capobianco | first1 = Silvio
 | last2 = Toffoli | first2 = Tommaso | author2-link = Томмазо Тоффоли
 | arxiv = 1103.4785
 | contribution = Can anything from Noether’s theorem be salvaged for discrete dynamical systems?
 | doi = 10.1007/978-3-642-21341-0_13
 | pages = 77–88
 | publisher = Springer-Verlag
 | series = [[Lecture Notes in Computer Science]]
 | title = Proceedings of the 10th International Conference on Unconventional Computation (UC 2011)
 | volume = 6714
 | year = 2011}}.
* {{citation
 | last1 = Chai | first1 = Zhenchuan
 | last2 = Cao | first2 = Zhenfu
 | last3 = Zhou | first3 = Yuan
 | contribution = Encryption based on reversible second-order cellular automata
 | doi = 10.1007/11576259_39
 | pages = 350–358
 | publisher = Springer-Verlag
 | series = [[Lecture Notes in Computer Science]]
 | title = Parallel and Distributed Processing and Applications (ISPA 2005 Workshops)
 | volume = 3759
 | year = 2005}}.
* {{citation
 | last = Culik | first = Karel, II
 | issue = 6
 | journal = [[Complex Systems (journal)|Complex Systems]]
 | mr = 931401
 | pages = 1035–1044
 | title = On invertible cellular automata
 | url = http://www.complex-systems.com/pdf/01-6-1.pdf
 | volume = 1
 | year = 1987}}.
* {{citation
 | last = Czeizler | first = Eugen
 | doi = 10.1016/j.tcs.2004.06.009
 | issue = 2
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | mr = 2086740
 | pages = 273–284
 | title = On the size of the inverse neighborhoods for one-dimensional reversible cellular automata
 | volume = 325
 | year = 2004}}.
* {{citation
 | last1 = Czeizler | first1 = Eugen
 | last2 = Kari | first2 = Jarkko | author2-link = Jarkko Kari
 | doi = 10.1016/j.tcs.2007.02.052
 | issue = 1–2
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | mr = 2330639
 | pages = 23–36
 | title = A tight linear bound on the synchronization delay of bijective automata
 | volume = 380
 | year = 2007}}.
* {{citation
 | last1 = Di Gregorio | first1 = S.
 | last2 = Trautteur | first2 = G.
 | doi = 10.1016/S0022-0000(75)80059-6
 | issue = 3
 | journal = [[Journal of Computer and System Sciences]]
 | mr = 0392201
 | pages = 382–391
 | title = On reversibility in cellular automata
 | volume = 11
 | year = 1975}}.
* {{citation
 | last = Durand-Lose | first = Jérôme
 | contribution = Representing reversible cellular automata with reversible block cellular automata
 | mr = 1888769
 | pages = 145–154
 | publisher = Maison Inform. Math. Discrèt. (MIMD), Paris
 | series = Discrete Math. Theor. Comput. Sci. Proc., AA
 | title = Discrete models: combinatorics, computation, and geometry (Paris, 2001)
 | year = 2001}}.
* {{citation
 | last = Durand-Lose | first = Jérôme
 | editor-last = Adamatzky | editor-first = Andrew | editor-link = Andrew Adamatzky
 | contribution = Computing inside the billiard ball model
 | pages = 135–160
 | publisher = Springer-Verlag
 | title = Collision-Based Computing
 | year = 2002}}.
* {{citation
 | last = Feynman | first = Richard P. | authorlink = Richard Feynman
 | doi = 10.1007/BF02650179
 | issue = 6–7
 | journal = [[International Journal of Theoretical Physics]]
 | mr = 658311
 | pages = 467–488
 | title = Simulating physics with computers
 | volume = 21
 | year = 1982}}.
* {{citation
 | last1 = Fredkin | first1 = Edward | author1-link = Эдвард Фредкин
 | last2 = Toffoli | first2 = Tommaso | author2-link = Томмазо Тоффоли
 | doi = 10.1007/BF01857727
 | issue = 3–4
 | journal = [[International Journal of Theoretical Physics]]
 | mr = 657156
 | pages = 219–253
 | title = Conservative logic
 | volume = 21
 | year = 1982}}. Reprinted in {{citation
 | editor-last = Adamatzky | editor-first = Andrew | editor-link = Andrew Adamatzky
 | pages = 47–82
 | publisher = Springer-Verlag
 | title = Collision-Based Computing
 | year = 2002}}.
* {{citation
 | last = Fukś | first = Henryk
 | arxiv = nlin/0502037
 | issue = 3
 | journal = [[Fundamenta Informaticae]]
 | mr = 2346870
 | pages = 329–341
 | title = Remarks on the critical behavior of second order additive invariants in elementary cellular automata
 | volume = 78
 | year = 2007}}.
* {{citation
 | last1 = Hattori | first1 = Tetsuya
 | last2 = Takesue | first2 = Shinji
 | doi = 10.1016/0167-2789(91)90150-8
 | issue = 3
 | journal = [[Physica (journal)|Physica D: Nonlinear Phenomena]]
 | mr = 1115865
 | pages = 295–322
 | title = Additive conserved quantities in discrete-time lattice dynamical systems
 | volume = 49
 | year = 1991}}.
* {{citation
 | last = Hedlund | first = G. A. | author-link = Gustav A. Hedlund
 | doi = 10.1007/BF01691062
 | issue = 4
 | journal = Mathematical Systems Theory
 | mr = 0259881
 | pages = 320–375
 | title = Endomorphisms and automorphisms of the shift dynamical systems
 | volume = 3
 | year = 1969}}.
* {{citation
 | last = Hertling | first = Peter
 | contribution = Embedding cellular automata into reversible ones
 | mr = 1653663
 | pages = 243–256
 | publisher = Springer-Verlag
 | series = Springer Series in Discrete Mathematics and Theoretical Computer Science
 | title = Unconventional models of computation (Auckland, 1998)
 | year = 1998}}.
* {{citation
 | last = Hillman | first = David
 | doi = 10.1016/0167-2789(91)90128-V
 | issue = 2–3
 | journal = [[Physica (journal)|Physica D: Nonlinear Phenomena]]
 | mr = 1128996
 | pages = 277–292
 | title = The structure of reversible one-dimensional cellular automata
 | volume = 52
 | year = 1991}}.
* {{citation
 | last = Janzing | first = Dominik
 | arxiv = 1009.1720
 | title = Is there a physically universal cellular automaton or Hamiltonian?
 | year = 2010}}.
* {{citation
 | last = Kari | first = Jarkko | author-link = Jarkko Kari
 | title = Reversibility of 2D cellular automata is undecidable
 | doi = 10.1016/0167-2789(90)90195-U
 | issue = 1–3
 | mr = 1094882
 | pages = 379–385
 | journal = [[Physica (journal)|Physica D: Nonlinear Phenomena]]
 | department = Cellular automata: theory and experiment (Los Alamos, NM, 1989)
 | volume = 45
 | year = 1990}}.
* {{citation
 | last = Kari | first = Jarkko | author-link = Jarkko Kari
 | contribution = On the inverse neighborhoods of reversible cellular automata
 | mr = 1226709
 | pages = 477–495
 | publisher = Springer-Verlag
 | title = Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology
 | year = 1992}}.
* {{citation
 | last = Kari | first = Jarkko | author-link = Jarkko Kari
 | doi = 10.1007/BF01201813
 | issue = 1
 | journal = Mathematical Systems Theory
 | mr = 1360196
 | pages = 47–61
 | title = Representation of reversible cellular automata with block permutations
 | volume = 29
 | year = 1996}}.
* {{citation
 | last = Kari | first = Jarkko | author-link = Jarkko Kari
 | contribution = Reversible cellular automata
 | doi = 10.1007/11505877_5
 | mr = 2187250
 | pages = 2–23
 | publisher = Springer-Verlag
 | series = [[Lecture Notes in Computer Science]]
 | title = [[International Conference on Developments in Language Theory|Developments in Language Theory: 9th International Conference, DLT 2005, Palermo, Italy, July 4–8, 2005, Proceedings]]
 | contribution-url = http://copper.math.buffalo.edu/urgewiki/uploads/Literature2010Carbonara/Kari2005.pdf
 | volume = 3572
 | year = 2005}}.
* {{citation
 | last = Kari | first = Jarkko | authorlink = Jarkko Kari
 | contribution = Structure of reversible cellular automata
 | doi = 10.1007/978-3-642-03745-0_5
 | mr = 2539690
 | page = 6
 | publisher = Springer-Verlag
 | series = [[Lecture Notes in Computer Science]]
 | title = Unconventional Computation: 8th International Conference, UC 2009, Ponta Delgada, Portugal, September 7–11, 2009, Proceedings
 | volume = 5715
 | year = 2009}}.
* {{citation
 | last = Margolus | first = Norman | author-link = Norman Margolus
 | doi = 10.1016/0167-2789(84)90252-5
 | journal = [[Physica (journal)|Physica D: Nonlinear Phenomena]]
 | mr = 0762656
 | pages = 81–95
 | title = Physics-like models of computation
 | volume = 10
 | year = 1984}}. Reprinted in {{citation
 | last = Wolfram | first = Stephen | author-link = Stephen Wolfram
 | pages = 232–246
 | publisher = World Scientific
 | series = Advanced series on complex systems
 | title = Theory and Applications of Cellular Automata
 | volume = 1
 | year = 1986}}, and in {{citation
 | editor-last = Adamatzky | editor-first = Andrew | editor-link = Andrew Adamatzky
 | pages = 83–104
 | publisher = Springer-Verlag
 | title = Collision-Based Computing
 | year = 2002}}.
* {{citation
 | last = Margolus | first = Norman | author-link = Norman Margolus
 | editor-last = Hey | editor-first = Anthony J. G.
 | arxiv = comp-gas/9811002
 | contribution = Crystalline computation
 | pages = 267–305
 | publisher = Perseus Books
 | title = Feynman and Computation
 | year = 1999}}.
* {{citation
 |last        = Marotta
 |first       = Sebastian M.
 |issue       = 1
 |journal     = Revista Ciências Exatas e Naturais
 |title       = Living in Critters' world
 |url         = http://web01.unicentro.br/revistas/index.php/RECEN/article/viewFile/385/537
 |volume      = 7
 |year        = 2005
 |archiveurl  = https://web.archive.org/web/20120319190822/http://web01.unicentro.br/revistas/index.php/RECEN/article/viewFile/385/537
 |archivedate = 2012-03-19
 |access-date = 2017-10-01
}} {{Wayback|url=http://web01.unicentro.br/revistas/index.php/RECEN/article/viewFile/385/537 |date=20120319190822 }}.
* {{citation
 | last = McIntosh | first = Harold V.
 | contribution = 12. Reversible cellular automata
 | pages = 205–246
 | publisher = Luniver Press
 | title = One Dimensional Cellular Automata
 | year = 2009}}.
* {{citation
 | last = Meyer | first = David A.
 | arxiv = quant-ph/9604003
 | doi = 10.1007/BF02199356
 | issue = 5–6
 | journal = [[Journal of Statistical Physics]]
 | mr = 1418805
 | pages = 551–574
 | title = From quantum cellular automata to quantum lattice gases
 | volume = 85
 | year = 1996}}.
* {{citation
 | last1 = Miller | first1 = Daniel B.
 | last2 = Fredkin | first2 = Edward | author2-link = Эдвард Фредкин
 | arxiv = nlin/0501022
 | contribution = Two-state, reversible, universal cellular automata in three dimensions
 | doi = 10.1145/1062261.1062271
 | isbn = 1-59593-019-1
 | location = New York, NY, USA
 | pages = 45–51
 | publisher = ACM
 | title = Proceedings of the 2nd Conference on Computing Frontiers (CF '05)
 | year = 2005}}.
* {{citation
 | last1 = Miller | first1 = Daniel B.
 | last2 = Fredkin | first2 = Edward | author2-link = эдвард Фредкин
 | arxiv = 1206.2060
 | title = Circular motion of strings in cellular automata, and other surprises
 | year = 2012}}.
* {{citation
 | last = Moraal | first = Hendrik
 | doi = 10.1016/S0167-2789(00)00020-8
 | issue = 1–2
 | journal = [[Physica (journal)|Physica D: Nonlinear Phenomena]]
 | mr = 1764165
 | pages = 1–18
 | title = Graph-theoretical characterization of invertible cellular automata
 | volume = 141
 | year = 2000}}.
* {{citation
 | last = Morita | first = Kenichi
 | doi = 10.1016/0304-3975(95)00038-X
 | issue = 1
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | mr = 1347674
 | pages = 157–163
 | title = Reversible simulation of one-dimensional irreversible cellular automata
 | volume = 148
 | year = 1995}}.
* {{citation
 | authorlink = John Myhill
 | last = Myhill | first = John
 | title = The converse of Moore's Garden-of-Eden theorem
 | journal = [[Proceedings of the American Mathematical Society]]
 | mr = 0155764
 | volume = 14
 | year = 1963
 | pages = 685–686 | doi = 10.2307/2034301}}. Reprinted in {{citation
 | last = Burks | first = Arthur W. | author-link = Arthur Burks
 | pages = 204–205
 | publisher = University of Illinois Press
 | title = Essays on Cellular Automata
 | year = 1970}}.
* {{citation
 | last1 = Nagaj | first1 = Daniel
 | last2 = Wocjan | first2 = Pawel
 | arxiv = 0802.0886
 | doi = 10.1103/PhysRevA.78.032311
 | journal = Physical Review A
 | page = 032311
 | title = Hamiltonian quantum cellular automata in one dimension
 | volume = 78
 | year = 2008}}.
* {{citation
 | last = Patt | first = Y. N.
 | publisher = Ft. Monmouth, NJ 07703
 | series = Technical Report ECON-N1-P-1
 | title = Injections of neighborhood size three and four on the set of configurations from the infinite one-dimensional tessellation automata of two-state cells
 | year = 1971}}. As cited by {{harvtxt|Amoroso|Patt|1972}} and {{harvtxt|Toffoli|Margolus|1990}}.
* {{citation
 | last = Pomeau | first = Y.
 | doi = 10.1088/0305-4470/17/8/004
 | issue = 8
 | journal = [[Journal of Physics A|Journal of Physics A: Mathematical and General]]
 | mr = 0750565
 | pages = L415–L418
 | title = Invariants in cellular automata
 | volume = 17
 | year = 1984}}.
* {{citation
 | last = Richardson | first = D.
 | doi = 10.1016/S0022-0000(72)80009-6
 | journal = [[Journal of Computer and System Sciences]]
 | mr = 0319678
 | pages = 373–388
 | title = Tessellations with local transformations
 | volume = 6
 | year = 1972}}.
* {{citation
 | last = Schaeffer | first = Luke
 | contribution = A physically universal cellular automaton
 | id = [[Electronic Colloquium on Computational Complexity|ECCC]] [https://eccc.weizmann.ac.il/report/2014/084/ TR14-084]
 | year = 2015
 | title = Proceedings of the 6th Innovations in Theoretical Computer Science Conference (ITCS 2015)
 | doi = 10.1145/2688073.2688107
 | publisher = [[Association for Computing Machinery]]
 | pages = 237–246}}.
* {{citation
 | last = Schiff | first = Joel L.
 | publisher = Wiley
 | title = Cellular Automata: A Discrete View of the World
 | isbn = 978-0-470-16879-0
 | year = 2008}}.
* {{citation
 | last1 = Schumacher | first1 = B.
 | last2 = Werner | first2 = R. F.
 | arxiv = quant-ph/0405174
 | title = Reversible quantum cellular automata
 | year = 2004}}.
* {{citation
 | last1 = Seck Tuoh Mora | first1 = Juan Carlos
 | last2 = Chapa Vergara | first2 = Sergio V.
 | last3 = Juárez Martínez | first3 = Genaro
 | last4 = McIntosh | first4 = Harold V.
 | doi = 10.1016/j.physd.2005.01.018
 | issue = 1–2
 | journal = [[Physica (journal)|Physica D: Nonlinear Phenomena]]
 | mr = 2131890
 | pages = 134–141
 | title = Procedures for calculating reversible one-dimensional cellular automata
 | volume = 202
 | year = 2005}}.
* {{citation
 | last1 = Shepherd | first1 = D. J.
 | last2 = Franz | first2 = T.
 | last3 = Werner | first3 = R. F.
 | arxiv = quant-ph/0512058
 | doi = 10.1103/PhysRevLett.97.020502
 | journal = [[Physical Review Letters]]
 | page = 020502
 | title = A universally programmable quantum cellular automaton
 | volume = 97
 | year = 2006 | pmid=16907423}}.
* {{citation
 | last = Sutner | first = Klaus | authorlink = Klaus Sutner
 | journal = [[Complex Systems (journal)|Complex Systems]]
 | mr = 1116419
 | pages = 19–30
 | title = De Bruijn graphs and linear cellular automata
 | url = http://www.complex-systems.com/pdf/05-1-3.pdf
 | volume = 5
 | year = 1991}}.
* {{citation
 | last = Takesue | first = Shinji
 | title = Relaxation properties of elementary reversible cellular automata
 | doi = 10.1016/0167-2789(90)90195-U
 | issue = 1–3
 | mr = 1094882
 | pages = 278–284
 | journal = [[Physica (journal)|Physica D: Nonlinear Phenomena]]
 | department = Cellular automata: theory and experiment (Los Alamos, NM, 1989)
 | volume = 45
 | year = 1990}}.
* {{citation
 | last = Toffoli | first = Tommaso | author-link = Томмазо Тоффоли
 | doi = 10.1016/S0022-0000(77)80007-X
 | issue = 2
 | journal = [[Journal of Computer and System Sciences]]
 | mr = 0462816
 | pages = 213–231
 | title = Computation and construction universality of reversible cellular automata
 | volume = 15
 | year = 1977}}.
* {{citation
 | last1 = Toffoli | first1 = Tommaso | author1-link = Томмазо Тоффоли
 | last2 = Margolus | first2 = Norman | author2-link = Norman Margolus
 | publisher = MIT Press
 | title = Cellular Automata Machines: A New Environment for Modeling
 | isbn = 9780262200608
 | year = 1987}}.
* {{citation
 | last1 = Toffoli | first1 = Tommaso | author1-link = Томмазо Тоффоли
 | last2 = Margolus | first2 = Norman | author2-link = Norman Margolus
 | doi = 10.1016/0167-2789(90)90185-R
 | issue = 1–3
 | journal = [[Physica (journal)|Physica D: Nonlinear Phenomena]]
 | mr = 1094877
 | pages = 229–253
 | title = Invertible cellular automata: a review
 | volume = 45
 | year = 1990}}.
* {{citation
 | last = Vichniac | first = Gérard Y.
 | journal = [[Physica (journal)|Physica D: Nonlinear Phenomena]]
 | mr = 0762657
 | pages = 96–115
 | title = Simulating physics with cellular automata
 | volume = 10
 | year = 1984
 | doi=10.1016/0167-2789(84)90253-7}}.
* {{citation
 | last = Watrous | first = John | authorlink = John Watrous (computer scientist)
 | contribution = On one-dimensional quantum cellular automata
 | doi = 10.1109/SFCS.1995.492583
 | location = Los Alamitos, CA
 | mr = 1619103
 | pages = 528–537
 | publisher = IEEE Computer Society Press
 | title = Proceedings of the 36th [[Symposium on Foundations of Computer Science|Annual Symposium on Foundations of Computer Science]] (Milwaukee, WI, 1995)
 | year = 1995}}.
* {{citation
 | last = Wolfram | first = Stephen | author-link = Stephen Wolfram
 | doi = 10.1038/311419a0
 | journal = [[Nature]]
 | title = Cellular automata as models of complexity
 | url = http://www.stephenwolfram.com/publications/academic/cellular-automata-models-complexity.pdf
 | volume = 311
 | year = 1984
 | pages=419–424}}.
* {{citation
 | last = Wolfram | first = Stephen | author-link = Stephen Wolfram
 | isbn = 1-57955-008-8
 | mr = 1920418
 | publisher = Wolfram Media
 | title = [[A New Kind of Science]]
 | year = 2002}}
{{refend}}

[[Категория:Клеточные автоматы]]
[[Категория:Модели вычислений]]