Collected Essays (68 page)

(1) G is false, and ~G is provable.
If G is false, his means there is a specific n such that g[n] holds in the world of numbers. F will be able to prove the instance g[n] simply by checking the arithmetic. Therefore, F will be able to prove ~G.

(2) G is true, and G is provable.
If the G sentence is true in the world of numbers, then g[n] is false for every n. Now in some situations, there may be a clever proof of this general fact from F. I call such a proof “clever” because it somehow has to prove in a finite number of symbols that that g[n] is impossible for
every
n. A general proof doesn’t get bogged down at looking at every possible value of n. It has to use some kind of tricky reasoning to cover infinitely many cases at once.

(3)
G is true, and G is not provable.
In these cases, there is no clever proof. The only way F could prove G would be to look at every possible number n and show that g[n] isn’t true—but this would take forever. In a case like this it’s almost as if G only
happens
to be true. At least as far as F can see, there’s no overarching reason
why
g[n] is impossible for every n. It’s just that, as chance would have it, in the real world there
aren’t
any such n. And thus G is undecidable by F .

The computer scientist Gregory Chaitin suggests that in a case like the third, we think of G as a
random truth
. It’s not true for any deep, theoretical reason. It’s just something that turns out to be so. ( You can find more details in the papers on Chaitin’s home page.)

Note that there’s an endless supply of undecidable sentences S beyond the simple kinds of sentences G that I’ve been discussing . Some initial examples of the next level of complexity might be “For each m there is an n such that g[m, n]” or “There is an m such that for all n, g[m, n].”

Most mathematicians would feel that, in the real world of mathematics, any of these sentences is definitely true or false, regardless of F’s inability to prove either of the alternatives. So the undecidable statements are “random” truths about the mathematical world, brute facts that hold for no particular reason.

But so far, we’ve only been talking about number theory. How do we get to undecidable sentences about the
natural
world? If we accept the HPH, and we assume that any natural process can be regarded as a computation, then we can find undecidability in any complex natural process!

The path leads through the following lemma, proved by Turing in 1936.

Unsolvability and Undecidability Lemma.
If P is a computation with an unsolvable halting problem, and F is a correct formal theory, then there will be infinitely many sentences about P which are undecidable for F.

In this Lemma, by the way, I’m using the phrase “correct formal theory” to mean a formal theory that doesn’t prove things which are false. I won’t go into the somewhat technical details of the proof of this lemma, but the general idea is that there have to be lots of sentences about P that are undecidable for F, for otherwise F could solve P’s unsolvable halting problem.

So now we come to the pay-off. Naturally occurring processes can be thought of as computations. If we accept the Halting Problem Hypothesis, then each naturally occurring process will have an unsolvable halting problem. And then, by applying Turing’s Unsolvability and Undecidability Lemma, we get the following.

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

What makes the Natural Incompleteness Theorem attractive is that the undecidable sentences are
not
just about arithmetic. They’re about the behavior of actual real-world processes.

No matter how thoroughly you try and figure the world out, there are infinitely many things you can’t prove. Here are some examples of potentially undecidable sentences. Each of them may be, in principle, true or false, but only in a random kind of way, in that they’re not proved or disproved by any of our formal theories about the world.

Potentially Undecidable Statements about the Natural World.

Do note that, as with our examples about natural halting problems, we need some analysis of how to take into account the issue that so few of our natural systems can in fact be viewed as potentially eternal. But I’ll leave the fine points of issue for other investigators to work out.

Undecidability Everywhere

It often happens in the history of science that some odd-ball new category is discovered. At first nobody’s sure if any phenomena of this kind exist, but then there’s some kind of logical argument why these odd-ball things have to occur. And then, as time goes on, more and more of the curious entities are discovered until finally they’re perceived to be quite run of the mill. And I think this is what will happen with the notion of undecidable sentences about the natural world.

To dramatize this notion, I’ll present a sustained analogy between the spread of undecidability and the rise of transcendental numbers in mathematics. Brian Silverman suggested this analogy to me in an email.

Transcendental Numbers
. 300 BC. The Greeks worked primarily with real numbers that can be expressed either as the fraction of two whole numbers, or which can be obtained by the process of taking square roots. By the time of the Renaissance, mathematicians had learned to work with roots of all kinds, that is, with the full class of algebraic numbers—where an algebraic number can be expressed as the solution to some polynomial algebraic equation formulated in terms of whole numbers. The non-algebraic numbers were dubbed the
transcendental
numbers. And, for a time, nobody was sure if any transcendental numbers existed.

Undecidable Sentences
. 1920. In David Hilbert’s time, it seemed possible that, at least in mathematics, every problem could be decided on the basis of a reasonable formal system. This was the inspiration for Hilbert’s program.

