Church-Turing hypothesis as a fundamental law of physics

The Church-Turing hypothesis says one can not build a computing device which has more computing power (in terms of computability) than the abstract model of Turing machine. So, there is something in our laws of physics which prevent us from making devices which are more powerful than Turing machine, so in this respect it can be viewed as a law of physics.

What is the physicists' view of Church-Turing hypothesis?

Can the Church-Turing hypothesis be deduced from other fundamental law of physics?

-
Deutsch's "Fabric of Reality" may be of interest to you. en.wikipedia.org/wiki/The_Fabric_of_Reality – user7757 Mar 6 '14 at 14:12

I love Alonzo Church, but not for his contributions to Physics.

The connection between algorithms and the real physical world can never be more than approximate. Noise is essential to the concept of probability, and probability is now essential to Physics via Quantum Mechanics. But Wiener saw this even classically, so I will go classical.

No finite apparatus can exactly reproduce a string of bits, e.g., consider how one would either produce, or process, or detect a square wave. All algorithms are Boolean, but no machines are Boolean: they can, at best, be approximately, i.e., noisily, Boolean.

Now the division of a real phenomenon into signal + noise is subjective. For Nature, there is only signal, never noise.

It is essential to the concept of computation or algorithm or Turing machine that somebody generates a square wave, a string of bits, somone else (which can be a machine) processes the string of bits, and then someone else detects the signal in the product of that process. There are never any perfect square wave inputs, and hence the information-theoretic modelling of an input by a string of bits is always a subjective division into signal + noise---there can never be a perfect realisation of any of the algorithms of which a Turing machine is capable so the transform of the input is never truly one of the algorithms studied---and detection is, as any of my signal processing students know, a matter of compromises and errors and noise.

All the popular discussion of «Physics as Computation» is claptrap. The only truly scientific and physical discussion going on in this regard goes on among signal processing engineers.

-
+1 very good points. Not sure how much I agree though (although I agree wholeheartedly with your first clause). I'll have to think about this carefully: I think my misgivings come from my belief in physics as an extension of mathematics (i.e. roughly as made up of the adding of experimental design, falsifiability, hypothesis testing to the programme of Hilbert's sixth problem), but I'll have to think some more to be sure what I am thinking! I think I even subscribe to Tegmark's mathematical universe ideas somewhat. Out of interest: do you have any researchers in mind in your last line? – WetSavannaAnimal aka Rod Vance Nov 22 '13 at 5:23
@WetSavannaAnimalakaRodVance No one in particular (except me...) Lots of qualified people are making incremental, practical, advances in this, but nothing (except mine....) that can be put in a headline. – joseph f. johnson Nov 26 '13 at 3:21

Complement to the initial answer (below)

My initial answer to this question (below) was only based on my knowledge of syntactic and semantics issues in computing, as well as some knowledge of various computing techniques such as computing on reals with infinite precision, or more precisely with arbitrary precision.

Looking for a better understanding of the issue, I found that it is currently actively researched. Though I have not explored much, I found that my perception of the crucial role of denumerability, which can be traced to the fact that everything is expressed syntactically, hence with denumerable systems of symbols, or symbols conbinations, is indeed justified.

One approach to prove Church-Turing thesis as a law of physics relies on assuming a specific property of the physical world, presented as dual of the limitation on the speed of light and information, which is a limitation on the space density of information, both limitations together ensuring density limitation in space-time. The translation of this new law in physical terms can actually be subtle to account for various existing physical laws. This apparently excludes unregulated use of real numbers.

Giving a bound to the amount of information to be found in a given volume of space-time seems to be the direct counterpart of the fineteness of what can be done by a computing process in finite time, and of the consequent denumerability of whatever may be considered without setting a time limitation.

I am also addind a note at the end to explain why, depite their infinite tape, Turing machines must be considered a physical model of computation, and have been thus considered by most people, afaik.

Note: I try to give the best answer I can, but I am stretching my confidence in my own understanding. The distinction between mathematics and physics is a topic I find fascinating (though I do not have much to say about it), and it is at the heart of the question, imho.

