Computation is a physical process in the sense that any information processing must be implemented in some medium that obeys the laws of physics, and is crucially bound by the limitations this imposes. Nonetheless, theoretical computer science is largely a mathematical theory that does not make reference to the laws of physics. For example, there is no need to specify how it is possible that a Turing machine can make deterministic state transitions reliably or that it moves into a particular direction depending on its state. In electronic computers, there is not much need to worry about this, either.
However, with recent developments in many fields it is becoming apparent that computation is a useful concept far beyond the disciplinary boundaries of computer science. Perhaps the most important class of natural computers can be found in biological systems that perform computation on multiple levels. Examples at the smallest scale are kinetic proofreading, molecular sensing, and DNA replication. Further up the hierarchy are gene regulatory networks and protein-protein interaction networks that sense the cellular environment and change the internal state of the cell accordingly. At the super-cellular level there is the brain which has substantial processing capabilities that still surpass the ability of the best electronic computers. It is thus clear that ecologies, organismal communication, economies, and societies must, on some level, compute as well.
While there is an appreciation now that computation does happen in biological systems and that it is worthwhile learning about it, there is no satisfactory theory of natural computation to complement the already established models. There is no reason to assume that natural computers can transcend the limits of classical computability, but existing theories are not sufficient to understand the constraints that natural computers do obey, especially thermodynamic constraints and those imposed by natural selection. It appears, for example, that any natural computation must be performed out of equilibrium, which implies that information processing requires energy to attain finite processing speed and acceptable reliability. Moreover, in biology, the operation of biochemical network computations is typically affected by non-negligible levels of noise. This makes the computation apparently unreliable. Furthermore, considerations of energy dissipation may be equally important in a biological context as the speed of an algorithm is an important phenotype that may be selected in evolution. While the relationship between energetic cost/accuracy and speed is understood for some specific systems, there is no general theory of natural computation. Indeed, there is no understanding of when a natural process constitutes a computation. For example, does a folding amino acid polypeptide compute the protein folding? Within non-equilibrium statistical mechanics, there are promising new theoretical developments including stochastic thermodynamics and fluctuation theorems (such as the celebrated Jarzynski equality), that could result in a theory of natural computers by complementing Turing computability with the laws of thermodynamics.
Another possible approach toward a theory of natural computation has developed from complex systems, network science, and the theory of phase transitions. According to this ansatz there are deep connections between universal computations and the onset of chaos. Model systems for these computations are Wolfram's Class IV cellular automata and Per Bak's sandpile model. These theoretical approaches formulate conditions enabling a system to act as a universal computer.
In the context of biological systems at the molecular scale, special purpose computation is often sufficient. These systems underscore the fact that, for natural computers, there is no meaningful distinction between hardware and software. This makes it difficult to apply basic concepts of computer science. For example, it is typically not clear what it would mean for a biochemical computation to "halt". On the other hand, one must assume that constraints arising from tractability apply to biological computers in the same way as they affect electronic computers.
A theory of natural computers has potential to be applied to engineer efficient real world unconventional computers, especially in synthetic biology. It will be important to understand how computation, energy dissipation, and noise are related so as to be able to engineer stable and efficient molecular computers.
An exception to the specialized computers of biological systems is sufficiently advanced brains that seem to be capable of accurate and universal computation. At the same time, neuronal networks are subject to high levels of synaptic noise. It is not clear how accurate information processing in brains can be achieved despite high levels of internal noise. Despite substantial interest in and funding for research into brain research, the fundamental question of how noise affects computation in the brain remains unresolved.
A large number of approaches have been taken to address parts of these questions: graph theory, microbiology, statistical mechanics, information theory, stochastic processes, cellular signaling– the list goes on. While this has led to considerable insights, the overall research effort is fragmented, and there is a lack of shared vision across the different communities.
The aim of this workshop is to overcome fragmentation by bringing together researchers from different communities that would not normally share a venue. It will break up the usual working patterns of the participants, discuss natural computation across disciplinary boundaries, and thus catalyse new collaborations.
The expected outcome is an increased awareness of methods and insights relevant to natural computers as a result a nucleation of a new community of research.
8 March 2017