Transcendental Numbers
. 1884. The first constructions of transcendental real numbers were carried out by Joseph Liouville. Liouville’s numbers were, however, quite artificial, such as the so-called Liouvillian number:

0.1100010000000000000000010000…

The number has a 1 in the decimal positions n! and 0 in all the other places. Someone might readily say that a number like this is unlikely to occur in any real context. (n! stands for “n factorial” which is the product 1*2*…*n of all the integers from 1 to n.)

Undecidable Sentences
. 1931. Kurt Gödel proved the existence of some particular undecidable algebraic sentences. These sentences were somewhat unnatural. Relative to a given formal system F, they had the form “This sentence is not provable from F,” or the alternate form, “The contradiction 0 = 1 is not provable from the formal system F.”

Transcendental Numbers
. 1874. Georg Cantor developed his set theory, and showed there are an infinite number of transcendental numbers. Someone could say that Cantor’s transcendental numbers aren’t numbers that would naturally occur, that they are artificial, and that they depend in an essential way upon higher-order concepts such as treating an infinite enumeration of reals as a completed object.

Undecidable Sentences
. 1936. Building on Gödel’s work, Alan Turing proved his theorem on the unsolvability of the halting problem. He immediately derived the corollary that there are infinitely many undecidable sentences of mathematics, and that these sentences came in quite arbitrary forms. Even so, the specific examples of such sentences that he could give were still odd and somewhat self-referential, like Gödel’s undecidable sentences.

Transcendental Numbers
. 1873. Charles Hermite proved that the relatively non-artificial number e is transcendental.

Undecidable Sentences
. 1965. On an entirely different front, Paul J. Cohen proved that an important question about infinite sets called the continuum hypothesis is undecidable from the known axioms of mathematics. (Cohen’s proof built on an earlier result proved by Kurt Gödel in 1946.) 1970. Back in the realm of unsolvable halting problems, Julia Robinson, Martin Davis, Yuri Matiyasevich showed that among the sentences undecidable for any formal theory we’ll find an infinite number of polynomial Diophantine equations which don’t have any whole number solutions, but for which we can’t prove this fact. This means there a very large range of ordinary mathematical sentences which are undecidable.

Transcendental Numbers
. 1882. Ferdinand Lindemann proved that the garden variety number pi is transcendental.

Undecidable Sentences
. 2002. Wolfram pointed out that we should be able to find numerous examples of undecidability in the natural world.

And 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.

References

Chaitin, G. J., 1999.
The Unknowable
. New York: Springer.

Leibniz, G.W. and Gerhardt, C.I. (ed.), 1978.
Die philosophischen Schriften von Gottfried Wilhelm Leibniz
. Hildesheim: Georg Olms Verlag.

Rucker, R., 1982.
Infinity and the Mind
. Boston: Birkhäuser.

Rucker, R., 2005.
The Lifebox, the Seashell, and the Soul
. New York: Thunder’s Mouth Press.

Wolfram, S., 2002.
A New Kind of Science
. Champaign: Wolfram Media.

Note on “An Incompleteness Theorem for the Natural World”

Written in 2012.

To appear in
Essays For the Tenth Anniversary of A New Kind of Science
.

 This paper is adapted from my book,
The Lifebox, the Seashell and the Soul
, and formal details about my argument can be found in that book’s appendix and in its footnotes. Note that in my book, I used a somewhat unfortunate terminology. I gave what I here call the
Halting Problem Hypothesis
a less precise name: I called it the
Natural Undecidability Hypothesis
. And what I here call the
Natural Incompleteness Theorem
is given the a less dramatic name in my bok: the
Principle of Natural Undecidability
.

Ever since graduate school I’d wanted to find a version of Gödel’s Incompleteness Theorem that applies to the physical world, and I feel like here I achieved what I wanted. Unlike my argument in “Everything is Alive,” the reasoning in “An Incompleteness Theorem for the Natural World” is meant in complete earnest.

But by the time I published
The Lifebox, the Seashell and the Soul
, I was no longer in academia, so I never got around to promoting my theorem among logicians and philosophers. I got my fill of doing that when I was in my thirties. I have some small hope that my theorem will receive some recognition when it appears in Wolfram’s forthcoming anthology of essays relating to his NKS, or
New Kind of Science
. But this recognition may take a long time, given that Wolfram is not in good repute among today’s academics. The history of philosophy flows at a leisurely pace.

Part 6: PERSONAL HISTORIES

Autobiographical Overview (2004)

Age 2, in Louisville, Kentucky.

My father ran a small furniture-manufacturing company when I was growing up near Louisville, Kentucky. When I was about ten—which would have been 1956—my mother, father and I drove out to a well-to-do friend’s country retreat to get big flat river rocks for my mother to put into her rose garden.