I somewhat disagree with Ben Crowell's interpretation of Church-Turing thesis. If it were the observation that a given variety of models of computation are all equivalent, it should be a mathematically provable hypothesis, or at least we could hope for a proof. This is not the case because the thesis states indeed the a function is computable according to whatever model of computation only if it is computable by a Turing machine (hence by any Turing complete model).

However this thesis is indeed motivated by the fact that all of the many models of computations that were designed by mathematicians and logicians turned out to be equivalent (a few being a bit weaker).

It is true that the Turing machine has an infinite memory tape, which is not too physical. This is not really essential since the interesting results are those computable in finite time, thus using only a finite part of the infinite tape. The tape is chosen to be infinite because it is not known in advance how much will be needed. The infinity of the tape becomes a problem in itself only when envisionning the possibility of infinite time, for example in Closed timelike curves. Many "non physical", or "not yet physical" (?) models of computation have been considered by mathematicians, which could become "physical" (that is, "operational") if ... (see hypercomputation). An interesting example is also oracle machines: what can we compute if we know how to solve such and such problem (not Turing computable, of course). If some physical breakthrough actually allowed to solve this problem, the problems addressable by oracle machine would become computable.

The wording of the previous paragraph actually means that, despite its infinite tape, the Turing machine is actually viewed as a physical device (by computer scientists if not by physicists), even if somewhat idealized. This is probably because a computer scientist considers that an infinite object is computable, or definable, if it is the limit of a sequence of finite objects that are all computable. A machine with infinite tape may be seen as the limit of a sequence of finite tape machines.

In this sense, we can say that Turing computability is a consequence of the laws of physics, since these law allow us to make computers, and we can in principle add memory as needed, for the time we are willing to wait for the result. This is no worse an approximation than physics theories have proved to be so far, given enough time to find out that they only approximate physical reality. This is also no worse than using calculus to reason about phenomena that are ultimately discrete rather than continuous.

But this is not the question being asked. The actual question is whether the Church-Turing hypothesis can be derived from the laws of physics. This thesis is that there is not a more powerful model of computation. If all phenomena describable by existing physical theories can be simulated by a Turing machine (a computer program), that does indicate that there is nothing in these theories that allows for more powerful computing models. But can they be simulated ?

An important chracteristic of Turing-Church computability is its discrete character (this is actually true of all human intellectual activities). It is mostly what people call derisively "symbol pushing". What can be computed is essentially discrete and denumerable. Physics theories are usually express as continuous structures. Are they, or is it just a convenient representation ? If they are continuous, it is not obvious that they can be simulated by a computer, even though computers can to some extent deal with continuous entities, such as real number, finitely represented, but there are all kinds of limitations to these computations and their uses.

Simulating discrete approximations of these theories is probably not satisfactory, and seems (to me at least) a bit tautological, saying that we can simulate with a Turing machine that part of physics that is simulatable by a Turing Machine (because it is discretized). Hence I do not see as very convincing the existence of computer programs that simulate known physics theories, and I do not much believe in the reducibility of physics to computing. But is that necessary to make the Church-Turing thesis a law of physics ?

Furthermore, the Church-Turing thesis is only an hypothesis. We do not know whether it is actually true. But it is true as far as we know, like laws of physics.

To push the problem further, there is a result called the Curry-Howard isomorphism, that shows that computer programs (read "Turing Machines") and mathematical proofs are fundamentally the same, in the sense that they have identical axiomatisation. Hence, for any statement you wish to make about Church-Turing computability, there is an equivalent statement about mathematical proofs.

So the question might also wonder whether our very exclusive way to do mathematics since Euclid's Elements can be viewed as a consequence of a law of physics. And it could restate the last point as: can it be deduced from fundamental laws of physics that mathematical theories must be constructed as we do it. And that applies naturally also to physical theories. Now we get a bit in a loop that I will not try to sort out.

Note about the physicality of Turing machines despite their infinite tape.

The fact that Turing Machines (TM) have infinite tape cannot be construed as evidence that they are not a physical model of computation. The infinite tape is only a mathematical device to simplify the analysis of computability, but whatever they compute only uses a finite tape.

