Physics problems cannot be undecidable
Luboš Motl, December 10, 2015
If one focuses on physics papers that are hyped in the mass media, one must conclude that science has already entered the postmodern era in which «anything goes». Statements that are arbitrarily close to the most embarrassing mistakes that a weak student may make are often said to be «true» and they are being supported by confused articles and quotes by at most semi-qualified researches.
One of the popular themes of low-quality popular books about physics has been the conflation of physics with Gödel’s incompleteness theorem and similar results. Lots of books liked to argue that the Heisenberg uncertainty relationship and the Gödel’s incompleteness theorem were basically the same thing and both of them were showing some fundamental limits of the scientific understanding of Nature.
However, these two results are not the same – they are not even parts of the same discipline. Gödel’s incompleteness results have pretty much by definition no relevance in natural science while the Heisenberg uncertainty principle tells us that it’s physically meaningless to make certain propositions – like propositions about both position and momentum that are too precise. But when we carefully talk about physically meaningful propositions only (namely about the results of doable experiments), quantum mechanics that results from the uncertainty principle demonstrably leads to a deeper, more complete, and more predictive framework for physics than classical physics used to. The predictions are unavoidably probabilistic but the probabilities are calculable, the possibilities (eigenvalues) are often discrete or mixed and therefore more separated from each other than the unavoidably continuous classical results, and quantum mechanics allows us to produce things like atomic clocks that are far more precise than those that would ever exist in a classical world.
This blog post is primarily about the weird 146-page-long February 2015 mathematically cultured preprint
by Toby Cubitt, David Perez-Garcia, and Michael Wolf (a short version exists) that was just published in Nature which was the event that produced some echoes in Phys.ORG and Nature. They claim that the question whether translationally invariant Hamiltonians have a gap (or whether there exist excited energy eigenstates whose energy is arbitrarily close to the ground state energy) is undecidable in the Gödel-Turing sense. Details will be discussed below.
But I want this text to be much more comprehensive because this is a theme that is periodically returning and some people – perhaps including Lenny Susskind – would like to convince themselves that even the research of quantum gravity is going to be «reduced» to computer-science questions similar to the algorithmic complexity and perhaps even undecidability. I think that this view is silly and we will discuss numerous aspects of these claims.
I think it’s right to say that the whole business of «undecidability in mathematics» is a «professional’s variation on the liar paradox» and it started with 1891 Cantor’s diagonal argument which proves that the real numbers aren’t «countable» which means that there can’t be any one-to-one map between integers and real numbers.
If the real numbers, say between \(0.00\) and \(1.00\), were countable, you could write an infinite table where these real numbers would be written in rows, e.g. in the decimal form. So you would basically have an infinite array of digits which would claim that each real number may be found on one of the rows. However, you may construct a new real number – if you guarantee that its \(n\)-th digit after the decimal point differs from the \(n\)-th digit of the real number on the \(n\)-th row (you may e.g. add one modulo 10 to the digits to change them) – which is easily seen to be absent in the table because such a new number disagrees with each row – it disagrees with the \(n\)-th row (at least) at the \(n\)-th place, by construction.
So when mathematicians talk about the cardinality of sets – the generalized number of elements in a set – they distinguish lots of different «infinities». The number of real numbers is much higher than the number of integers, they think because of this argument, and they think that those things are deep or important in some general sense.
But in physics, this «uncountability of the real numbers» is basically a bogus formal statement that can have no implications. It is «morally untrue» for a simple reason: the new number that Cantor (and we) have constructed cannot ever occur in any physically meaningful (or calculus-related) problem. It was intentionally constructed as a straw man that, by definition, disagrees with every number you could ever care about in any «problem described by a finite sequence of rules». In other words, all the particular and precise numbers we can ever encounter in any calculus-like enterprise are unavoidably countable. They are «constructible». They may be precisely pinpointed by a description that requires a finite number of words – and finite sequences of words (or \(\rm\LaTeX\) symbols etc.) are countable.
Cantor’s argument uses the same trick as the following sentence in recreational mathematics:
This sentence is false.
It leads to a problem known as the liar paradox. If the sentence is true, then what it says must be true. But what it says is that it is false. So if the sentence is true, then it is false. Similarly, if it is false, it must be true. But no logical proposition may be true and false at the same moment – and no proposition is allowed to have no truth value at all – so we face a paradox. The whole world collapses if sentences like that are allowed. 😉
Can the world be saved? You bet. When you define your rules of mathematics in which there are propositions, you must make sure that sentences such as the sentence above are prohibited. How do you ban it without banning vital ordinary propositions in mathematics? You notice that it is referring to itself – and this is the kind of a feature that you must suppress in one way or another.
The same basic problem was revived in 1901 when Bertrand Russell presented his paradox in set theory. In mathematics with sets, as outlined by Cantor (the same one), it is possible to construct sets including all elements satisfying a property (such as the set of primes). It’s also possible to construct the set
\[ R = \{x; x\notin x \} \] of all sets \(x\) that don’t belong to itself. Most ordinary sets are not included in \(R\), of course, because their elements look nothing like themselves. Only some «fractal», self-containing sets could obey the condition. The question is whether \(R\in R\). Is the set \(R\) we have just defined an element of itself? If it is not, then it obeys the condition \(x\notin x\), and therefore we must include it in \(R\), and therefore \(R\in R\). And on the contrary, if \(R\in R\), then the condition \(x\notin x\) is violated, and therefore \(R\notin R\). We have a «liar» contradiction once again. If \(R\) is containing itself, it’s not, and vice versa.
In this case, the paradox implies that a particular ambitious axiomatic system – Cantor’s set theory – is internally inconsistent or self-contradictory. Self-contradictory theories or axiomatic systems (e.g. a simple axiomatic system that postulates that global warming causes more snow in the world and global warming causes less snow in the world) must be abandoned by competent scientists and mathematicians because every conceivable statement may be proved to hold from these axioms and it’s just not interesting if all claims and their negations are equally true. Cantor wanted to claim that all sets defined by similar properties must exist; and all propositions must be either true or false but not both. We (Russell and the TRF readers) have shown that those assumptions can’t be true at the same moment.
Mathematicians have easily found a fix. In fact, Cantor’s theory may be fixed in various ways. The Zermelo-Fraenkel set theory no longer claims that the sets may be constructed by «any condition». They may only be constructed from the bottom, by «exponentiating» or doing similar operations with existing sets, and by taking subsets of those existing sets. Too huge or ill-defined sets are avoided. You’re only allowed to define a «truncated» version of the set \(R\) above which contains \(x\) for which \(x\notin x\) but these \(x\) must also be picked from some pre-existing set whose existence you have previously proved.
The other most prominent framework for set theory is the Gödel-Bernays theory which allows you to clump sets with any property – including the condition \(x\notin x\) – but you are no longer automatically guaranteed that the resulting clumping is a set itself. It may also be just a «class» which is almost like a set except that you’re not allowed to clump it in other classes (classes, including sets, only contain sets, not non-set classes). In the GB system, the proof of Russell’s paradox becomes a proof that the class \(R\) is not a set which is kosher. Because \(R\) is not a set, it isn’t even a candidate for being included in \(R\) – and GB set theory allows you to conclude that \(R\notin R\).
With these fixes, are the ZF and GB set theories internally consistent? People tried to prove it – and similar claims – and Gödel ultimately realized what the answer is: the liar paradox re-emerges once again which makes it impossible to prove the consistency of any axiomatic system within itself. His first 1931 incompleteness theorem says that there exist statements that are neither provable nor disprovable in every axiomatic system that is at least powerful enough to allow us to deal with infinite sets of integers. Like the previous examples of the «liar paradox» (or self-hating Jews), this undecidable proposition negatively refers to itself. Now, it basically says:
GITP: I am not provable within the axiomatic system.
It doesn’t say it literally – it seemingly says some complicated thing about integers etc. but one may show that the claim about the integers is right exactly if the proposition is not provable. How does the liar paradox work now? Well, if the proposition were provable, then it would be true (everything that is provable has to be true). What it says would have to be true but what it says is that it is not provable which contradicts the assumption that it is provable. The proposition cannot be disprovable, either, because in that case, it would be false and what it says would have to be false. It would have to be provable, but it can’t be provable and disprovable simultaneously.
In this case, the third possibility is allowed: the proposition is neither provable nor disprovable.
Again, the claim that is shown to be undecidable is very artificial, different from the problems we would be interested in physics. But I think that one more feature weakens the «true value» of this argument even more strongly, and it’s the following: GITP is formally unprovable but once we realize that, we actually know that GITP is true because «I am unprovable» is exactly what GITP says! The GITP proposition is true, morally provable, and the unprovability of it only holds because of (and as far as there exist) some bureaucratic restrictions on what a proof is allowed to do.
So this whole game is a bureaucratic sleight-of-hand. Gödel was a smart and clever guy and set theorists have produced an impressive religion in which similar results lie at the foundations of philosophy of everything – and they are said to be deeper than physics and everything else, too. (I assure you that I have had some of these religious feelings as well – when folks like Petr Vopěnka talked about the mysterious infinity and infinite sets etc., I was on their frequency for a while, too.) But at least equally convincingly, you may say that all these self-contradictory games are games analogous to 8-year-old kids’ arguments about the liar paradox – games that some adults kept on playing. They’re just a piece of recreational mathematics that tries to look more serious than it is while it is self-evident that this recreational mathematics cannot influence the really important problems such as the problems in physics, especially because the underlying logic and patterns («I am always lying») are too simple for a truly interesting structure to emerge (compare «I am lying» with the structure of the \(E_8\) Lie group – the former is childish – and Gödel and friends were basically formulating the same childish «beef» in some languages of «adults» but the beef of the problem remained «childish»).
In mathematics, one needs to avoid similar paradoxes and one must be extremely careful what kinds of arguments are allowed in a proof (or disproof). But if we’re more tolerant towards the creativity of the proof – the physicists’ tolerance is surely enough – we know what the answer actually is. GITP is true because it is not provable within the system – but once we realized that, we proved the proposition in an innocent extension of the axiomatic system. If a similar situation ever occurred in physics, every physicist would know that GITP is true. The question would be settled and the inability of the original axiomatic system to prove something would be viewed as a vice of this system (analogous to a loophole in a particular bill on taxation), not a virtue and not a key to some deep wisdom about the «truth of things».
Similarly, Gödel has shown (using a similar self-referring reasoning) that if axiomatic systems are consistent, they can’t be powerful enough to prove their consistency. It is ironically a good thing that they can’t prove their health. Why? Because in internally contradictory systems, you may prove any statement, whether it’s true or false, as well as its negation. So the inability to prove «big» things such as one’s own consistency is actually a sign that the system is consistent. (Needless to say, the proof of the unprovability of the consistency could be proved by an inconsistent system as well LOL – because everything may be proven using such systems – but I don’t want to continue with this playful discussion indefinitely.)
Finally, Cantor’s diagonal trick was recycled in 1936 by Alan Turing who proved that there can’t be a general algorithm answering the halting problem. This mythical algorithm would take a piece of code as the input; and it would always decide whether this code will ever end once you run it. Again, Turing proves this «problem» by constructing an unnatural, self-referring counterexample, a code that basically says «keep on going if it may be proven that I stop», or something like that. So if the code may be proven to terminate, it keeps on running, and if it may be proven to run indefinitely, it will stop. Both are contradictions so the universal deciding algorithm won’t be able to authoritatively claim either answer.
And this Turing’s variation of the liar paradox is the essence of the work of Cubitt et al. that pretends to be about physics.
If I understood the paper well, they basically construct Hamiltonians for «grids» that contain a gap (a property of the spectrum) if and only if some corresponding algorithm stops. The «increasing time» needed to run the algorithm is basically identified with the number of lattice sites that we want to be sent to infinity. The Hamiltonian is constructed as one associated with some tilings and some overall phase of the material matters.
Their counterexamples – the self-referring liars – look like some Hamiltonians for lattices with some nearest neighbor plus similar interactions. But the precise numerical structure is chosen in such a way that the problem resembles a self-referring liar, more precisely Turing’s counterexample code for the halting problem.
They – and the popular writers hyping the article – love big words so they suggest it makes all condensed matter physics undecidable. And maybe, they could also deserve the $1 million Clay Institute prize for the millennium problem to «prove the gap of Yang-Mills theory». Instead of proving or disproving the Yang-Mills gap, they may have proved that no proof exists in either way – which would also be a full solution if the claim were true. Needless to say, all these claims are complete rubbish. They haven’t proven anything of the sort. They have just constructed a reincarnation of a self-referring liar – in this case, a Hamiltonian – in an unusual context. (The Yang-Mills gap almost certainly exists, the answer «No» or «Mixed» is almost certainly wrong, and I think that this Clay Institute problem is more about the formal rules of a proof than about the actual physics essence – because of all the physics-wise satisfactory existence that has been found, including some AdS/CFT arguments, no good physicist seriously doubts that the gap exists.)
On page 8 of their long paper, they write pretty clearly what their «great» result actually is:
This has two subtly distinct meanings. First, the spectral gap problem is undecidable in precisely the same sense as the Halting Problem is undecidable: there cannot exist an algorithm, no matter how inefficient, to determine if a general Hamiltonian is gapped or gapless.
What they have actually proven is that there cannot exist a single universal general algorithm that would be able to deduce the qualitative properties for any lattice-style Hamiltonian that you insert. They may prove such a result because one may construct Hamiltonians that are like self-referring liars.
But to suggest that this result is important for physics means to entirely misunderstand the goal of physics, the method of physicists’ work, and the relationships between theories and solutions in physics. Why?
Because physicists are in no way trying to find a universal algorithm that «solves everything». This has two major reasons:
- Physicists are only trying to solve problems that may occur naturally, and those are analogous to constructible (and therefore countable) real numbers and not the self-referring liar things
- Physicists understand way too well that to solve different problems, even seemingly similar Hamiltonians with qualitatively different values of parameters, they need to apply very different methods!
The result of Cubitt et al. would be worthless for physics even if only one of the problems above existed. But both of them make the result super-dead in the context of physics.
A few more words about these two problems.
The first problem basically says that their «halting problem» environment works with an infinite collection of Hamiltonians that may be increasingly complex. And it’s this setup with «arbitrarily complicated examples» clumped along with «the simpler ones» that makes the universal algorithm impossible.
But a well-defined problem in physics always works within the limits of a finite complexity. The laws of physics are only given by particular Hamiltonians which are analogous to the «simple real numbers» in all the efforts to count the reals. In recent weeks, I played with the Riemann Hypothesis a lot again. One of the features that has fascinated me much more than before was the «universality».
If you take any everywhere nonzero holomorphic function \(f(s)\) in a compact set \(M\) in the critical strip
\[ 0\lt {\rm Re}(s) \lt 1 \] you will be able to shift \(s\) by a sufficiently large imaginary number \(i\cdot\Delta t_{\epsilon,f}\) so that the Riemann \(\zeta\)-function in the shifted set \(M_{+\Delta t}\) will coincide, up to errors never exceeding \(\epsilon\) which you predecided and can be arbitrarily small, with the function \(f(s)\) in the set \(M\).
All non-vanishing holomorphic functions are somewhere in the critical strip! This may ultimately be proven assuming that the nontrivial zeroes of the \(\zeta\)-function are distributed according to the patterns of random matrix theory – even though a full proof of the universality would probably need (or imply) the Riemann Hypothesis. If you want to find places where the \(\zeta\)-function’s absolute value is small, you need a location where the («random») density of the nontrivial zeroes is higher; if you need the absolute value of the holomorphic function to be large, you need to visit the places with a lower density of the zeroes (the distribution of the nontrivial zeroes is «in some sense» dual to the distribution of primes, I think), and the precise patterns of distances between the nearby relevant zeroes (which may look like any pattern, for a suitable large enough \(\Delta t\)) are able to encode as many «detailed patterns» (e.g. Taylor series coefficients of \(f(s)\)) of the desired holomorphic function as you wish.
But a wisdom to notice here is that the holomorphic functions are basically «rated» by the shift \(\Delta t\), the imaginary part of \(s\). The \(\zeta\)-function is «simpler» near the real axis and becomes «more contrived» (perhaps increasingly analogous to the «Boltzmann Brains», you could say, but don’t forget that the analogies between mathematics and physics carry some unavoidable risks) very far from the real axis, for \(\Delta t\to \infty\), and that’s the limiting region where the «self-referring liars» may be hiding.
Every Hamiltonian that you encounter in the real world corresponds to some finite or bounded complexity, a reasonably small value of \(\Delta t\) in the Riemann zeta analogy, if you wish. In some broad moral sense, string theory has a «unique Hamiltonian». But in different compactifications, it may manifest itself as different «effective Hamiltonians». However, even these compactifications – or effective Hamiltonians – are bounded. The number of stabilized semirealistic compactifications is finite, perhaps \(10^{272,000}\), but it is finite, anyway. So there’s no way for «self-referring liars» to emerge here, simply because physics is ultimately solving a finite number of finitely complex problems instead of efforts to classify infinitely many problems at the same moment.
The second problem of Cubitt-et-al.’s philosophy is that they assume that physics is about finding «universal algorithms to solve everything». However, physics is an accumulation of lots of great, inequivalent ideas and physicists aren’t ashamed of thinking differently about different problems. This ability is really what their expertise is all about! The laws of physics may be unified in terms of similar Hamiltonians – and string theory represents the most perfect unification of this kind that we know (and apparently the final one) – but these Hamiltonians etc. are still able to manifest themselves in very many ways, to have many different solutions and kinds of behavior.
Condensed matter physics is absolutely full of these things. The same Hamiltonians lead to phase diagrams as functions of parameters. Different phases are studied by totally different tools. But I want to mention «fundamental particle physics». We have things like Yang-Mills (gauge) theory, a very important example. Gauge theories look similar to each other but they may behave in many different ways.
If the number of matter fields etc. is small enough, the theory preserves its asymptotic freedom (and basically the confinement, too, although it’s not quite an equivalent characteristic): the charged particles are almost free at short distances but the charges (colored quarks etc.) can’t be isolated. If the number of matter fields is higher, the behavior is reverted and the theory has to be replaced by something more consistent at short distances while the confinement may disappear at long distances. When the matter fields include Higgses with the potentials like \(A\phi^4+B\phi^2\), the behavior changes when \(B\) changes the sign. A negative \(B\) will lead to a spontaneously broken symmetry which is analyzed by different tools than the unbroken symmetry.
The fundamental laws of physics may be unified but the methods to solve them in various situations cannot!
The ability of the same or similar laws of physics to have many qualitatively different implications is nothing else than «the power of unification» described in different words.
I think that this observation may be the single most important point about physics that is generally misunderstood by the people who are trained computer scientists and who want to think about Nature from the viewpoint of computer scientists. Search for Aaronson on this blog – I’ve made the same point or very similar points in the past.
In some sense, the computer scientists – much like lots of the laymen – completely miss one (and arguably the key) portion of the work of the physicists, namely the search for the right laws. They only see the «solving of the problems». But a priori, the right (mathematical) problems that physicists should solve are completely unknown – in other words, physicists aren’t born (and the mankind wasn’t born) with the knowledge of the accurate enough laws of physics.
These laws had to be found (by creative enough theorists and by experimenters who have helped to show them which right was right) and whenever they’re found, they’re concise and described by a finite collection of rules about the external objects – rules that look nothing like the artificially engineered self-referring liars. But once physicists find viable laws – and accumulate the evidence that they’re the right laws while other candidates are wrong – physics isn’t solved yet. It may be very hard to solve some equations in a particular context. And it always seems possible to construct «increasingly difficult physical systems» on which some laws may be applied. But once you are going in this direction, you start to do applied physics, not fundamental physics (a pure science).
Feynman’s and Kitaev’s texts motivating quantum computation are cited by Cubitt et al. as examples of work that shows that some problems in physics may be computationally hard – those are the observations you need to demonstrate if you want to claim that a quantum computer would be helpful for something (it’s helpful because the problem is hard for classical computers). But Kitaev let alone Feynman wouldn’t agree that important problems that exist in physics could be undecidable. If a proposition were really undecidable, then it would be physically meaningless because all physically meaningful propositions are decidable at least in one sense – they may be decided by an experiment that must be in principle doable. This is particularly the case of the question whether a Hamiltonian is gapped because the experiments looking for the gap are straightforward.
Let me repeat this point about the difference between physicists’ and mathematicians’ motives and attitudes in slightly different words. For physicists, the search for the right laws that govern some physical systems is really the primary goal of their discipline. They only solve difficult enough problems if these difficult enough problems are needed to decide whether some candidate laws agree with the observations of a physical system. When the answer is No, the candidate theory has to be modified or eliminated; when the answer is Yes, physicists’ respect towards and excitement about the theory is increasing.
But once they know that some laws hold in a given situation, the problem is solved in principle. It’s obvious that in the given context, one may prepare increasingly difficult and complex systems that may be solved – the Ruby Goldberg machines are just among the simplest examples of problems in mechanics that start to be difficult. But to solve difficult composite or «engineered» problems isn’t really a fundamental job for a physicist or according to a physicist.
Mathematicians solve problems regardless of the origin of these problems. There is really no objectively well-defined regulating mechanism that would say that this problem is far more profound than another problem. All these comparisons may only be done subjectively by the mathematicians. Physics is different because the final criterion of importance is the existence of a certain behavior in Nature around us – and the proximity between a problem in physics and our ignorance about some core issues defining the basic laws of physics which affect our understanding of other phenomena.
This undecidability-in-physics issue has some links to the «discrete physics» religious experience. Stephen Wolfram and others are excited that some simple cellular automata are able to produce aperiodic, easily unpredictable, yet not quite «random» (in the sense of «white noise») patterns. But this feature isn’t surprising for a physicist. Almost all equations for large enough systems you can write down are analytically unsolvable. A three-body problem in Newton’s theory of gravity is enough to generate chaotic behavior. And so on. Such a situation isn’t a rare gem. Instead, it’s the norm. Most laws of physics lead to a messy behavior that can’t be solved easily or completely. On the contrary, it’s the integrable systems that are special and that physicists should better learn because they’re islands from which you may swim to other places of the ocean of ignorance as well – without getting drowned too quickly.
But the analytically unsolvable problems may still be solved numerically (or by «related approaches») in principle. A finite accuracy is always enough to settle a question in principle. If the calculation according to a theory were impossible even in principle, we would have to conclude that the theory is ill-defined! And the materials that condensed matter physicists study are finite in size. The «infinite lattice» is always just an approximation and because macroscopic pieces of a material are much larger than the atomic scale, the properly defined «infinite lattice» is always a good and useful limit to study «finite pieces of materials» in condensed matter physics. If some «totally new» problems arose in the «infinitely large material» limit, these problems would obviously have nothing to do with physics because solids can’t be infinitely large.
In fact, just the opposite thing is true. People in physics study the «infinite lattice» limit because many of the calculations – using physicists’ clever methods – simplify in this limit. One may design special Hamiltonians where the limiting procedure makes things harder but they’re either strictly unphysical or it is at least infinitely unlikely for these subtleties to matter in physics.
So I find it plausible that physicists will need to know more complexity theory than before to assess certain claims about the holographic code or the black hole interior or the Hawking evaporation and other things in quantum gravity – and complexity theorists and similar folks may contribute some helpful insights. But I don’t think it’s conceivable that the «liar paradox» will become an important consideration in physics, ever. The people who try to spread such memes in physics are trying to blindly impose the rules of one scientific discipline on another discipline. Or they are trying to be «interdisciplinary» at any cost. I don’t find this tendency to be a feasible path towards the scientific progress, at least not in most cases, because such an approach basically represents the denial of any relevance of all key insights of the «target» discipline (in this case physics).
Dualities have blurred the some of the difference between «simple» and «complex» laws of physics or «simple» and «complex» computations needed to answer a question. But they haven’t blurred the difference between «learning the laws of physics» and «applying the laws of physics». The first process, the «learning of the laws of physics», must always come first, and that’s why the arguments by Cubitt et al. won’t become relevant in physics. Physics is only solving problems defined by those laws of physics that seem viable as a description of phenomena in Nature; Cubitt et al. are trying to «impose» some laws on Nature that are chosen according to very different than empirical criteria, according to some «special mathematical properties», namely either by their ability to admit a «universal algorithm to solve all problems» or their ability to «escape universal algorithms».
But none of these properties are relevant for finding the right laws of physics. The right laws of physics seem to be simple enough – we can only write down a finite number of symbols – and they require different ideas to be solved in different contexts and for different values of parameters. Because the physical theories must ultimately refer to objects in the external world, they are not reincarnations of Cantor-Russell-Gödel-Turing self-referring liars.
