# Is limited computational capacity a fundamental obstacle?

Statistical physics books often motivate the necessity of statistical/thermodynamic description by impossibility of calculating the trajectories of all the molecules (I speak of "trajectories" but the discussion applies to the quantum case with the obvious adjustments). The bases of the statistical physics were laid about a hundred years ago, when the limited computation abilities seemed indeed to be an unsurmountable obstacle. The situation has however changed since then and it is not uncommon to suggest that we could in principle attain enough computational power to predict behavior of any system of interest (with the corollary that such ab initio calculation would render redundant the empirical laws of chemistry, biology, economics, psychology, as was debated in the comments that followed the question on whether physics explains biology.)

One could oppose this view by noting that, at a certain scale, the computer itself, being the part of the Universe, would interfere with such a calculation. This might be compounded by the possible non-linearities, which can result in small fluctuations producing wildly different results. Moreover, we are not free to choose the initial state of our computation, given the trajectory taken by the Universe from the Big Bang till now.

In a sense this limitation is similar to those that gave rise to relativity and quantum mechanics: the observer (the computer in this case) influences the outcome of measurement (computation).

The question, to which I would like to obtain a factual answer is:
Is the above described computational capacity limitation fundamental, or not, or it is impossible to say?

Update
A related question: more specifically focused on molecular physics rather than the general problem of computability.

Update 2
Just in case the comments are removed for some reason, I would like to put here the valuable references given by @ChiralAnomaly:

Update 3
To restate the question differently:
Can we model complex (e.g., biological or social) systems without resorting to intermediate concepts ("emergent properties"), directly in terms of basic physical equations.
(This formulation suggests an answer along the lines of the information loss when replacing detailed description by a higher level concept, and the inevitable noise resulting from such an approximate description, which makes explanations in terms of basic concepts meaningless.)

Update 4
Interesting relevant quote from Kondepudi & Prigogine's book Modern Thermodynamics:

The traditional answer to this question is to emphasize that the systems
considered in thermodynamics are so complex (they contain a large number of
interacting particles) that we are obliged to introduce approximations. The
Second Law of thermodynamics would have its roots in these approximations!
Some authors go so far as to state that entropy is only the expression of our
ignorance!
Here again the recent extension of thermodynamics to situations far from
equilibrium is essential. Irreversible processes lead then to new space-time
structures. They play therefore a basic constructive role. No life would be
possible without irreversible processes (Chapter 19). It seems absurd to suggest
that life would be the result of our approximations! We therefore cannot deny the
reality of entropy, the very essence of an arrow of time in nature. We are the
children of evolution and not its progenitors.

• I don't think it definitively answers your question, but you might be interested in these related papers by Scott Aaronson: "NP-complete Problems and Physical Reality" arXiv:quant-ph/0502072, and "Limits on Efficient Computation in the Physical World," arXiv:quant-ph/0412143. Susskind and others have some papers about how computational complexity relates to black holes, like this one: "Computational Complexity and Black Hole Horizons" arXiv:1402.5674. – Chiral Anomaly Apr 1 at 13:35
• What does "fundamental" mean here? – ACuriousMind Apr 1 at 22:57
• @ACuriousMind here *fundamental*=impossible to overcome (with development of technology, computational methods, better knowledge of the universe, etc.) In the same sense as one cannor move faster than the speed of light. – Roger Vadim Apr 2 at 4:42
• @ChiralAnomaly I think efficient vs. non-efficient is a whole different (weaker) "fundamental" obstacle than speed of light or uncertain relation. It is more as if the energy required to get to a certain speed would grow exponentially with the speed: There is no fundamental speed scale/limit, and how much energy you have available is very subjective (a battery? one power plant? earth? the solar system?) – Norbert Schuch Apr 2 at 19:57
• I would like to point out that even if it were the case that one could compute everything exactly, we would still be interested in the laws at the emergent scale because exact calculations just aren't really useful or illuminating when it comes to "understanding" the emergent behavior. For example, it would really be unilluminating to talk of a table in terms of the propagators of constituent elementary particles. – Dvij D.C. Apr 3 at 1:33

