Computability in Europe 2006

When we currently think of computability , we have the picture of a computing machine in our mind as we use it every day: a desktop personal computer, a workstation, a laptop. All of these computers use an architecture that is normally called the von Neumann architecture based on bits (zeroes and ones) and the computational model of (something equivalent to) a Turing machine.A lot of things can be done with these machines. It has become normal for us to sit in the airport lounge with a laptop, use a wireless network and access a physical machine on a different continent with no apparent physical connection. Most of the achievements of computing of the late 1990s and the first years of the 21st century would have been considered science fiction (and possibly beyond science fiction) by the computability theorists who started this development in the 1940s and 1950s. While we can do amazing things with von Neumann computers, there are two facts about classical computability that we cannot ignore:1. (von Neumann) computability provably has its limits, both abstractly (the halting problem is not computable), but also pragmatically (there are no feasible algorithms for a number of practically relevant problems), 2. and there are still some major gaps in the understanding of the underlying theory, the most famous being the P=NP problem that has been listed as one of the seven Clay Millennium Problems.Especially the first fact is vexing: a lot of problems that are easy for human beings or other natural systems seem to be hard for the von Neumann computer. This discrepancy spawned the interest in alternative models of computation, and we find ourselves in a situation as thrilling and exciting as the time of the early computer pioneers: models like quantum computing, DNA computing, molecular computing, and others are being proposed, and put to test both theoretically and in practice. So far, no one can say which (if any) of these models will survive and become as important or even more important than von Neumann computers. Yet, the analogy to the 1950s is striking: we are once again dealing with theoretical models that cannot yet be fully tested in real life as there are engineering problems to be overcome. In the late 1990s, the first quantum computers have been built in Los Alamos with very few qubits. It is unknown and disputed whether quantum computers will ever grow beyond 10 qubits. Like Church, Turing and Kleene in the 1930s and 1940s, current theoretical researchers have more information at their disposal than their colleagues working on the practical side. In a situation of many options and possible directions for the future, computability theory can provide guidance and the theoretical foundations for more pragmatic developments if it enters a synergetic feedback loop and includes the results from the science labs into its investigations. Computability in Europe 2006: Logical Approaches to Computational Barriers is the second conference in the new Computability in Europe (CiE) conference series which had its start in June 2005 in Amsterdam with the conference CiE 2005: New Computational Paradigms, and which addresses the role of Computability Theory at the beginning of this new Millennium. The next conferences in the CiE serie will be CiE 2007: Computation and Logic in the Real World in Siena, Italy; CiE 2008: Logic and Theory of Algorithms in Athens, Greece; and CiE 2009: Mathematical Theory and Computational Practice in Heidelberg, Germany.