Adamatzky A. (Ed.) Advances in Unconventional Computing. Volume 1. Theory

Springer International Publishing, 2017. — 874 p. — (Emergence, Complexity and Computation 22). — ISBN: 978-3-319-33924-5; 978-3-319-33923-8.The unconventional computing is a niche for interdisciplinary science, cross-bred of computer science, physics, mathematics, chemistry, electronic engineering, biology, material science and nanotechnology. The aims of this book are to uncover and exploit principles and mechanisms of information processing in and functional properties of physical, chemical and living systems to develop efficient algorithms, design optimal architectures and manufacture working prototypes of future and emergent computing devices.
This first volume presents theoretical foundations of the future and emergent computing paradigms and architectures. The topics covered are computability, (non-)universality and complexity of computation; physics of computation, analog and quantum computing; reversible and asynchronous devices; cellular automata and other mathematical machines; P-systems and cellular computing; infinity and spatial computation; chemical and reservoir computing.
The book is the encyclopedia, the first ever complete authoritative account, of the theoretical and experimental findings in the unconventional computing written by the world leaders in the field. All chapters are self-contains, no specialist background is required to appreciate ideas, findings, constructs and designs presented. This treatise in unconventional computing appeals to readers from all walks of life, from high-school pupils to university professors, from mathematicians, computers scientists and engineers to chemists and biologists.Nonuniversality in Computation: Fifteen Misconceptions Rectified
What Is Computable? What Is Feasibly Computable? A Physicist’s Viewpoint
The Ideal Energy of Classical Lattice Dynamics
An Analogue-Digital Model of Computation: Turing Machines with Physical Oracles
Physical and Formal Aspects of Computation: Exploiting Physics for Computation and Exploiting Computation for Physical Purposes
Computing in Perfect Euclidean Frameworks
Unconventional Computers and Unconventional Complexity Measures
Decreasing Complexity in Inductive Computations
Asymptotic Intrinsic Universality and Natural Reprogrammability by Behavioural Emulation
Two Small Universal Reversible Turing Machines
Percolation Transition and Related Phenomena in Terms of Grossone Infinity Computations
Spacetime Computing: Towards Algorithmic Causal Sets with Special-Relativistic Properties
Interaction-Based Programming in MGS
Cellular Automata in Hyperbolic Spaces
A Computation in a Cellular Automaton Collider Rule 110
Quantum Queries Associated with Equi-partitioning of States and Multipartite Relational Encoding Across Space-Time
Solving the Broadcast Time Problem Using a D-wave Quantum Computer
The Group Zoo of Classical Reversible Computing and Quantum Computing
Fault Models in Reversible and Quantum Circuits
A Class of Non-optimum-time FSSP Algorithms
Universality of Asynchronous Circuits Composed of Locally Reversible Elements
Reservoir Computing as a Model for In-Materio Computing
On Reservoir Computing: From Mathematical Foundations to Unconventional Applications
Computational Properties of Cell Regulatory Pathways Through Petri Nets
Kernel P Systems and Stochastic P Systems for Modelling and Formal Verification of Genetic Logic Gates
On Improving the Expressive Power of Chemical Computation
Conventional and Unconventional Approaches to Swarm Logic
On the Inverse Pattern Recognition Problem in the Context of the Time-Series Data Processing with Memristor Networks
Self-Awareness in Digital Systems: Augmenting Self-Modification with Introspection to Create Adaptive, Responsive Circuitry
Looking for Computers in the Biological Cell. After Twenty Years
Unconventional Computing: A Brief Subjective History