So, let's start with the fundamental vagueness of the question. The reason behind this vagueness is the lack of clear unpacking of what is meant by "computation" or "prediction" or "modelling".

Let's suppose for a second that you actually do have an infinitely powerful computer that is able to simulate the dynamics of any number of fundamental particles. How would you use it to "model" or "predict" or "compute" the things that you want? You'd still have to use the high-level "emergent" concepts to set up the problem in terms of fundamental particles. Then you'd use the machine to predict the future state. Then you'd have to reinterpret this microstate back to the level of "emergent" concepts.

On top of that - you most likely would have an astronomical number of possible ways to set up the same high-level initial problem in terms of microstates. So you'd have to approach the whole thing statistically and your end results will be probabilistic over the high-level concepts.

My point is that it is not really the "computational capacity" that is fundamental here. The issue is with setting up initial conditions and interpreting the results. This focusing on "computational capacity" is based on the flawed assumption that we, humans, are "infinitely smart" to be able to interact with it.

• Perhaps* computational capacity* is too specific a term - what I meant is whether we can bypass using the emergent concepts (and hence creatings ciences such as chemistry, biology, etc.) – Roger Vadim Apr 8 at 10:30
• @Vadim then check out my take on "emergent concepts" in the liked answer. They are "emerging" in our heads - not in reality. – Kostya Apr 8 at 10:51
• All of the physics (and knowledge) exists only in our heads. – Roger Vadim Apr 8 at 11:51
• @Vadim The "emergent" stuff is usually fuzzy - there are exceptions and situations that are not easily classified into "emergent" buckets. Take your "genetic code" example: are non-standard amino acids, codon variations, all the ribosomal frameshift shenanigans part of it? How about organisms that flip between different codings? Are viruses organisms? – Kostya Apr 8 at 12:32
• @Vadim But I do get your drift - you are asking how do I know that the molecular/atomic/particle level is not "emergent" itself. And it most likely isn't - I've addressed that once here physics.stackexchange.com/a/1903/386 . But I still believe that molecular level description is less wrong that "genetic code" description. Anyhow, that's a philosophy discussion. In comments. I think I'd finish it there. – Kostya Apr 8 at 12:39

The question could easily introduce opinion-based answers. To avoid this danger, I'll try to stick to our present knowledge and understanding, avoiding any speculation on the future evolution of the field.

I think that two related assumptions are underlying this question and should be elicited.

The first is that computation always implies the possibility of predicting the behavior of a system. I think that this assumption strongly overlooks what computation is. The physical basis of any simulation is to establish a mapping between the steps of an algorithm and the states of a time-evolving physical system (the computer). Therefore, to have predictions, we need an algorithm sufficiently powerful and a physical system with enough states to describe the system of interest. The typical approach is to find a suitable set of basic building blocks such that a faithful algorithmic description of their behavior is possible. For example, we can start with atoms, interaction laws, and a few prescriptions for their dynamic behavior. Then, we map a starting configuration of atoms into some internal state (bits, qubits, or whatever we can use) of a physical system (the computer), and we start its dynamical evolution mirroring the steps of the algorithm.

It should be clear that his kind of computation is just a way to have the full information on the microscopic states of the system in the cases it is not possible to obtain the same information by direct measurements on the system of interest. The best prediction we may hope to get from this computation is predicting the final microscopic state after some time. Now, the real question is if this kind of prediction is really what we are looking for. I think that the factual answer coming from the present status of Science is negative. The bare detailed knowledge of the microscopic state may be an interesting result but does not provide insight by itself. This observation brings us to the next point.

The second implicit assumption of the question is that Statistical Physics exists only because of our limited computational capabilities. I think the history of Statistical Physics shows that it is a theory designed to extract the emergent phenomena in complex systems. Therefore, it should not be seen as expedient to overcome limited computational abilities but as the scientific way to get insight from a microscopic description by a systematic and controlled coarse-graining process.

For the above reasons, my answer to the question in the title is the following.

