Перегляд вихідного коду сторінки Оборотний клітинний автомат

[[Файл:Rectangular band cellular automaton.svg|thumb|upright=1.35|Одновимірний оборотний клітинний автомат з 9 станами. На кожному кроці комірка набуває форми свого лівого сусіда і кольору&nbsp;— правого.
{{якір|зображення прикладу}}]]

'''Оборотний клітинний автомат'''&nbsp;— [[клітинний автомат]], у якому кожен стан має єдиного попередника. Таким чином, це регулярна ґратка з комірок, стан кожної з яких береться зі скінченної множини станів, і правило для одночасного оновлення станів комірок, виходячи зі станів їхніх сусідів. Умова оборотності полягає в тому, що попередній стан будь-якої комірки можна визначити, знаючи оновлені стани всіх комірок ґратки. Після обернення часу виходить інший оборотний клітинний автомат, можливо зі значно ширшим околом, але також із правилом для визначення майбутнього стану комірки, виходячи з поточних станів її сусідів.
 
Відомо кілька методів задавання оборотних клітинних автоматів, зокрема [[Блоковий клітинннй автомат|блокових клітинних автоматів]], у яких кожен блок оновлюється незалежно від інших, і [[Клітинний автомат другого порядку|клітинних автоматів другого порядку]], в яких правило оновлення комірок визначається двома попередніми станами автомата. Разом з тим, якщо автомат задано за допомогою таблиці правил, задача перевірки його оборотності розв'язна для одновимірного клітинного автомата, але [[Алгоритмічно нерозв'язна задача|нерозв'язна]] в загальному випадку.
 
Оборотні клітинні автомати задають природну модель [[Оборотні обчислення|оборотних обчислень]]&nbsp;— технології, яка дозволяє створити обчислювальні пристрої з дуже низьким споживанням електроенергії. [[Квантовий клітинний автомат|Квантові клітинні автомати]], які дають змогу проводити обчислення з використанням принципів [[Квантова механіка|квантової механіки]], часто передбачаються оборотними. Крім того, багато фізичних моделей, такі як рух молекул [[Ідеальний газ|ідеального газу]] або [[модель Ізінга]] розміщення магнітних зарядів, природно оборотні і моделюються оборотними клітинними автоматами.

Властивості оборотних клітинних автоматів можна використати для вивчення автоматів, які є необоротними, але мають [[атрактор]]&nbsp;— підмножину станів, до якої збігаються випадкові початкові стани. Як пише [[Стівен Вольфрам]], «при наближенні до атрактора будь-яка система, навіть необоротна, виявляє деякі властивості, близькі до оборотності»<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> Якщо функція переходу ніколи не змінює стану комірки, завжди змінює його на протилежний, змінює його на стан сусіда (завжди одного й того ж&nbsp;— ліворуч або праворуч) або застосовує комбінацію з останніх двох операцій, то такий елементарний клітинний автомат оборотний. Попри простоту, функція переходу, що присвоює кожній комірці значення її сусіда, відіграє важливу роль у [[Символічна динаміка|символічній динаміці]], де вона відома як [[оператор зсуву]].<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]] (також відомою як виключне «АБО»,{{Lang-en|XOR}}) поточних станів її двох сусідів. Хоча правило 90 необоротне, кожна його конфігурація має рівно чотири попередники, а також правило 90 '''''локально оборотне''''', тобто будь-яка послідовність станів, що йдуть підряд, має хоча б одного попередника.<ref name="s91">{{Harvtxt|Sutner|1991}}.</ref>

=== Інші одновимірні приклади ===
Трохи складніший приклад: нехай стан кожної комірки є [[Впорядкована пара|впорядкованою парою]] (''l'', ''r''), а функція переходу бере ліву частину нового стану в сусіда ліворуч, а праву&nbsp;— праворуч. При цьому ми припускаємо, що ліва та права частини беруться з двох різних скінченних множин можливих значень. Приклад зображено [[#зображення прикладу|на ілюстрації]] на початку статті: ліва частина стану&nbsp;— це форма фігури, а права&nbsp;— її колір. Такий автомат оборотний, оскільки можна взяти ліву частину попереднього стану з комірки праворуч, а праву&nbsp;— ліворуч.

Інший приклад оборотного одновимірного клітинного автомата здійснює множення на 2 або 5 у [[Десяткова система числення|десятковому записі]]. Кожна цифра за такого множення залежить тільки від двох попередніх розрядів, а тому окіл, що визначає наступне значення, скінченний, що необхідно для клітинного автомата. Загалом, множення або ділення числа в [[Позиційна система числення|позиційному записі]] на натуральне число <math>n</math> задається клітинним автоматом [[тоді й лише тоді]], коли всі [[Просте число|прості множники]] числа <math>n</math> входять в основу системи числення. Такий автомат одновимірний і оборотний, оскільки можна поділити або помножити відповідно на те саме число. І, наприклад, множення на 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|Планери поширюються із центральної ділянки, заданої випадково.]]

