Undecidable problems limit physical theories

Question

Does the existence of undecidable problems immediately imply the non-predictability of physical systems? Let us consider the halting problem, first we construct a physical UTM, say using the usual circuit based construction. Then there can be no decidable physical theory which can determine, given any input setting of the circuits, whether the circuit will halt. This seems a triviality, but doesn’t this give us a weak sort of unpredictability without reference to quantum or chaotic considerations? Moreover we can strengthen the above argument by noting that there is nothing special about the circuit based UTM, so we have that the behavior of a physical system is in general undecidable at any level where a UTM can be constructed.

Edit: as pointed out by both Babou and Ben Crowell, my suggested circuit construction is merely an LBA. As I argued in the comments, I find it easy, and intuitive to imagine a machine which is physical but is not linearly bounded. Simply construct a machine (robot) which can mechanically move left/right on an input arbitrarily many times, and assume it has a finite, but non expiring power source. Now we also run into the problem that the universe is finite, but that lets us conclude either that the universe is finite, or the originally hoped for consequence must be true (that would still be a surprising conclusion to arrive at from the above argument).

Answer 1

This was initially intended as a comment, as it side-steps a bit the question. But I think it does answer in its own way.

What is known, or attempted so far, shows that connecting computation theory with physics can be a pretty subtle endeavour, and I am afraid that the approach suggested in the question is probably a bit too crude. I am not sure it is much better than the classical argument that, everything being finite, all we need is finite state automata theory, and that studying Turing machines is a waste of time. (Not my view of things)

Why should such issues be addressed with caution

I should probably motivate the above comparison with the finite automata argument. My perception is that computability is, maybe even more than complexity, an asymptotic theory: what matters is what occurs at infinity. But we do not know whether the universe is finite or infinite. If it is finite, then what would be the point of considering infinite computations. The following concerns physics, and I am not a physicist. I do my best to be accurate, but you have been warned.

We often see the Big Bang as a "time" when the whole universe was a very tiny something, with a very small size. But if it had a size at some point, how did it transform into something infinite at a later time. I am not trying to say it is impossible ... I do not have the slightest idea. But it could be that it always was infinite.

Then, let us consider the universe as infinite. Does it help us? Well, we have some problems with the speed of light. If we consider what may be relevant here (where we are), we have to consider that we can be concerned only by a part of the universe that is included in a finite sphere. The radius $r$ of that sphere is such that the relative speed of two points at distance $r$ due to expansion is equal to the speed of light. According to what we currently know, without a future variation in expansion speed, nothing outside that sphere will ever be of concern to us. So the universe is finite for us for all practical purposes. Actually, things are even worse if you consider the contents of this relevant universe: it is shrinking (unless there is some creation process). The reason is that the sphere is expanding beyond its own diameter, carrying with it some of its content that becomes irrelevant too. Remark: that sphere is not what is called the observable universe (which is dependent on the age of the universe), it is much larger.

Thus, not only "our" universe is finite, but its resources might be shrinking. It is possible that in so many billions years, only our galaxy might be still relevant to us (assuming we still exist), with the Andromeda galaxy which will hit the Milky Way before then.

Well, I do not know what is considered established at this time, but it shows at least that assuming infinity is a big assumption.

However, is it the case that physical limitations prevent us from using computability theory. All that can be concluded from the above is that it may be unreasonable to draw physical conclusions from the theoretical work on Turing Machines and the halting problem.

However the concerned techniques may also give useful results when applied to devices or formalisms that are not Turing-complete. I would not try to go into details, if only because algorithmic complexity is not my area, but I would guess that, if the structure of the universe is discrete, complexity could be in some form relevant to the behavior of some phenomena. Of couse, this is only wild speculation on my part. Some of the research I reference below is related to such discreteness issues.

Some examples of work relating physics and computation theory

There is a significant body of work trying to tie computation and physics, most of which I barely know of. So, please, do not rely on anything I might say, but simply take it as pointers to search for potentially relevant work.

A good part of that work is concerned with thermodynamic aspects, such as the possibility of reversible computing with no energy cost. I thinks this ties with functional programming as it is side-effects that cost energy (but do not trust me). You may take wikipedia as an introduction, but Google will yield many references.