Our present limited computational capacity seems to preclude the possibility of direct modeling of arbitrarily complex systems. However, at least for those systems about which we do not need the full information about the initial state, we could model them better and better. Then, a good understanding of the meaning of computation would suggest that there is nothing in the present state of things hampering an asymptotic faithful representation of their behavior. However, the possibility of a faithful mapping of a complex system into another system of the same complexity is completely useless for the advancement of our knowledge. In this sense, present or future limits of computation do not look like a fundamental obstacle. The real limit is in our capacity of making sense of the results. It is a fact that Statistical Physics has been developed mainly for that purpose. If in the future, this branch of Physics or some evolution of it could help, it can only be matter of opinion.

• Your last sentence seems to contradict the rest of the answer. Worded differently, the question is: can we model systems of any complexity by direct computation, without introducing intermediate/emergent concepts. – Roger Vadim Apr 8 at 9:34
• @Vadim It is not a contradiction, but I agree that it is not clear. I'll clarify this point. As far as your last re-wording, It should be clear from my answer that I think that asymptotically it could be possible, but completely useless. Maybe I'll make more clear this point too. – GiorgioP Apr 8 at 10:26

There are several issues here. First there is a question about whether physics is deterministic enough that it can be computed even in principle. The second is how to motivate statistical mechanics.

The first one is somewhat outside the scope of this SE, although the question does show up here from time to time. One can argue that certain quantum events are logically independent of everything else and hence totally random, but then again a computer with the same kind of random number generator can generate indistinguishable dynamics (if not the same). Others lines of inquiry involve the computability of physics, whether there are limits on acquiring information about the world that prevent accurate simulations, whether chaos and other issues cause too rapid divergence. Lots of topics, but they are irrelevant to the core of the question.

One can motivate statistical mechanics as a way of circumventing our limited knowledge of the micro-states and micro-physics, making the simplifying assumption that "it all averages out". One can also note that the laws that emerge from this averaging appear nearly or completely independent of the microphysics if it has the right form. Indeed, historically people started with macroscale thermodynamics, tried to derive it from the kinetic energy of heat, and ended up with a theory that explains not just the macroscale thermodynamics (and deviations from it) but a lot of other things. In this work computational capacity was never really central, but issues of randomness and probability mattered a lot.

In modern statistical mechanics our computational abilities do not play a major role in the theory itself. It deals with how complicated microphysics statistically produces reliable phenomena; one can sometimes simulate microsystems to see this process happening, but this is no replacement for the overall theory.

However, statistical mechanics has a lot of important things to say about what and how we can compute, for example the famous Landauer's principle for the entropic cost of erasing information. Deep down many of these links emerge from quantum thermodynamics where the random microphysics and the physics of quantum information are combined. For example, the no-hiding theorem both explains conservation of quantum information and the Landauer principle.

So the answer to the second issue is that while simulating some of these phenomena is exciting and may help us understand them better, the theory we actually use to predict observable effects does not care about much of the microphysics. If we had magical computers that could calculate properties of interest from detailed microphysics we would likely use them to get data, but they do not give the qualitative understanding we usually aim for.

• Thank you. That we aim for qualitative understanding is a very good point. Statistical physics here is just an example - what you call the limit on acquiring information is probably more relevant to my question. Errors might average out in stat physics, but if we aim at describing more and more complex systems - biological, social, economic - we need heigher precision. Would it be ultimately possible to define the computability limitation mathematically? – Roger Vadim Apr 2 at 4:58

It depends on what meaning you attribute to the term "fundamental". If the physics you describe is a system of discrete classical particles subject to instantaneous impact and binding forces, the computability might be feasible, say for a several trillion particles. So in this case neither the physics is fundamental, nor the incomputability of the system.

If you consider the physics as described by quantum mechanics, it gets more complicated, because already the single-particle Schrödinger equation is a continuum problem in 3+1 dimensions, i.e. fundamentally, you have an infinite number of degrees of freedom (e.g. the wave function for every point in space), even though it still describes a single particle. In order to solve a continuum problem, you will usually approximate this by a discretization scheme (e.g. finite element, finite difference, unperturbed eigen-functions,...), which makes your calculation approximate. If you want more accuracy (for continuum problems this often means being able to represent smaller wavelengths), you have to increase the number of degrees of freedom taken over to the discretized equations. Unless you happen to have an analytic solution anyway (e.g. the hydrogen atom), more required degrees of freedom means more required computational resources. In fact you have to store all of them and you have to touch all of them during computation.

