Emergent Computation

This book is dedicated to Professor Selim G. Akl to honour his groundbreaking research achievements in computer science over four decades. The book is an intellectually stimulating excursion into emergent computing paradigms, architectures and implementations. World top experts in computer science, engineering and mathematics overview exciting and intriguing topics of musical rhythms generation algorithms, analyse the computational power of random walks, dispelling a myth of computational universality, computability and complexity at the microscopic level of synchronous computation, descriptional complexity of error detection, quantum cryptography, context-free parallel communicating grammar systems, fault tolerance of hypercubes, finite automata theory of bulk-synchronous parallel computing, dealing with silent data corruptions in high-performance computing, parallel sorting on graphics processing units, mining for functional dependencies in relational databases, cellular automata optimisation of wireless sensors networks, connectivity preserving network transformers, constrained resource networks, vague computing, parallel evolutionary optimisation, emergent behaviour in multi-agent systems, vehicular clouds, epigenetic drug discovery, dimensionality reduction for intrusion detection systems, physical maze solvers, computer chess, parallel algorithms to string alignment, detection of community structure. The book is a unique combination of vibrant essays which inspires scientists and engineers to exploit natural phenomena in designs of computing architectures of the future.

Emergent Computation is concerned with recent applications of Mathematical Linguistics or Automata Theory. This subject has a primary focus upon "Bioinformatics" (the Genome and arising interest in the Proteome), but the closing chapter also examines applications in Biology, Medicine, Anthropology, etc. The book is composed of an organized examination of DNA, RNA, and the assembly of amino acids into proteins. Rather than examine these areas from a purely mathematical viewpoint (that excludes much of the biochemical reality), the author uses scientific papers written mostly by biochemists based upon their laboratory observations. Thus while DNA may exist in its double stranded form, triple stranded forms are not excluded. Similarly, while bases exist in Watson-Crick complements, mismatched bases and abasic pairs are not excluded, nor are Hoogsteen bonds. Just as there are four bases naturally found in DNA, the existence of additional bases is not ignored, nor amino acids in addition to the usual complement of 20. Can there be more than "64" possible codons? RNA is examined from the point of view of Nussinov plots. All information is presented from the point of view of regular, context-free, and context sensitive languages, as well as Turing machines and Sequential Machines (and their corresponding semi-groups). Relationships to other subjects of mathematics such as Complex numbers, Quaternions, Algebraic-Topology, and Knot Theory are also mentioned. An examination is made of Splicing Systems as well as Dominoes. Shortcomings illustrating the dangers of mathematical abstractions that ignore biochemistry are pointed out. The papers examine the subjects of interest from the point of view of applying language theory to search for new results, but also as biological-automatons (implementations or machines) to do calculations. This book will be of value to those studying Bioinformatics, Biochemistry, Computer-Science, Mathematical Linguistics, and Biology, as well as Pharmacology (with the possible promise of medically active artificial DNA, RNA, and proteins). Laboratory results to demonstrate the usefulness of the topics discussed are demonstrated both in vitro and in vivo.

An understanding of emergent computation requires a profound revision of the most fundamental ideas. A noticeable attempt of such a rethinking is a world view in which natural systems are seen not as separate entities but as integrated parts of a unified whole. The book for the first time presents such a mathematical structure, which remarkably is based on integers as the single concept. As integers are considered to be the most fundamental entities irreducible to something simpler, this makes the mathematical structure a final theory, and thus we do not have to look for its explanation in terms of deeper concepts. The book is not only applicable to models of computation and optimization but also has scientific consequences, as it contributes to a rethinking of the most fundamental ideas about nature. Audience: The book is written at a level suitable for advanced undergraduate students and graduate students as well as research workers and practitioners in computer science information technology, mathematics and physics. The book is suitable as a reference or as supplementary reading material for an advanced graduate course. Only a basic knowledge of calculus is required.

Cellular computing is a natural information processing paradigm, capable of modeling various biological, physical and social phenomena, as well as other kinds of complex adaptive systems. The programmingof a cellular computer is in many respects similar to the geneticevolution in biology, the result being a proper cell design and atask-specific gene.

This volume contains papers presented at the BCEC97 conference, held in Skövde, Sweden, in September 1997. The conference brought together researchers from biology and computer science to discuss the use of computational techniques in biology, as well as the use of biological metaphors in computing. Examples of the work presented in these papers include computer simulations of embryogenesis; algorithms for protein folding prediction; problem solving using DNA computation; neural-network learning in retina implants; and optimisation algorithms inspired by natural evolution.

Modern computing relies on future and emergent technologies which have been conceived via interaction between computer science, engineering, chemistry, physics and biology. This highly interdisciplinary book presents advances in the fields of parallel, distributed and emergent information processing and computation. The book represents major breakthroughs in parallel quantum protocols, elastic cloud servers, structural properties of interconnection networks, internet of things, morphogenetic collective systems, swarm intelligence and cellular automata, unconventionality in parallel computation, algorithmic information dynamics, localized DNA computation, graph-based cryptography, slime mold inspired nano-electronics and cytoskeleton computers. Features Truly interdisciplinary, spanning computer science, electronics, mathematics and biology Covers widely popular topics of future and emergent computing technologies, cloud computing, parallel computing, DNA computation, security and network analysis, cryptography, and theoretical computer science Provides unique chapters written by top experts in theoretical and applied computer science, information processing and engineering From Parallel to Emergent Computing provides a visionary statement on how computing will advance in the next 25 years and what new fields of science will be involved in computing engineering. This book is a valuable resource for computer scientists working today, and in years to come.

Researchers in several fields are exploring computational systems in which interesting global behavior emerges from local interactions among component parts - an approach called emergent computation. In these systems, interactions among simultaneous computations are exploited to improve efficiency, increase flexibility, or provide more realistic models of natural phenomena. These 31 essays define and explore the concept of emergent computation in such areas as artificial networks, adaptive systems, classifier systems, connectionist learning, other learning, and biological networks to determine what properties are required of the supporting architectures that generate them. Many of the essays share the themes of design (how to construct such systems), the importance of preexisting structure to learning and the role of parallelism, and the tension between cooperative and competitive models of interaction. In the introduction, Stephanie Forrest presents several detailed examples of the kinds of problems emergent computation can address. These include showing how emergent computation can lead to efficiency improvements in parallel processing, establishing the connection between emergent computation and nonlinear systems, and comparing two search techniques to show how the emergent-computational approach to a problem differs from other more conventional approaches. Stephanie Forrest is Assistant Professor in the Department of Computer Science at the University of New Mexico. She is also affiliated with the Center for Nonlinear Studies and Computing Division at Los Alamos National Laboratory.

The papers in this book show the tremendous potential of emerging computing paradigms such as genetic algorithms, evolutionary computing, and neural networks for solving problems of engineering design.