There is also work trying to tie Church-Turing thesis and physics, involving information density among other things. See for example:

• The physical Church-Turing thesis and the principles of quantum theory

• Around the Physical Church-Turing Thesis: Cellular Automata, Formal Languages, and the Principles of Quantum Theory,

• Physics and Church-Turing Thesis.

I vaguely recall seen other interesting takes on this, but it escapes me right-now.

Then you have Lamport's work on clocks synchronization and relativity in distributed systems.

And, of course, you have quantum computing that apparently changes some (achievable) time-complexities, though it does not affect computability.

Another take is Wolfram's work on modelling physical laws with cellular automata, though the real benefits of this work seem disputed.

I think that trying to understand all this work could get you closer to understanding how you can tie some computability knowledge with (as implying) theoretical limitations of the physical world, though the trend so far was more to tie limitations of computability to (as consequences of) properties of the physical universe.

One possible problem in all this is the self-embedding of all our theories (mathematics, computation, physics, ...) within the limits of concepts that are syntactically expressible (i.e. by a language) which might set a limit on the expressive power of our science. But I am not sure whether the preceding sentence has meaning ... sorry about that, it is the best I can do to express one nagging doubt.

As an account of personal disappointment, I would add that physicists (at least on http://physics.stackexchange.com) are not very amicable to discussing what other sciences could have to say about physical issues (though they are quite willing to discuss what physics may have to say about other sciences).

Answer 2

Babou,

It's indeed a very interesting question but as said above a lot of literature has been produced on the subject. The least you can say once you have read all that is that mapping UTM to physical systems is far from straightforward - however seducing the idea is.

Personally I like to start from the concept of reversible computing introduced by Landauer and mentioned in the previous answers. There seems to be a conceptual connection between entropy and UTM.

Think about it this way: imagine you want to walk from point A to point B (geographically distinct) using a deterministic plan (i.e. a number of steps which can be written down in advance like a UTM: walk straight for 100m, turn right at the bakery, walk 50m etc.). You can walk the distance once. Twice. Three times. How many times can you do it? Unless you include an infinite stock of food and water in your plan, you'll have to stop after a finite number of journeys. But although a UTM tape is infinite, the number of steps of the TM itself has to be written in a finite number of characters. Therefore your plan cannot include an infinite amount of food and water.

Now energy is a conservative quantity. So you could think a finite amount of provisions should suffice. But clearly this is not your issue here. Even if you travel very slowly between A and B, your body will turn your food into something you cannot consume anymore. Note that if you try to escape that issue and go INFINITELY slowly (quasi-statically between A and B) you cannot write your "plan" with a finite number of characters anymore. So it's the increase of thermodynamic entropy (degradation of food and water through the processing of your body) which seems to pose a limit to the number of journeys you can make while sticking to a deterministic plan (i.e. a UTM).

If this is right, the unpredictability of TM has to be mapped to the increase of thermodynamic entropy. Note how this seems quite counter-intuitive (as said before that sort of mapping is far from trivial): to infinity the increase of thermodynamic entropy leads to an equilibrium i.e. something stable; but the same infinite limit of the corresponding UTM leads to a random behavior (i.e. we are not sure what sort of output). That's even more striking with a ball rolling down a convex curve with frictions: thermodynamic entropy makes the ball stop at the low ebb of the curve which is something quite easy to predict; but the equivalent UTM will tell you that "something random" happens in the end which cannot be predicted. Is it that we have to map that unpredictability to the random motion of atoms created by the heat dissipation of the movement of the ball against the surface of the curve? That's an open question but at least it shows you the difficulty.

Hope that helps!

Answer 3

The question asks in part about nonpredictability of physical systems. Undecidability does show up in a few physics problems. An early survey by this is by Wolfram, Undecidability and Intractability in Theoretical Physics (or here) and this area continues to expand. However, a better way to understand physical inherent unpredictability is more via what is known as "sensitive dependence on initial conditions" aka butterfly effect. This can be studied using the Lorentz attractor as a semi-toy model.

Answer 4

The question is interesting (you may want to check a related question "Is there a connection between the halting problem and thermodynamic entropy?")

The core of the problem is what comes first mathematics or physics? Well physics is the answer. A quote by Einstein says: "the kind of mathematics we do, depends on the world we live" (if i'm not mistaken this is in "Einstein, Philosopher-Scientist") (and another related, and slightly paraphrased "Nature does not care about our mathematical difficulties. It integrates empirically"). So in this sense certain physical features are reflected in the mathematical symbolism and procedure. But one can also take the opposite view that mathematics defines physics (a view that is quite popular in certain circles).

There is a passage in the introduction of the book "Linear Algebra" by J B. Fraleigh, R A. Beauregard (a good book on the subject and a point i wanted to address given the opportunity)

Numbers exist only in our minds. There is no physical entity that is number 1. If there were, 1 would be in a place of honor in some great museum of science, and past it would file a steady stream of mathematicians gazing at 1 in wonder and awe.

Yet this is not true, there is indeed something which we experience and is one (literaly), the sun (careful not the stars at night nor the moon which is not perceived as one under all circumstances, the sun, the one and only visible thing in the sky in daylight). (and indeed it has been historicaly an object of honor and awe from the humankind). One can go on and discuss other things which we experience as two or three and four (two hands, five fingers and so on), but the main point has been given (for more information search for "pre-history and history of number systems")

Say for a minute that a mathematical result would state something but then a physical theory would provide a procedure to achieve the opposite (effectively a constructive proof of the opposite). Then something would be wrong, these are related especialy when they use the exact same formalism. It is intuitive that these should be related somehow.

For example an mathematical imposibility result would limit the mathematical description of a physical theory that would need such a result and so on. An example that i can use right now is the so-called "theory of everything". It is supposed to describe in mathematical form all the physical interactions that take place, so in effect describe everything. However by Goedel's theorem it is known that such a description would be incomplete in one sense or another. Does this say something about the world we live? Most probably.

But imposibility results are known in purely physical terms and most of them are related to thermodynamics. For example "Heat flows from hot to cold". This is an imposibility result. But this also limits any mathematical result which would imply (when applied in the proper context) that heat flows from cold to hot, this does not happen. So mathematics can be limited by physical terms. The real question is what is the exact connection (if any) between these two and this is a very interesting question with interesting anf far-reaching results. For example you can check the work of G. Chaitin which relates information theory, Goedel's theorems and bio-physical systems for a start. Some other connections have been already mentioned like reversible computing, quantum computing and so on.

Last but not least remember that physics relies on experiment to formulate and verify things and not symbolic proofs. (A) Mathematical description of a physical theory is important in terms of calculations, so a problematic mathematics may limit or otherwise pose problems in the calculation power of the theory, experiment remains nevertheless. And remember that physicists are usualy among the creators of new mathematics as needed (e.g Calculus and Differential Equations, Probabilities, Tensor analysis, Renormalisation procedure in quantum mechanics, Analytic regularisation and so on)

As regards your example connecting un-predictability with a TM, the connection can be done and it might require an unbounded tape provided the machine will need to calculate with infinite precision (i.e irrational/transcendental numbers which are in no-way excluded from a physical system). Then an LBA machine will not be powerful enough to calculate a given physical system and one enters the infinite tape UTM which has a halting problem. The question whether unpredictatibility can be attributed to initial conditions (the taught formal definition of chaotic behaviour) or the computation itself is not of the essence since it only shifts the problem to another place instead of addresing it.

Answer 5

I think a good model for this is Conway's game of life.

Since we invented the rules, we know them perfectly. This is analogous to a physical theory.

Yet, despite how simple the rules are, and the fact that we know them, life is undecidable.

Similarly, even if we learned all the laws of physics, it could turn out they are undecidable as well.

There is not really anything you can do about it. One thing to keep in mind though is that you can predict Conway's game of life for any finite number of steps. This might turn out to be the same for physics.

Answer 6

Does the existence of undecidable problems immediately imply the non-predictability of physical systems?

No.

first we construct a physical UTM, say using the usual circuit based construction.

A universal Turing machine is a Turing machine. A Turing machine has an infinite (or infinitely extensible) tape. Therefore you can't build one out of circuits. What you can build is a linear bounded automaton (LBA).

Then there can be no decidable physical theory which can determine, given any input setting of the circuits, whether the circuit will halt.

The halting problem is decidable for an LBA, so your argument fails.