If you consider a multiple-particle Schrödinger equation, you can easily imagine how complicated it gets in 3N dimensions to solve the corresponding continuum problem. Without statistical quantum mechanics you're totally lost even for the most primitive of problems. And yet, at least computational chemistry has developed several methods to manage (whether they are "ab-initio" or semi-empiric/heuristic/approximate) computations of multi-particle systems, at least on the level of a molecule. If ab-inition QM calculations are already being used for systems of molecules, I don't know, but I seriously doubt that they result in much more or even the same information than statistical/thermodynamical calculations.

If that's not enough practical incomputability, I can even go one better: in quantum field theory, the forces are themselves quantized. That is, what is already classically understood as an infinite number of degrees of freedom (the continuous field), gets another level of infinity, in that every one of the plane waves is not only able to oscillate in one mode, but rather infinitely many modes (which represents the number of photons "in this plane wave"). The possible number of photons is not constant, but can change in interactions with matter, from the ground state up to infinitely many photons. And several of these multiple photon states can even exist at the same time (they are each a quantum mechanical harmonic oscillator).

This should illustrate that the distinction between fundamental/theoretical incomputability and practical incomputability is moot. In the end, it all amounts to "practical incomputability" with respect to the number of degrees of freedom you have to carry with your simulation.

Independent of any consideration of spatial degrees of freedom, there is always the problem of solving the equations of motion with sufficient accuracy in time (aka time discretization). You may get away with explaining that you could always refine your time integration to arbitrary accuracy. However, if non-linearity is present (i.e. almost always, at least in classical physics), then the requirements of computational stability (Ljapunov exponents) is usually not satisfied, which leads to what is colloquially labelled as "chaos", i.e. it is incomputable mathematically-fundamentally.

Having said this, computational methods are often used to verify, confirm or even supply statistical statements, for example for quantum field theory, Lattice Gauge Theory is used. Therefore, not the attribute of "fundamentality" is stretched, but rather only the attribute of "accuracy". Think about it that way: if "Chaos" and it's corresponding apparently random influence is omnipresent anyway, there is no need to calculate everything to 100 digit accuracy if all you are interested in are statistical statements anyway.

• I've removed a comment discussion that had gone off in a weird direction. Be kind, folks. If you're not sure whether a remark is kind or not, keep your trap shut and come back to the discussion later. – rob Apr 2 at 23:32

I don't think that this question can be answered on a "fundamental" level. To judge the computational resources you must have an underlying problem that you are going to compute. But this underlying problem is always limited/based on our current understanding of physics. So, unless we manage to unify all branches of physics into a great grand super equation, we can't know what the resources to solve the problem are going to be. I don't see how you can tackle the computational problem if you haven't solved this problem first. The question is thus not answerable at the moment in my opinion.

And to my knowledge, we don't have equations that allow you to derive all properties of "macroscopic" objects from first principles. Room-temperature superconductors come to mind as a current example, unless i missed new developments.

• +1 I disagree that we need a complete knwoledge of all the physics laws to come up with fundamental principles - after all, we have already come up with many of them. On the other hand, the expample of high-Tc superconductors is an excellent one! – Roger Vadim Apr 8 at 11:47
• I don't think i said something about fundamental principles in general. My point is specific to the question about computation. I think the word "fundamental" is a somewhat unlucky choice as people may have different thoughts what it means. For me, fundamental principles should hold at all times and i don't think that we can make a claim about computation times that will also cover all possible future developments in physics. But i may misunderstand your question, especially the term "fundamental". – Hans Wurst Apr 8 at 12:18
• I agree that "fundamental" was an unfortunate term - what I mean is whether we can define bounds onw hat is posisble to predict without resorting to higher order concepts. Carno cycle efficiency or entropy increase are clear bounds, even though some may disagree to call them "fundamental". – Roger Vadim Apr 8 at 12:26