Оборотний клітинний автомат

Оборотний клітинний автомат — клітинний автомат, у якому кожен стан має єдиного попередника. Таким чином, це регулярна ґратка з комірок, стан кожної з яких береться зі скінченної множини станів, і правило для одночасного оновлення станів комірок, виходячи зі станів їхніх сусідів. Умова оборотності полягає в тому, що попередній стан будь-якої комірки можна визначити, знаючи оновлені стани всіх комірок ґратки. Після обернення часу виходить інший оборотний клітинний автомат, можливо зі значно ширшим околом, але також із правилом для визначення майбутнього стану комірки, виходячи з поточних станів її сусідів.

Одновимірний оборотний клітинний автомат з 9 станами. На кожному кроці комірка набуває форми свого лівого сусіда і кольору — правого.

Відомо кілька методів задавання оборотних клітинних автоматів, зокрема блокових клітинних автоматів, у яких кожен блок оновлюється незалежно від інших, і клітинних автоматів другого порядку, в яких правило оновлення комірок визначається двома попередніми станами автомата. Разом з тим, якщо автомат задано за допомогою таблиці правил, задача перевірки його оборотності розв'язна для одновимірного клітинного автомата, але нерозв'язна в загальному випадку.

Оборотні клітинні автомати задають природну модель оборотних обчислень — технології, яка дозволяє створити обчислювальні пристрої з дуже низьким споживанням електроенергії. Квантові клітинні автомати, які дають змогу проводити обчислення з використанням принципів квантової механіки, часто передбачаються оборотними. Крім того, багато фізичних моделей, такі як рух молекул ідеального газу або модель Ізінга розміщення магнітних зарядів, природно оборотні і моделюються оборотними клітинними автоматами.

Властивості оборотних клітинних автоматів можна використати для вивчення автоматів, які є необоротними, але мають атрактор — підмножину станів, до якої збігаються випадкові початкові стани. Як пише Стівен Вольфрам, «при наближенні до атрактора будь-яка система, навіть необоротна, виявляє деякі властивості, близькі до оборотності»^[1]

Приклади

Елементарні клітинні автомати

Найпростіші клітинні автомати мають одновимірний масив комірок, кожна з яких містить 0 або 1, при тому, що окіл комірки складається з неї самої і по одному сусіду з кожного боку; такі клітинні автомати називають елементарними.^[2] Якщо функція переходу ніколи не змінює стану комірки, завжди змінює його на протилежний, змінює його на стан сусіда (завжди одного й того ж — ліворуч або праворуч) або застосовує комбінацію з останніх двох операцій, то такий елементарний клітинний автомат оборотний. Попри простоту, функція переходу, що присвоює кожній комірці значення її сусіда, відіграє важливу роль у символічній динаміці, де вона відома як оператор зсуву.^[3]

Елементарні клітинні автомати необоротні, крім згаданих вище очевидних випадків, у яких кожна комірка визначається станом лише одного зі своїх сусідів. Однак близьке до оборотних правило 90, в якому майбутній стан кожної комірки є сумою за модулем 2 (також відомою як виключне «АБО»,англ. XOR) поточних станів її двох сусідів. Хоча правило 90 необоротне, кожна його конфігурація має рівно чотири попередники, а також правило 90 локально оборотне, тобто будь-яка послідовність станів, що йдуть підряд, має хоча б одного попередника.^[4]

Інші одновимірні приклади

Трохи складніший приклад: нехай стан кожної комірки є впорядкованою парою (l, r), а функція переходу бере ліву частину нового стану в сусіда ліворуч, а праву — праворуч. При цьому ми припускаємо, що ліва та права частини беруться з двох різних скінченних множин можливих значень. Приклад зображено на ілюстрації на початку статті: ліва частина стану — це форма фігури, а права — її колір. Такий автомат оборотний, оскільки можна взяти ліву частину попереднього стану з комірки праворуч, а праву — ліворуч.

Інший приклад оборотного одновимірного клітинного автомата здійснює множення на 2 або 5 у десятковому записі. Кожна цифра за такого множення залежить тільки від двох попередніх розрядів, а тому окіл, що визначає наступне значення, скінченний, що необхідно для клітинного автомата. Загалом, множення або ділення числа в позиційному записі на натуральне число ${\displaystyle n}$ задається клітинним автоматом тоді й лише тоді, коли всі прості множники числа ${\displaystyle n}$ входять в основу системи числення. Такий автомат одновимірний і оборотний, оскільки можна поділити або помножити відповідно на те саме число. І, наприклад, множення на 3 в десятковому записі не задається клітинним автоматом, оскільки може відбутися перенесення через як завгодно багато розрядів: при множенні 333334 * 3 = 1000002 відбувається перенесення через 5 розрядів.^[5]

