Physics and Church–Turing Thesis

Just appeared on the arXiv today: "The physical Church-Turing thesis and the principles of quantum theory," by Pablo Arrighi and Gilles Dowek. http://arxiv.org/abs/1102.1612

Abstract:

Notoriously, quantum computation shatters complexity theory, but is innocuous to computability theory. Yet several works have shown how quantum theory as it stands could breach the physical Church-Turing thesis. We draw a clear line as to when this is the case, in a way that is inspired by Gandy. Gandy formulates postulates about physics, such as homogeneity of space and time, bounded density and velocity of information --- and proves that the physical Church-Turing thesis is a consequence of these postulates. We provide a quantum version of the theorem. Thus this approach exhibits a formal non-trivial interplay between theoretical physics symmetries and computability assumptions.

The Church-Turing thesis

The Church-Turing thesis asserting that "everything computable is computable by a Turing machine," (and its sharper forms regarding efficient computation) can be regarded as laws of physics. However, there is no strong connections between the thesis and computability in general and theoretical physics. This is discussed in this related question on the CS site.

When it come to the original form of the Church-Turing thesis, (namely when efficiency of computation is not an issue) it does not seem to matter if you allow quantum mechanics or work just within classical mechanics. However, for a model of computation based on physics it is important to specify what are the available approximations or, in other words, the way errors are modeled. (Failing to do it may lead even to "devices" capable of solving undecidable problems.) There are various proposed derivation of the Church-Turing thesis from physics laws. On the other hand, there are various "hypothetical physical worlds" which are in some tension with the Church-Turing thesis (but whether they contradict it is by itself an interesting philosophical question). A paper by Pitowsky "The Physical Church’s Thesis and Physical Computational Complexity", Iyun 39, 81-99 (1990) deals with such hypothetical physical worlds. See also the paper by Itamar Pitowsky and Oron Shagrir: "The Church-Turing Thesis and Hyper Computation", Minds and Machines 13, 87-101 (2003). Oron Shagrir have written several philosophical papers about the Church-Turing thesis see his webpage. (See also this blog post.) Overall these studies are more of a philosophical nature.

The efficient Church-Turing thesis

Concerning the efficient Church-Turing thesis, namely regarding computations in polynomial time, as Peter Shor mentioned, the rules of quantum physics allows for computationally superior computers compared to classical computation. (This depends on computational complexity conjectures e.g., regarding factoring bot being in P.) The efficient Church-Turing thesis (first stated, as far as I know, by Wolfram in the 80s) is "A (probabilistic) Turing machine can efficiently simulate any realistic model of computation." The analogous conjecture for quantum computers is "A quantum Turing machine can efficiently simulate any realistic model of computation." One aspect of the effecient Church-Turing thesis (again, both in its classical and quantum version) is that NP hard problems cannot be computed efficiently by any computational device. This is a physics conjecture of a sort (but it depends, of course, on conjectures from computational complexity and asymptotic issues.) There are some interesting attempts to relate the impossibility to solve NP complete problems to physics.

One interesting aspect of (both classic and quantum version of) the efficient Church-Turing thesis is that they imply that physical models which requires computationally-unfeasible computations are unrealistic. It is an interesting question if this should be taken into consideration in model-building.

Remark: Oron Shagrir and Yuri Gurevich pointed out to me that my formulation of the Church-Turing thesis is a modern version from the last 2-3 decades which is different from Church's and Turing's original formulation. See Yuri's answer below.

There is a body of literature on the topic of supertasks, which are computational tasks involving infinitely many steps. A large part of this work involves a purely mathematical analysis and development of the concept, such as my work on infinite time Turing machines ("Infinite time Turing machines," with Andy Lewis in the Journal of Symbolic Logic, 65(2):567-604, 2000, ArXiv version) and other work on higher recursion theory, E-recursion and other infinitary models of computability. All of these computational models exhibit functions that are not computable by Turing machines, but are computable with respect to the infinitary model. (See this MO answer for an entertaining supertask example.)

Another part of the work,however, has considered the topic of your question, about the extent to which we might actually hope to carry out such infinitary computations. The idea is that the real universe exhibits relativistic phenomenon of which we might take advantage for computational effect, and doing so might take us beyond the Turing barrier. Hogarth and others have described physical models, Malament-Hogarth spacetimes, in which one observer has access to the results of an infinite computation carried out by another in that world. To get the idea, imagine assigning your graduate students, and their graduate students and so on in perpetuity, the task of searching for an arithmetic counterexample, while flying in ever-faster rockets around the Earth, signaling when a counterexample has been found. Because of relativistic time foreshortening, their entire infinite journey will amount to a total finite amount of time for you, and so you can get the answer in finite time.

Philip Welch recently wrote an excellent survey and also this article describing some of the physical models in which one can compute non-computable functions by a physical procedure, among several other articles on the topic on his web page.