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.

This book describes reversible computing from the standpoint of the theory of automata and computing. It investigates how reversibility can be effectively utilized in computing. A reversible computing system is a “backward deterministic” system such that every state of the system has at most one predecessor. Although its definition is very simple, it is closely related to physical reversibility, one of the fundamental microscopic laws of Nature. Authored by the leading scientist on the subject, this book serves as a valuable reference work for anyone working in reversible computation or in automata theory in general. This work deals with various reversible computing models at several different levels, which range from the microscopic to the macroscopic, and aims to clarify how computation can be carried out efficiently and elegantly in these reversible computing models. Because the construction methods are often unique and different from those in the traditional methods, these computing models as well as the design methods provide new insights for future computing systems. Organized bottom-up, the book starts with the lowest scale of reversible logic elements and circuits made from them. This is followed by reversible Turing machines, the most basic computationally universal machines, and some other types of reversible automata such as reversible multi-head automata and reversible counter machines. The text concludes with reversible cellular automata for massively parallel spatiotemporal computation. In order to help the reader have a clear understanding of each model, the presentations of all different models follow a similar pattern: the model is given in full detail, a short informal discussion is held on the role of different elements of the model, and an example with illustrations follows each model.

This book constitutes the strictly refereed post-conference proceedings recording the scientific progress achieved at the First International Conference on Evolvable Systems: From Biology to Hardware, ICES'96, held in Tsukuba, Japan, in October 1996. The volume presents 33 revised full papers including several invited contributions surveying the state of the art in this emerging area of research and development. The volume is divided into topical sections on evolware, cellular systems, engineering applications of evolvable hardware systems, evolutionary robotics, innovative architectures, evolvable systems, evolvable hardware, and genetic programming.

The present work addresses itself to one of the most hotly debated issues in contemporary ethics-relativism. Relativism has become a formidable argument in Western socio-moral thought under the impact of postmodern writings. The author presents a detailed critique of various relativist and postmodernist theses, without rejecting some of their empirically justified observations. She underscores the fact that the intercultural communication which has been going on since time immemorial puts a question mark to the postmodernist theories of indeterminacy of translation, incommensurability of various conceptual frameworks etc. The author supports cognitivism in ethics according to which the moral properties of the object of moral judgement do in some way determine or `cause` that judgment. This view is not to be confused with any realist ontological commitment. She asserts that universalizability is the necessary condition of all rational judgments, including the moral ones. The author also discusses the relationship between self and others; and in this context she draws upon the insights of ancient Indian thinkers. She proposes that minimum moral principles and maxims can be agreed upon through reasoning and intercultural discourse.

Unconventional computing is the quest for groundbreaking new algorithms and computing architectures based on and inspired by the principles of information processing in physical, chemical and biological systems. The timely scientific contributions in this book include cutting-edge theoretical work on quantum and kinematic Turing machines, computational complexity of physical systems, molecular and chemical computation, processing incomplete information, physical hypercomputation, automata networks and swarms. They are nicely complemented by recent results on experimental implementations of logical and arithmetical circuits in a domino substrate, DNA computers, and self-assembly. The book supports interdisciplinary research in the field of future computing and contributes toward developing a common interface between computer science, biology, mathematics, chemistry, electronics engineering, and physics.

This unique comprehensive compendium provides extensive studies on reversible cellular automata (RCAs), exhibiting a wide range of interesting phenomena similar to the Game-of-Life, a well-known irreversible CA.The useful reference text also introduces innovative approaches to constructing universal computers in a reversible cellular space. Numerous figures are included to illustrate the evolution of RCA configurations, and to elucidate theoretical results on RCAs. Additionally, readers can observe evolution processes of various RCAs on the free CA simulator Golly using supplementary files.

Collision-Based Computing presents a unique overview of computation with mobile self-localized patterns in non-linear media, including computation in optical media, mathematical models of massively parallel computers, and molecular systems. It covers such diverse subjects as conservative computation in billiard ball models and its cellular-automaton analogues, implementation of computing devices in lattice gases, Conway's Game of Life and discrete excitable media, theory of particle machines, computation with solitons, logic of ballistic computing, phenomenology of computation, and self-replicating universal computers. Collision-Based Computing will be of interest to researchers working on relevant topics in Computing Science, Mathematical Physics and Engineering. It will also be useful background reading for postgraduate courses such as Optical Computing, Nature-Inspired Computing, Artificial Intelligence, Smart Engineering Systems, Complex and Adaptive Systems, Parallel Computation, Applied Mathematics and Computational Physics.