Reversibility and Universality: Essays Presented to Kenichi Morita on the Occasion of his 70th Birthday (Emergence, Complexity and Computation Book 30)

"This book is a tribute to Kenichi Morita's ideas and achievements in theoretical computer science, reversibility and computationally universal mathematical machines. It offers a unique source of information on universality and reversibility in computation and is an indispensable book for computer scientists, mathematicians, physicists and engineers. Morita is renowned for his works on two-dimensional language accepting automata, complexity of Turing machines, universality of cellular automata, regular and context-free array grammars, and undecidability. His high-impact works include findings on parallel generation and parsing of array languages by means of reversible automata, construction of a reversible automaton from Fredkin gates, solving a firing squad synchronization problem in reversible cellular automata, self-reproduction in reversible cellular spaces, universal reversible two-counter machines, solution of nondeterministic polynomial (NP) problems in hyperbolic cellular automata, reversible P-systems, a new universal reversible logic element with memory, and reversibility in asynchronous cellular automata. Kenichi Morita's achievements in reversibility, universality and theory of computation are celebrated in over twenty high-profile contributions from his colleagues, collaborators, students and friends. The theoretical constructs presented in this book are amazing in their diversity and depth of intellectual insight, addressing: queue automata, hyperbolic cellular automata, Abelian invertible automata, number-conserving cellular automata, Brownian circuits, chemical automata, logical gates implemented via glider collisions, computation in swarm networks, picture arrays, universal reversible counter machines, input-position-restricted models of language acceptors, descriptional complexity and persistence of cellular automata, partitioned cellular automata, firing squad synchronization algorithms, reversible asynchronous automata, reversible simulations of ranking trees, Shor's factorization algorithms, and power consumption of cellular automata"-- Proporcionat per l'editor Front Matter ....Pages i-xii A Snapshot of My Life (Kenichi Morita)....Pages 1-3 FSSP Algorithms for 2D Rectangular Arrays. Recent Developments (Hiroshi Umeo)....Pages 5-36 Abelian Invertible Automata (Klaus Sutner)....Pages 37-59 Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage (Jérôme Durand-Lose)....Pages 61-93 A Weakly Universal Cellular Automaton on the Grid {8, 3} with Two States (Maurice Margenstern)....Pages 95-127 Cellular Automata: Descriptional Complexity and Decidability (Martin Kutrib, Andreas Malcher)....Pages 129-168 Invertible Construction of Decimal-to-Binary Converter Using Reversible Elements (Tai-Ran He, Jia Lee, Teijiro Isokawa)....Pages 169-181 Power Consumption in Cellular Automata (Georgios Ch. Sirakoulis, Ioannis Karafyllidis)....Pages 183-198 Logical Gates via Gliders Collisions (Genaro J. Martínez, Andrew Adamatzky, Kenichi Morita)....Pages 199-220 Computation and Pattern Formation by Swarm Networks with Brownian Motion (Teijiro Isokawa, Ferdinand Peper)....Pages 221-241 Clean Reversible Simulations of Ranking Binary Trees (Yuhi Ohkubo, Tetsuo Yokoyama, Chishun Kanayama)....Pages 243-267 On Radius 1 Nontrivial Reversible and Number-Conserving Cellular Automata (Katsunobu Imai, Bruno Martin, Ryohei Saito)....Pages 269-277 The Computing Power of Determinism and Reversibility in Chemical Reaction Automata (Fumiya Okubo, Takashi Yokomori)....Pages 279-298 On Non-polar Token-Pass Brownian Circuits (Ferdinand Peper, Jia Lee)....Pages 299-311 On the Reversibility of ECAs with Fully Asynchronous Updating: The Recurrence Point of View (Nazim Fatès, Biswanath Sethi, Sukanta Das)....Pages 313-332 An Overview of 2D Picture Array Generating Models Based on Membrane Computing (K. G. Subramanian, Sastha Sriram, Bosheng Song, Linqiang Pan)....Pages 333-356 Input-Position-Restricted Models of Language Acceptors (Oscar H. Ibarra, Ian McQuillan)....Pages 357-372 On the Persistency of Gellular Automata (Masami Hagiya, Katsunobu Imai)....Pages 373-383 Queue Automata: Foundations and Developments (Martin Kutrib, Andreas Malcher, Matthias Wendlandt)....Pages 385-431 Small Universal Reversible Counter Machines (Artiom Alhazov, Sergey Verlan, Rudolf Freund)....Pages 433-446 Improving the Success Probability for Shor’s Factorization Algorithm (Guoliang Xu, Daowen Qiu, Xiangfu Zou, Jozef Gruska)....Pages 447-462 Simple Block-Substitution Rule Exhibits Interesting Patterns (Rolf Hoffmann)....Pages 463-479 Back Matter ....Pages 481-484