Natural Processes and Models of Computation

Various computational paradigms inspired to models of physical and biological systems are being vigorously explored. Quantum and analog computation, evolutionary and molecular computation are prominent cases in point. This multidisciplinary workshop brings together people working in computer science, physics, philosophy, and the cognitive neurosciences with the aim of exploring and comparing these computational paradigms, in the light of questions that arise at the crossroad of mathematical, empirical, and broadly conceptual investigations. The identification of the computable functions with the recursive functions was proposed by Alonzo Church in a communication at an AMS meeting which took place 70 years ago. This proposal, which became known as Church’s thesis, is equivalent to Turing’s thesis, arrived at by Alan Turing on the basis of his independent analysis of human computation processes. Can the standard concept of Turing computability be extended coherently to a stronger notion of computability? Are there Super-Turing, physically realizable processes? These questions, whose investigation was pioneered, during the 1960’s, by Scarpellini, Pour-El, and a few other researchers in connection with analog computation and physical law, can be now explored against the richer background provided by emerging paradigms of natural computation. Which physical processes is one entitled to regard as computations? Are physically and biologically inspired computations relevant to understanding how classes of computational problems can be efficiently solved? Are quantum computers just faster computers than Turing machines? Alternatively, can quantum computation processes enable one to solve problems that no Turing machine can solve? Which finiteness conditions do they meet? How do they contend with Turing’s limits? Which brain and mental processes is one entitled to regard as computations? Conceptual investigations driven by similar questions were pioneered by Turing and von Neumann during the 1950’s on the basis of fundamental concepts from computability theory. These relationships can now be explored against the background of new models of computation: are physically and biologically inspired computations relevant to understanding how biological systems process information and give rise to adaptive and intelligent behaviours