Click covers for info. Copyright (C) Rudy Rucker 2021.

An Incompleteness Theorem for the Natural World

I spent the last few of days working on a philosophical essay for a collection of articles about Stephen Wolfram’s 2002 book, A New Kind of Science. I’m a friend of Wolfram’s and a big fan of his work. For much more about Wolfram’s book and its reception, you can see my long 2003 review of it for the monthly magazine of the Mathematical Association of America.

But today I don’t want to get into all that, I want to talk about my new essay, which is called “An Incompleteness Theorem for the Natural World.” (In 2020 I posted the full essay online as a PDF.)  I’m very happy with the argument I presented there. The argument isn’t really all that complicated—but I’ve been looking for it for about thirty years! I won’t print the whole essay here, but I will print the introductory section to give you an idea of what I’m getting at. A lot of it is based on material in my book, The Lifebox, the Seashell, and the Soul, but just this week I saw how to present it in a much clearer light.

So here we go, the intro to my essay, “An Incompleteness Theorem for the Natural World.”

The philosopher Gottfried Wilhelm von Leibniz is perhaps best known for the fierce controversy that arose between him and Sir Isaac Newton over the invention of calculus. The S-like integral sign that we use to this day is in fact a notation invented by Leibniz.

When Leibniz was a youth of nineteen, he wrote a paper called “De Arte Combinatorica”, in which he tried to formulate a universal algebra for reasoning, in the hope that human thought might some day be reducible to mathematical calculations, with symbols or characters standing for thoughts.

But to return to the expression of thoughts by means of characters, I thus think that controversies can never be resolved, nor sectarian disputes be silenced, unless we renounce complicated chains of reasoning in favor of simple calculations, and vague terms of uncertain meaning in favor of determinate characters.

In other words, it must be brought about that every fallacy becomes nothing other than a calculating error, and every sophism expressed in this new type of notation becomes in fact nothing other than a grammatical or linguistic error, easily proved to be such by the very laws of this philosophical grammar.

Once this has been achieved, when controversies arise, there will be no more need for a disputation between two philosophers than there would be between two accountants. It would be enough for them to pick up their pens and sit at their abacuses, and say to each other (perhaps having summoned a mutual friend): “Let us calculate.”

Let’s refer to this notion as Leibniz’s dream — the dream of finding a logical system to decide all of the things that people might ever disagree about. Could the dream ever work?

Even if the dream were theoretically possible (which it isn’t), as a practical matter it wouldn’t work anyway. If a universal algebra for reasoning had come into existence, would, for instance, Leibniz have been able to avoid his big arguments with Newton? Not likely. People don’t actually care all that much about logic, not even Leibniz. We just pretend to like logic when it happens to be on our side — otherwise we very often abandon logic and turn to emotional appeals.

This said, there’s a powerful attraction to Leibniz’s dream. People like the idea of finding an ultimate set of rules to decide everything. Physicists, for instance, dream of a Theory of Everything. At a less exalted level, newspapers and TV are filled with miracle diets — simple rules for regulating your weight as easily as turning a knob on a radio. On the ethical front, each religion has its own compact set of central teachings. And books meant to help their readers lead happier lives offer a simple list of rules to follow.

But, as I hinted above, achieving Leibniz’s dream is logically impossible.

In order to truly refute Leibniz’s dream, we need to find a precise way to formulate it. As it happens, formal versions of Leibniz’s dream were first developed early in the Twentieth century.

An early milestone occurred in 1910, when the philosophers Bertrand Russell and Alfred North Whitehead published their monumental Principia Mathematica, intended to provide a formal logical system that could account for all of mathematics. And, as we’ll be discussing below, hand in hand with the notion of a formal system came an exact description of what is meant by a logical proof.

There were some problems with the Russell-Whitehead system, but by 1920, the mathematician David Hilbert was confident enough to propose what came to be known as Hilbert’s program.