Критери

Докладніше: Критери

Планери поширюються із центральної ділянки, заданої випадково.

Один з найвідоміших клітинних автоматів — гра «Життя», не є оборотним: наприклад, багато конфігурацій вимирають. Також у ньому є едемські сади — конфігурації без попередників. Натомість Томмасо Тоффолі та Норман Марґолус винайшли «Критерів» — оборотний клітинний автомат із динамічною поведінкою, багато в чому схожою на «Життя».^[6]

«Критери» — блоковий клітинний автомат, у якому комірки розділено на блоки 2×2, що оновлюються окремо від інших. При цьому після кожного кроку поділ на блоки змінюється: вони зсуваються на одну комірку по горизонталі та вертикалі. Функція переходу «Критерів» змінює стан кожної комірки на протилежний, якщо кількість живих комірок у блоці не дорівнює двом, і обертає блок цілком на 180 °, якщо це число дорівнює трьом. Оскільки кількість живих комірок змінюється на кількість мертвих, а функції переходу при кожному значенні кількості комірок оборотні, такий клітинний автомат оборотний на кожному блоці, а тому оборотний у цілому.^[6]

Якщо почати з невеликої кількості випадкових комірок усередині великої ділянки мертвих комірок, то з центральної ділянки пошириться багато маленьких шаблонів, подібних до планера з гри «Життя», які складно взаємодіятимуть. При цьому «Критери» допускають складні космічні кораблі та осцилятори з нескінченним числом різних періодів.^[6]

Побудови

Відомо кілька загальних методів побудови оборотних клітинних автоматів.

Блокові клітинні автомати

Окіл Марґолуса для блокових клітинних автоматів. Правило перетворення по черзі діє блоки 2×2, обмежені синіми лініями, і блоки 2×2, обмежені пунктирними червоними лініями.

Блоковий клітинний автомат — клітинний автомат, комірки якого поділено на рівні блоки, а функція переходу застосовується до кожного блоку окремо. Зазвичай такий автомат по черзі використовує кілька розбиттів на блоки.^[7] Типовим прикладом такої схеми є окіл Марґолуса, в якому комірки квадратної ґратки поділено на блоки 2×2 вертикальними та горизонтальними прямими, а після кожного кроку поділ на блоки зсувається на одну комірку по горизонталі та вертикалі; завдяки цьому, всі чотири комірки будь-якого блоку на наступному кроці опиняються в різних блоках.^[8] «Критери», розглянуті вище, використовують окіл Марґолуса.

Щоб блоковий клітинний автомат був оборотним, необхідно і достатньо оборотності функції переходу на кожному блоці, що уможливлює перевірку оборотності блокового клітинного автомата за допомогою повного перебору. Обернений клітинний автомат у такому разі теж є блоковим із такою самою структурою розбиття на блоки, але оберненою функцією переходу.^[7]

Моделювання необоротних автоматів

Будь-який ${\displaystyle d}$-вимірний клітинний автомат можна вкласти в ${\displaystyle (d+1)}$-вимірний оборотний: в цьому разі кожен стан нового автомата зберігає всю історію еволюції старого. Використовуючи це вкладення, Тоффолі показав, що багато властивостей необоротних клітинних автоматів переносяться на оборотні, наприклад, вони можуть бути повними за Тюрінгом.^[9]

Збільшення розмірності в такій побудові не випадкове: за деяких слабких обмежень (на зразок інваріантності вкладення відносно паралельних перенесень) доведено, що будь-яке вкладення клітинного автомата з «едемським садом», тобто конфігурацією без попередників, у оборотний клітинний автомат має збільшувати розмірність.^[10]

Проте, за наявності станів спокою (англ. quiescent states), тобто станів, які не змінюються за умови, що сусідні стани також не змінюються^[як?], можливе моделювання кінцевої конфігурації клітинного автомата в блоковому оборотному клітинному автоматі тієї ж розмірності.^[11] Інформація, яка мала б бути втрачена на наступному кроці, натомість зберігається в нескінченній ділянці з клітин, які перебувають у стані спокою. В такому разі час, необхідний для моделювання частини конфігурації, пропорційний її обсягу. Тим не менш, така побудова дає змогу довести існування оборотного одновимірного клітинного автомата, повного за Тюрінгом.^[12]

Див. також

• Скінченний автомат
• Фронтальний клітинний автомат
• Метод рухливих клітинних автоматів
• Елементарні клітинні автомати

Література

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