### 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.

6more comments