by Rucker, Rudy
(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 (2002, p. 790) has suggested that there might be some much simpler undecidable Gödelian sentences, and proposes that the following sentence might be undecidable: “For all m and n, m2 ¹ n5 + 6n + 3.”
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 (Rucker, 1982, p. 290), 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 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 this essay I’ll 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’ll 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 (2002, p. 1138) gives some specific examples of undecidable statements about natural processes, he fails to state the general Natural Incompleteness Theorem.
The Halting Problem Hypothesis
It’s traditional to ask if a computation comes to an end, or if it halts. We can extend our language a bit and speak of a natural process as halting it happens to reach or to pass through some particular designated state. The established results about the narrow sense of halting apply to this generalized sense as well.
In many situations we value processes that halt in our more general sense. Suppose you feed a set of equations into some computer algebra software, and that you ask the software to solve the equations. What you want is for the resulting process to halt in the sense of displaying an answer on the screen. It doesn’t halt in the more dramatic and narrow sense of going dead or freezing up the machine.
In many situations, we like to have computations or processes that don’t halt. When we simulate, say, the life of some artificially alive creature, or the evolution of a species, we aren’t aiming towards a specific kind of result, and still less do we want to see a fixed state or periodic behavior. In this situation we prefer a non-halting computation that continues to produce novel effects.
The distinction between halting and not halting leads to Turing’s Theorem of 1936.
Definition. The computation P is said to have a solvable halting problem if and only if there is an algorithm for deciding in advance which inputs will cause P eventually to reach a halted target state, and which inputs will cause P to run endlessly without ever reaching a halted target state.
Definition. A computation is universal if it can emulate any other computation.
Emulating a particular computation C means that you can feed a certain code into your universal computation U that will cause U to produce the same input-output behavior as C.
As it happens, universal computations are in fact very common. Any personal computer, for instance, embodies a universal computation. Indeed, even as simple a computation as the one-dimensional cellular automaton with rule-code 110 is universal (Wolfram, 2002).
Putting all our new concepts together, we arrive at the following.
Turing’s Theorem. If U is a universal computation, and then U has an unsolvable halting problem.
This means that if a computation is of a sufficiently rich and general nature, then there is no simple algorithm for predicting which inputs will make U run forever, and which inputs will make U end up in some desired target state, such as the state of coming to a halt.
Let’s switch focus now, and discuss how the notion of halting problems can be used to formulate a weaker form of Wolfram’s Principle of Computational Equivalence. For convenience, here is a statement of the PCE again.
Wolfram’s Principle of Computational Equivalence (PCE): Almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication.
I’ll now ring the PCE through three changes, hit a snag, formulate an alternate form of the PCE, and then suggest a still-weaker hypothesis that I’ll call the Halting Problem Hypothesis (HPH).
Suppose that we speak of computations rather than processes, and that we speak of computations that are “complex” rather than “not obviously simple.” In this case the PCE becomes:
(1) Almost all complex computations are of equivalent sophistication.
What might Wolfram mean by saying that two computations are “of equivalent sophistication”? Suppose we take this to mean that the computations can emulate each other or that, more technically, they have the same degree of unsolvability. So now the PCE becomes:
(2) Almost all complex computations can emulate each other.
Now certainly Turing’s universal computation is complex. So, given that a computation which emulates a universal computation is itself universal, the PCE becomes:
(3) Almost all complex computations are universal.
But mathematical logicians have proved:
(Snag) There are very many complex computations which are
not universal.
The “almost all” in the PCE gives us some wiggle room. But at this point we’d do well to back off. Suppose we weaken the range of application of the PCE. Rather than saying it applies to “almost all” complex computations, suppose we say it applies to “Most naturally occurring” complex computations. And this gives us a weakened formulation of the PCE.
(4) Most naturally occurring complex computations are universal.
This statement may still be too strong. Rather than insisting upon it, let’s consider what we plan to use the PCE for. As I mentioned in the introductory section, I plan to use something like the PCE as a stepping stone to a Natural Incompleteness Theorem. And for this, all I need is the following Halting Problem Hypothesis (HPH).
(HPH) Halting Problem Hypothesis: Most naturally occurring complex computations have unsolvable halting problems relative to some simple notion of halting.
Think of a computation as an ongoing process, for example your life, or society, or a plant growing, or the weather. As I mentioned in the previous section, relative to a given computation we can formulate the notion of a target state as being some special status or behavior that the computation might eventually reach. The halting problem in this context is the problem of deciding whether a given input will eventually send your computation into one of the target states. And, once again, a halting problem is unsolvable if there’s no computation, algorithm, or rule-of-thumb to detect which inputs won’t ever produce one of these specified target state.
The HPH says that if you have some naturally occurring computation that isn’t obviously simple, then there will probably be some simple notion of a target state that leads to an unsolvable halting problem.
Note that the PCE implies the HPH. Going in the other direction, the HPH does not imply the PCE. The HPH claims only that certain computations have unsolvable halting problems, and does not claim that these computations are universal. The good thing about the HPH is that, unlike the PCE, the HPH has no difficulties with the many non-universal computations that have unsolvable halting problems. The HPH has a better chance of being true, and is easier to defend against those who doubt the validity of Wolfram’s analysis of computation.
It’s worth noting that it may be possible to drop the two-fold qualifier “mast naturally occurring” from the HPH and to get a Strong Halting Problem Hypothesis as stated below.
Strong Halting Problem Hypothesis: All complex computations have unsolvable halting problems relative to some notion of halting.
This says that all complex computations have associated with them some unsolvable halting problem. If this is indeed the case, then the Strong Halting Problem Hypothesis clarifies what we mean by a “complex computation.”
Getting back to the weaker HPH, let me clarify its import by giving some fanciful examples. The table below lists a variety of real world computations. In each row, I suggest a computation, a notion of “target state”, and a relevant question that has the form of a halting problem—where we try to detect initial states that produce endlessly running computations that never reach the specified target state. (I’m idealizing here, and temporarily setting aside the issue that none of the physical processes that I mention can in fact run for infinitely many years.)
Assuming that the HPH applies to these computations with these particular definitions of target state, we’re faced with unsolvability, which means that none of the questions in the third column can be third column can be answered by a finding a simple way to detect which inputs will set off a process that never reaches the target states.
Computation
Target States
Unsolvable Halting Problem
The motions of the bodies in our solar system.
Something rams into Earth.
Which possible adjustments to Earth’s orbit can make us safe forever?
The evolution of our species as we spread from world to world.
Extinction.
Which possible tweaks to our genetics might allow our race survive indefinitely?
The growth and aging of your body.
Developing cancer.
Which people will never get cancer?
Economics and finance.
Becoming wealthy.
Which people will never get rich?
Crime and punishment.
Going to jail.
Which kinds of careers allow a person to avoid incarceration forever?
Writing a book.
It’s obviously finished.
Which projects are doomed from the outset never to be finished?
Working to improve one’s mental outlook.
Serenity, tranquility, peace.
When is a person definitely on the wrong path?
Finding a mate.
Knowing that this is the one.
Who is doomed never to find true love?
Inventing something.
Eureka!
Which research programs are utterly hopeless?
Unsolvable Halting Problems In Everyday Life.
A Natural Incompleteness Theorem
Let’s begin by defining what I mean by a formal system. A formal system F can be characterized as having four components: A set of symbols, a rule for recognizing which finite strings of symbols are grammatical sentences, a rule for deciding which sentences are to be regarded as the axioms of the system, and some inference rules for deducing sentences from other sentences.
A proof of a sentence S from the formal system F is a sequence of sentences, with the last sentence of the sequence being the targeted sentence S. Each preceding sentence must either be an axiom or be a sentence which is arrived at by combining still earlier sentences according to the inference rules. If a sentence is provable from F, we call it a theorem of F.
Combined with the notion of proof, a formal system becomes the source of a potentially endless number of theorems. Aided by a formal system, we mentally reach out into the unknown and produce facts about entirely new situations.
Now let’s think of a formal system as a computation. There are several ways one might do this, but what’s going to be most useful here is to work with a computation FProvable that captures the key aspect of a formal system: it finds theorems. Our FProvable will try to detect—so far as possible—which strings of symbols are theorems of F. That is, for any proposed provable sentence S, the computation FProvable(S) will carry out the following computation.
(1) If S fails to be a grammatical sentence FProvable(S) returns False.
(2) Otherwise FProvable starts mechanically generating proofs from the formal system F in order of proof size, and if S appears at the end of a proof, FProvable(S) returns True.
(3) If S is a grammatical sentence but no proof of S is ever found, then FProvable(S) fails to halt.
As it turns out, if F is a powerful enough formal system to prove the basic facts of arithmetic, then FProvable will be universal. And then, by Turing’s Theorem, FProvable has an unsolvable halting problem.
(That is, Turing’s work showed that arithmetic is strong enough to emulate the running of Turing machines. More specifically, he showed that for any F as strong as arithmetic, we can set things up so that FProvable emulates M. Since we can do this for any machine M, this means that FProvable is a universal computation, so Turing’s Theorem applies, and FProvable has an unsolvable halting problem.)
Let’s come back to Leibniz’s dream. Suppose we could formulate some wonderfully rich and inclusive formal system F that includes mathematics, physics, biology, human psychology, and even the laws of human society. And then, just as Leibniz said, whenever we’re asked if some statement S about the world were true, we’d set the computation FProvable(S) in motion, and the computation would eventually return True—provided that S is provable as well as true.
One cloud on the horizon is that, if S isn’t provable, then FProvable(S) is going to run forever. And, due to the unsolvability of the halting problem, there’s no way to filter out in advan
ce those sentences S that are in fact unprovable sentences.
To delve deeper, we need two more definitions. As a I mentioned before, we’ll use ~ to represent negation. So if S is a sentence, ~S means “not S”. That is, S is false if and only if ~S is true. Using this notion of negation, we can formulate the notion of consistency.
Definition. F is consistent if and only if there is no sentence S such that F proves S and F proves ~S.
According to the usual rules of logic, if a theory proves even one contradiction, then it will go ahead and prove everything possible. So an inconsistent theory is useless for distinguishing between true and false statements about the world. We can reasonably suppose that our proposed Leibniz’s-dream-type theory F is consistent.
What if neither S nor ~S are provable from F? As it turns out, the neither-nor case does happen. A lot! The reason has to do with, once again, the unsovability of the halting problem for FProvable.
Definition. If F is a formal system and S is a particular statement such that F proves neither S nor ~S, we say S is undecidable for F.
A priori, we can see that there are four possible situations regarding the behavior of the “Is S provable?” computation.
FProvable(~S) returns True
FProvable(~S) doesn’t halt.
FProvable(S) returns True.
F proves both S and ~S, meaning F is inconsistent.
F proves S.
FProvable(S) doesn’t halt.
F proves ~S.
F proves neither S nor ~S, meaning that S is undecidable for F.
Four Kinds of Provability and Unprovability
In their optimism, the early mathematical logicians such as David Hilbert hoped to find a formal system F such that the undecidable and inconsistent cases would never arise. As I mentioned earlier, Hilbert’s program proposed finding a provably consistent formal system F that could decide all mathematical questions. But Hilbert’s hopes were in vain. For we have Gödel’s Incompleteness Theorem, which tells us that any formal system designed along the lines of Leibniz’s dream or Hilbert’s program will leave infinitely many sentences undecidable.