Один з найвідоміших клітинних автоматів&nbsp;— [[Життя (гра)|гра «Життя»]], не є оборотним: наприклад, багато конфігурацій вимирають. Також у ньому є [[Едемський сад (клітинний автомат)|едемські сади]]&nbsp;— конфігурації без попередників. Натомість [[Томмасо Тоффолі]] та [[Норман Марґолус]] винайшли [[Критери|'''''«Критерів»''''']]&nbsp;— оборотний клітинний автомат із динамічною поведінкою, багато в чому схожою на «Життя».<ref name="critters">{{Harvtxt|Toffoli|Margolus|1987}}, section 12.8.2, «Critters», pp. 132—134; {{Harvtxt|Margolus|1999}}; {{Harvtxt|Marotta|2005}}.</ref>

«Критери»&nbsp;— [[блоковий клітинний автомат]], у якому комірки розділено на блоки 2×2, що оновлюються окремо від інших. При цьому після кожного кроку поділ на блоки змінюється: вони зсуваються на одну комірку по горизонталі та вертикалі. Функція переходу «Критерів» змінює стан кожної комірки на протилежний, якщо кількість живих комірок у блоці не дорівнює двом, і обертає блок цілком на 180&nbsp;°, якщо це число дорівнює трьом. Оскільки кількість живих комірок змінюється на кількість мертвих, а функції переходу при кожному значенні кількості комірок оборотні, такий клітинний автомат оборотний на кожному блоці, а тому оборотний у цілому.<ref name="critters2">{{Harvtxt|Toffoli|Margolus|1987}}, section 12.8.2, «Critters», pp. 132—134; {{Harvtxt|Margolus|1999}}; {{Harvtxt|Marotta|2005}}.</ref>
 
Якщо почати з невеликої кількості випадкових комірок усередині великої ділянки мертвих комірок, то з центральної ділянки пошириться багато маленьких шаблонів, подібних до [[Планер (конфігурація клітинного автомата)|планера]] з гри «Життя», які складно взаємодіятимуть. При цьому «Критери» допускають складні [[Космічний корабель (конфігурація клітинного автомата)|космічні кораблі]] та [[Осцилятор (конфігурація клітинного автомата)|осцилятори]] з нескінченним числом різних періодів.<ref name="critters3">{{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, обмежені пунктирними червоними лініями.]]

'''''Блоковий клітинний автомат'''''&nbsp;— клітинний автомат, комірки якого поділено на рівні блоки, а функція переходу застосовується до кожного блоку окремо. Зазвичай такий автомат по черзі використовує кілька розбиттів на блоки.<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="block2">{{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>

=== Моделювання необоротних автоматів ===
 
Будь-який <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>

== Див. також ==
* [[Скінченний автомат]]
* [[Фронтальний клітинний автомат]]
* [[Метод рухливих клітинних автоматів]]
* [[Елементарні клітинні автомати]]

== Література ==
{{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 (журнал)|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 = Роберт Девані
 | last3 = Keen | first3 = Linda | author3-link = Лінда Кін
 | 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 (журнал)|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]]
 | 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 (журнал)|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 (журнал)|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 = Ендрю Адамацький
 | 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 = Річард Філіпс Фейнман
 | 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 = Ендрю Адамацький
 | 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|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 = Ґустав Гедлунд
 | 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|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 = Яркко Карі
 | 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|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 = Яркко Карі
 | 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 = Яркко Карі
 | 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 = Яркко Карі
 | contribution = Reversible cellular automata
 | doi = 10.1007/11505877_5
 | mr = 2187250
 | pages = 2–23
 | publisher = Springer-Verlag
 | series = [[Lecture Notes in Computer Science]]
 | title = [[Міжнародна конференція з розвитку теорії мови|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 = Яркко Карі
 | 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 = Норман Марґолус
 | doi = 10.1016/0167-2789(84)90252-5
 | journal = [[Physica|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 = Стівен Вольфрам
 | 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 = Ендрю Адамацький
 | pages = 83–104
 | publisher = Springer-Verlag
 | title = Collision-Based Computing
 | year = 2002}}.
* {{citation
 | last = Margolus | first = Norman | author-link = Норман Марґолус
 | 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|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 (журнал)|Theoretical Computer Science]]
 | mr = 1347674
 | pages = 157–163
 | title = Reversible simulation of one-dimensional irreversible cellular automata
 | volume = 148
 | year = 1995}}.
* {{citation
 | authorlink = Джон Мігілл
 | 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 = Артур Беркс
 | 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}}. Процитовано в {{harvtxt|Amoroso|Patt|1972}} і {{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|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 = Клаус Сатнер
 | 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|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 = Норман Марґолус
 | 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 = Норман Марґолус
 | doi = 10.1016/0167-2789(90)90185-R
 | issue = 1–3
 | journal = [[Physica|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|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 = Джон Ватруз
 | 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 = Стівен Вольфрам
 | isbn = 1-57955-008-8
 | mr = 1920418
 | publisher = Wolfram Media
 | title = [[A New Kind of Science]]
 | year = 2002}}
{{refend}}

== Примітки ==
{{reflist|2}}
{{Conway's Game of Life}}
[[Категорія:Клітинні автомати]]
[[Категорія:Обчислювальні галузі досліджень]]