# Undecidable problems limit physical theories

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

• Perhaps better suited to Physics? – David Richerby May 24 '15 at 23:35
• @DavidRicherby Physicists consider this at best as a matter of opinion. I cannot unfortunately point to examples as they delete them. That is their point of view considering any role computability could play in physical theory, other than providing them with computers. I am dead serious. – babou May 24 '15 at 23:57
• @babou The experts on the behaviour of the universe are physicists, not computer scientists. If the physicists don't think this is a "real" question then we have a problem: the experts don't consider it worth answering so only the non-expert answers remain. – David Richerby May 25 '15 at 8:07
• I spent significant time writing a question about a possible role of computation theory in theoretical physics (not just as computational tool, or as universal modeling tool witjout perspicuity), asking for published refeered references. It was rejected as "primarily opinion-based". And it was quickly deleted so that no one can even comment it ... I did receive one or two relevant comments. I wonder what they are afraid of. But this reinforced me in refusing to condone the trigger happy closing policies, especially based on flimsy assessment such as opinion based. I can send you my copy of it. – babou May 25 '15 at 9:56
• @BenCrowell So you might ask for my question in physics to be undeleted, as it was only asking for such references. and hopefully some comments on them. BTW, there is only a single paper. – babou May 25 '15 at 15:21

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:

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

• The question posed a specific argument and asked if it was right. This isn't an answer to the question. – Ben Crowell May 25 '15 at 14:48
• 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. This would make a good question on physics.SE, but it doesn't help to answer the question being asked here. – Ben Crowell May 25 '15 at 14:52
• This site has a lot of questions asked rather naively, and members with higher rep tend to try to answer in a useful, pedagogical way. Your answer is only telling off someone with no rep, who does not have the maturity to ask a question with a chance of being meaningful. I tried to answer in a well motivated way, and also give him context so that he can look at real scientific work on similar issues. Your answer says no: but you never say why infinity should be a problem. It is not a real answer. What does it teach? – babou May 25 '15 at 15:32
• Why do you assert that trying to determine whether we have an infinite universe available is irrelevant for the question? – babou May 25 '15 at 15:49

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.

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.

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!

• Doesn't this mean that, essentially, we can predict that either the UTM will halt or it will run out of energy? Since we know how much energy is available to it, we can just simulate the UTM and its energy consumption until it's used its available energy, and then we know the answer without having to decide the halting problem. – David Richerby Aug 9 '16 at 14:45
• Oh hi David!! Nice try but that would infringe on energy conservation (classic mistake for non-physicists). From the moment you have defined A, B and your "plan", walking back and forth between A and B doesn't consume any energy as this model is adiabatic (i.e. isolated, nothing comes in or out). Even if you assume walking consumes energy (which is far from trivial if you walk on a flat surface), this energy is just transferred somewhere else to the system and you should be able to recover it with a simple finite UTM. In other words your model is E=cste. Doesn't help much does it? – Jerome Aug 9 '16 at 15:19
• The analogy about walking around isn't helping me: I'm talking about Turing machines. Suppose I have a physical implementation of a Turing machine. As we know, there's no algorithm I can use to determine if the abstract TM it embodies will terminate on a given input. My claim is that I can simulate it on my desktop PC to determine whether it will halt for a particular input before it breaks or runs out of energy or whatever, so the state of the physical TM in the future is, after all, a computable function of the current state. I don't see how any of that violates conservation of energy. – David Richerby Aug 9 '16 at 15:57
• I didn't read the whole of this, but it starts out as a comment on another answer. Please don't use answers to start discussions; there's Computer Science Chat for that. (cc @DavidRicherby) – Raphael Aug 9 '16 at 21:36
• Thanks Raphael. I don't have enough credits, I quickly reply here. David, even if your UTM says nothing about energy you include some lines of code to explain why I will stop walking. So your model implicitly encompasses a quantity Q which will "wear out" along the way. You assume Q exists. Occam's Razor tells you that risky. Especially when you know that another explanation requiring fewer assumptions seems to work. Although, like me, you manage to model the walk with a UTM, your code is longer than mine: to me the existence of a UTM itself suffices to explain why I will stop walking – Jerome Aug 10 '16 at 7:10

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.

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.

• Maybe you can read my updated answer (I was still working on it) and be more explicit and precise about why you think my answer is wrong = the part you downvoted in particular, as I certainly do not see where it could be incompatible with yours. At least your technical point of view could be useful to our community, while just downvoting means either that you consider all my references to published work as nonsense, or that our community is not worth more than scorn. – babou May 25 '15 at 15:04
• @babou: A downvote is not a personal attack on you or a statement of "scorn" for this community. I explained the reason for my downvote. If you want to discuss your answer, the place to do that would be in comments on your answer, not in comments on mine. – Ben Crowell May 25 '15 at 15:06
• If you believe what you just wrote in your comment, maybe you should read again your own "answer". - - - - - Just to make things clear ... I never downvote. I comment when I feel comments are needed. – babou May 25 '15 at 15:38
• I've edited the question to respond to your answer (which babou also brought up), because I find that answer unsatisfactory. Thank you for responding though, maybe you can point out to me why my imagined non-LB, UTM fails? – user2663116 May 25 '15 at 20:36
• In a TM, it's only the tape that must be of infinite size. A finite-sized physical machine that is capable of visiting a countably infinite number of physical locations ("cells") would suffice, so to show "[t]herefore you can't build one out of circuits", you need to show that this is impossible. (Maybe this can be argued on the basis of the energy requirements of the machine, but you don't do so.) – j_random_hacker Aug 9 '16 at 10:30