The whole theory could be built on Finite Turing Machines (FTM), i.e., Turing Machines with finite tape, which are actually just finite state automata, the simplest kind of of formal computing device there is. These are definitely easy to implement as physical devices. FTM have a special state they enter when they run out of tape, called MemOverflow.

Then we consider classes of FTM, such that all FTM that differ only by the length of their finite tape belong to the same class.

Let C be such a class. We say that C halts on an input x if there is a FTM M in the class C such that its tape is long enough to be initialized with x, and the computation of M with its tape thus initialized never loops (which is easy to detect on a finite state device) and never enter the state MemOverflow. If there is no such machine M in C, then C is said to not to halt on this input.

For all intents and purposes, there is just no difference between these classes of finite state machines and Turing machines with infinite tapes. Doing the theory is just a bit more awkward for no benefit.

-
"The tape is chosen to be infinite because it is not known in advance how much will be needed. The infinity of the tape becomes a problem in itself only when envisionning the possibility of infinite time, for example in Closed timelike curves." The first and second sentences contradict each other. The first is right, the second wrong. The impossibility of building an infinite tape, i.e., an infinite computer memory, is a problem whenever you run out of memory on your computer and don't know whether the computation would have succeeded given more memory. – Ben Crowell Aug 7 '13 at 0:19
@BenCrowell I am of course aware that the issue with Turing machines is the halting problem. I am only trying to say in simple terms that you get a result only if the TM halts, and if it does it has used only a finite amount of memory. Being able to observe infinite computations, whatever that means (and that is one issue stretching my confidence) would solve the halting problem, but would also require an infinite tape. Is infinite space more to ask than infinite time. I have no idea, not even whether it can make sense. I know little of général relativity, and nothing of its weird solutions. – babou Aug 7 '13 at 17:33
@BenCrowell Mathematics allow us to analyse some of the properties and power that computational models would have under a variety of assumptions. But these abstract classes of computational models are so far empty where effective calculations are concerned. In a way, the OP is asking whether this emptiness is of a mathematical or a physical nature. Trying to imagine a physical implementation of some assumptions is an interesting exercise, and may well be Gödel's motivation for his work on relativity. But talking of infinity in physics is usually a sign that you have a problem. If I may say ... – babou Aug 7 '13 at 17:37
Yet another example of downvoting stupidity. This long contribution, with several independent issues has been downvoted without a word of explanation. What is the use ? What is the purpose ? If something is wrong, it would be better to know what. I know I am screaming to deaf ears, but it is a matter self-respect and hope for progress. – babou Oct 17 '13 at 11:11

You are asking two questions. I am only going to address one of them:

Can the Church-Turing hypothesis be deduced from other fundamental law of physics?

There are two fundamental theories of physics that account for nearly all experiments and observations performed to date: general relativity and the Standard Model. If we could simulate these theories by Turing machines, then the outcomes of any experiment could be deduced by a Turing machine, and then then any physical computational device could be simulated by a Turing machine.

General Relativity: There was a breakthrough in numerical relativity in 2005, and we now have computer programs that do an excellent job of simulating general relativity. While we can't rigorously show that relativity satisfies the Church-Turing hypothesis, this is good evidence that it does.

The Standard Model: Lattice field theory seems to do a very good job of simulating the Standard Model (albeit with enormous computation times). Again, we can't rigorously show that the Standard Model satisfies the Church-Turing hypothesis, but this is good evidence that it does.

If you are talking about computing devices that can be built using any conceivable future technology, these two theories probably cover all of them.

