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.

This entry was posted on Sunday, February 12th, 2012 at 4:54 pm and is filed under Rudy's Blog. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.