(1) We will discover a complete formal system, capable of deciding all the questions of mathematics.

(2) We will prove that this system is free of any possible contradiction.

As Hilbert put it, “The conviction of the solvability of every mathematical problem is a powerful incentive to the worker. We hear within us the perpetual call: There is the problem. Seek its solution. You can find it by pure reason, for in mathematics there is no ignorabimus.”

For a decade, scientists could dream that Hilbert’s program might come true. And meanwhile mathematics and much of physics were being recast as formal systems. Scientific theories could now be viewed as deterministic processes for determining the truth of theorems. Leibniz’s dream was nearly at hand!

But, then, in 1931, the logician Kurt Gödel proved his celebrated Incompleteness Theorem.

Gödel’s Incompleteness Theorem. If F is a consistent formal system as powerful as arithmetic, then there are infinitely many sentences which are undecidable for F.

This means there can never be formal system of mathematics of the kind sought by Hilbert’s program. Every formal system F about mathematics is incomplete in the sense that there are sentences G such that F fails to prove G or ~G, where ~G is the negation of G.

Gödel’s sentences G take the form of statements that certain algebraic formulas have no solutions in the natural numbers. Normally these sentences include at least one very large numerical parameter that in some sense codes up the entire theory F. Wolfram has suggested that there might be some much simpler undecidable Gödelian sentences that involve very simple algebraic formulae.

Philosophers of science have wondered if there is something like an Incompleteness Theorem for theories about the natural world. One somewhat awkward approach might be to argue that if the natural world happens to be infinite, then we can in some sense represent the system of natural numbers as a list of objects within the world and then go on to claim that the usual undecidable Gödel statements about arithmetic are also statements about the natural world.

But, as I discuss in my 1982 book, Infinity and the Mind, this isn’t a satisfying approach. If we wanted to have number theory be a subset of a theory W about the physical world, we’d need for W to single out an infinite set of objects to play the role of the numbers, and W would also need to define relations the correspond to numerical addition and multiplication.

What we really want is a proof—or at least a plausibility argument—for a Natural Incompleteness Theorem that asserts the existence of undecidable sentences that are about natural physical processes—as opposed to being about the natural numbers in disguise.

Wolfram’s analysis of computation in his A New Kind of Science opens a path. The first step is to accept the idea that natural processes can be thought of as computations. And the second step is to argue for some form of Wolfram’s Principle of Computational Equivalence.

Wolfram’s Principle of Computational Equivalence (PCE): Almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication.

In my essay I show that, starting from Wolfram’s two steps, we can prove a Natural Incompleteness Theorem. My method will be to make use of Alan Turing’s 1936 work on what he called unsolvable halting problems. And rather than using the full strength of Wolfram’s somewhat controversial Principle of Computational Equivalence, I’ll base my argument on a weaker assumption, which I call the Halting Problem Hypothesis. And we end up with the following Natural Incompleteness Theorem.

Natural Incompleteness Theorem. For most naturally occurring complex processes and for any correct formal system for science, there will be sentences about the process which are undecidable by the given formal system.

This is, I believe, a clean statement of new result—and may be of real importance to the philosophy of science. Although Wolfram has pointed out some specific examples of undecidable statements about natural processes, he didn’t mange to state the general Natural Incompleteness Theorem.

But now we have a Natural Incompleteness Theorem telling us that every possible complex natural process is going to have undecidable sentences associated with it! Undecidability is everywhere, and all of our theories about nature must remain incomplete.

I’m very stoked.

12 Responses to “An Incompleteness Theorem for the Natural World”

1. Steve H Says:

“Now my own suspicion is that the Universe is not only queerer than we suppose, but queerer than we can suppose.” – JBS Haldane
Sounds logical to me; Nature is a huge chaotic system and impossible to predict.

Wonderful, Rudy! A clean new result indeed!

