Computability: The Greatest Law of Physics

Wigner famously declared mathematics to be “unreasonable effective” in the natural sciences. It is indeed something magical about the fact that if we have a mathematical theory and some mathematically representable aspect of reality then we can carry out abstract, conceptual, mathematical reasoning and formulate some new facts about reality which will turn out to be true. Even more amazing, such theoretical reasoning can lead to genuine discoveries about reality — new observations. According to Lakatos this is the most important thing about a scientific theory. Indeed Eddington would have never ventured to the island of Principe to take measurements of the Hyades during a solar eclipse unless Relativity predicted that he would see something interesting. Haley would have never predicted the return of the comet that now bears his name.

The validity of a scientific theory rests on the correspondence between a mathematical model and measurements made of the physical world. The same relationship between an abstract, essentially mathematical model, and the physical world, usually a special-purpose device, lies also at the heart of computation. This relation, called the implementation relation by Chalmers, was first introduced in the context of trying to figure out what things can be said to compute. For most Computer Scientists this is not particularly exciting or interesting because of our Engineering-minded approach. We build computers so that they satisfy an implementation relation. In fact we rarely distinguish between “abstract” mathematical computation and “concrete” physical computation. We casually deal in “abstract machines”, such as the Turing Machine, without worrying too much whether we are talking about its mathematical definition or an actual physical instance. We just know that the latter can be easily built so that it implements the former.

However for those interested in Natural Computing, the implementation relation is far more interesting because an implementation relation is discovered rather than constructed. Some natural occurring phenomenon (the behaviour of slime mold, for example) can be used to calculate with because it implements a complex computation. Natural Computing works because such phenomena, implementing complex computations, exist. In some trivial sense any physical system can be used to compute facts about its own mathematical model, although that is hardly interesting. Natural Computing is interesting because particular physical systems can compute fast solutions to problems of general interest, which can actually encode the evolutions of other physical systems that evolve much slower or that are complicated or expensive to build.

What is truly fascinating is that no physical system can implement an abstract model which is mathematically uncomputable. For me this is indeed the greatest law of physics in terms of its generality, as it relates any abstract mathematical model to any physical system. The non-implementability of uncomputable models is an impossibility result of a staggering magnitude. And it is truly a falsifiable (in the logical, Popperian sense) scientific law. Scientists, most notably Penrose, suggest that some neuronal processes in the brain may be physical yet uncomputable, but the evidence for this is very sketchy. More generally, philosophers propose that the brain is an instance of a physical yet non-computable process, mainly based on interpretations of Goedel’s incompleteness theorem which I find rather naive. But at least this shows that we can logically conceive of such systems.

In fact I would say that not just computability in the sense of Church-Turing, but the whole of computability theory, including complexity analysis, is essentially formulating extremely general laws of physics between whole classes of formal models and any physical system which might implement them. Computer Science is truly deserving of its name!

About Dan Ghica

Reader in Semantics of Programming Languages // University of Birmingham // //
This entry was posted in armchair philosophy. Bookmark the permalink.

One Response to Computability: The Greatest Law of Physics

Leave a Reply

Your email address will not be published. Required fields are marked *


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>