-
Aren't you worried that your last statement might be too similar to Lord Kelvin's alledged statement "there is nothing new to be discovered in physics now. All that remains is more and more precise measurement", or to Planck's professor Phillip von Jolly's "in this field, almost everything is already discovered, and all that remains is to fill a few unimportant holes", just before quanta and relativity. The future may last long. – babou Aug 7 '13 at 19:23
I don't think the holes that would be covered by a theory of quantum gravity are unimportant, but I do think they are impractical. – Peter Shor Aug 7 '13 at 19:54
I think I did not state my objection properly. The issue is not whether existing knowledge or new advances in physics would allow anything practical in terms of new computability, but only whether they might allow for the possibility, however impractical, of achieving a computational feat not possible (or not imaginable) heretofore. Try as we might, we think in a discrete world, and this is essential here. Why is it? Is it us, is it intellectual activity itself, or is it physics that is responsible for it? Is it conceivable that exact analog computation might become possible? If not, why not? – babou Aug 7 '13 at 21:02
I thought I was answering the OP's question: "Can the Church-Turing hypothesis be deduced from other fundamental law of physics?" It currently appears that it can be deduced from either GR and QFT in isolation (although not mathematically rigorously); we can't tell whether it can be deduced from quantum gravity until we have a better understanding of quantum gravity. – Peter Shor Sep 7 '13 at 19:40
As I explain in my answer, I am not convinced by your argument based on existing computer simulation of major physical theories (for lack of ToE), as I explain in my answer. Apparently some scientists researching that issue are not convinced either, and are looking for better arguments. I think you are fundamentally confusing what the physical universe is with our possibly limited ability to describe it. Turing machines belong to the denumerable world. So do formal theories. We do not know that the universe has the same limitation. It may or may not. Syntax vs Semantics. – babou Sep 7 '13 at 21:00

This is an interesting question, but I think the description of the CT thesis given in the first paragraph is inaccurate. AFAIK the CT thesis is not a statement about what we can or can't build. It's more like an observation that a variety of superficially dissimilar mathematical (not physical) models of computation are all equivalent (ignoring complexity). In reality, we can't even build a Turing machine, since a Turing machine has an infinite memory (tape).

When mathematicians create a Turing machine, which has an infinite memory, they're indulging in abstraction. Similarly, when mathematicians talk about real numbers they're also doing an abstraction. The purpose of the abstractions is to make systems whose properties are simple, so that one can prove things about them easily. Physics works by taking finite-precision measurements, doing finite-memory computations on them, and using them to make testable predictions about other finite-precision measurements.

It's possible to take a physical theory, abstract it, and make it into something that's no longer physics but that one can easily write proofs about. An example would be Andreka 2011. In this flavor of work, which is mathematics and not physics, I think it's an open question as to what models of computation are realizable.

Andréka et al., Closed Timelike Curves in Relativistic Computation, http://arxiv.org/abs/1105.0047

-
If you were right in your characterization of the Church-Turing thesis, it would be the Church-Turing Theorem. It's the Church-Turing Thesis. Here is an excerpt from Church: "The proposal to identify these notions with the intuitive notion of effective calculability is first made in the present paper." So does the "intuitive notion of effective calculability" involve physics experiments? Probably not for Church, who was most likely thinking of people scribbling things on pieces of paper. Maybe for Turing, who had mechanical devices in mind from the start. – Peter Shor Aug 6 '13 at 12:14
And Emil Post, also in 1936, says about the Church-Turing hypothesis: "The success of the above program would, for us, change this hypothesis not so much to a definition or to an axiom but to a natural law" While he seems to be talking about a law of neuroscience rather than a law of physics, this comes close to the OP's characterization of the Church-Turing hypothesis. – Peter Shor Aug 6 '13 at 13:00
"If you were right in your characterization of the Church-Turing thesis, it would be the Church-Turing Theorem." I disagree. The CT thesis says that if you come up with a reasonable or "effective" model of computation, Church and Turing think it's going to be equivalent to a Turing machine. That's not a provable mathematical theorem, since "reasonable" and "effective" are undefined, and we can only check equivalence for some small number of models, not for all reasonable/effective models. – Ben Crowell Aug 7 '13 at 0:10
Your disagreement with @PeterShor and myself is due to your statement that "CT thesis ... is more like an observation that ...". This is not accurate. The CT thesis is (as indicated by the word "thesis") a conjecture (not mathematically provable) based on the mathematically proved observation that known computational models are equivalent to or weaker than the Turing Machine. The OP question is whether there could be a physical rather than mathematical proof of CT thesis. The infinite tape is only a convenient mathematical device to make reasonning simpler and its statements less convoluted. – babou Aug 8 '13 at 8:14