Pushing Goedel’s 1st into (most) natural chaos is fine; but do consider Goedel’s 2nd and Loeb’s Theorem. Goedel 1 is about ‘this sentence is unprovable’; unprovable if true, hence proof is incomplete. Goedel 2 is about ‘this sentence is irrefutable’; itself refuted! Hence all formal existence is necessarily contingent. Does natural chaos punish hubris? Loeb’s theorem is about ‘this sentence is provable’; itself provable, though empty. Does natural chaos support self-validation?

4. Roy Says:

I can’t wait to read this full paper on incompleteness for the natural world.

In the meantime, it might be of interest to mention Gödel’s own generalization of his theorem to human affairs, mentioned in a letter dated 15 March 1961: “A completely unfree society (i.e., one proceeding in everything by strict rules of ‘conformity’) will, in its behavior, be either inconsistent or incomplete, i.e., unable to solve certain problems, perhaps of vital importance. Both of course, may jeopardize its survival in a difficult situation. A similar remark would also apply to individual human beings.”

(Cited in Hao Wang, A Logical Journey, page 4.)

Roy; thanks for the Gödel quote. So perhaps a true psychohistory is necessarily Gödelian!
And ditto for a true unified field theory. In both, proof is incomplete or inconsistent, and existence is at best conditional.
But also Löbian: self-validation self-validates.

6. Mike Marinos Says:

Nassim Talebs’ work on antifragility in systems seems to suggest a corollary of your incompleteness: Any system that you can describe wont be complex enough to support your survival.
http://www.blackswanreport.com/blog/tag/anti-fragility/

7. John Starrett Says:

“The argument is really all that complicated” maybe, but it would be better if it was not all that complicated.

8. Rudy Says:

John Starrett, that was typo on my part, sorry. I meant to say, “The argument isn’t really all that complicated.” [I corrected this in the post now.]

But, to be honest, that’s kind of a subjective judgment in any case—what’s complicated and what isn’t. At this point the argument doesn’t seem all that complicated to me but, again, this is stuff I’ve thought about for thirty years, so it might not seem very clear to someone hearing about it for the first time.

If, however, the argument were to be completely transparent and practically trivial, then it wouldn’t be something that I’d be as excited about.

In math, philosophy, and logic, you like to find an argument that seems to prove something interesting in a comprehensible way, but you want the proof to be a little bit subtle so there’s a sense of surprise when you reach the conclusion. Like a good magic trick.

9. Eric James Parfitt udqbpn Says:

exist rules or not exist rules. not exist rules leads to contradiction therefor exist rules therefore matbe exists the set of all programs. therefor maybe exists our universe. Q.E.D.

==(rule === if(chi(sub(0.,chi(sub(1.
~Chase of Mendota

where chi(sub(0 stands for one thing and chi(sub(1 stands for anther thing and ~===citation.

did our fighting in WWII Maximize fun while minimizing death? fun is hard to define but i think it is definable. you could start with wolfram alpha or a dictioinary. One may start with thinking about the history of China, or the ultimate reason for fighter jet’s existence, whcih should in principle be reducable to logic symbols. I rest my case.

10. Eric James Parfitt Says:

What do you know of M-theory?

11. John Says:

Hi Rudy, where can I find your “incompleteness theorem for the natural world” article? I wonder if you could prove the theorem rigorously. I really want to see it. Please let me know.
By the way, this effort is not new, please see Barry Cooper’s article called “Beyond Godel’s theorem. Thank you. John.

12. Rudy Says:

John, I have a sample PDF version of the full text of my book, THE LIFEBOX, THE SEASHELL, AND THE SOUL online at the book’s page. If you open this PDF and go to p. 479, you can find my “Technical Appendix,” which outlines in some detail the steps to my result. Alternately you might seek out this book in a library.

I had known S. Barry Cooper for his ongoing tracking of the Turing Centennial year, but hadn’t been aware of his papers on the philosophy of mathematics, so thanks for pointing these out. Can you post a link to the specific paper you were referring to?