Collected Essays

by Rucker, Rudy

  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.

  What are these undecidable sentences like? As I mentioned in the introduction, one simple kind of undecidable sentence, call it G, might be characterized in terms of some algebraic property g[n] that a number n might have. It might look like this, where g[n] can be thought of as being a simple algebraic formula with the parameter n:

  (G) For all n, g[n] isn’t true.

  It’s interesting, though a bit dizzying, to compare and contrast two related ways of talking about a sentence S. On the one hand, we can ask if S is true or false in the real world of numbers, and on the other hand we can ask if S or ~S happens to be provable from F . In the case where the sentence G has the form mentioned above, only three possibilities can occur. In order to illuminate the notion of undecidability, let’s take a quick look at the three case.

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

  Nobody will ever manage to bounce a golf ball a thousand times in a row off a putter head.

  There are an endless number of planets in our universe.

  There are an endless number of planets with people indistinguishable from you.

  No human will ever be born with six functioning arms.

  No cow’s spots will ever spell out your first name in big puffy letters.

  Every year with a big birth rate increase is followed by a big war.

  The left wing will dominate American politics more often than the right wing does.

  Mankind will evolve into higher forms of life.

  The majority of times that you move to a different line in a supermarket, the new line goes slower than one of the lines you didn’t pick.

  New races of intelligent beings will emerge over and over for the rest of the time.

  The time of our cosmos extends forever.

  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 readi
ly 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.

  “What do you want to be when you grow up?” the landowner asked me.

  “A businessman,” I replied, wanting to be like my father. He seemed to get a lot of pleasure out of his ever-changing small companies, all of them related to wood. One of them—the Rucker Corporation—had gone bankrupt the year before, but Pop had already put together a new company called Champion Wood Products.

  “Oh, don’t be a businessman, Rudy,” said Pop. “You can do better than that. You’re bright.”

  “Then I’ll be a scientist,” I said.

  As a boy, my absolute favorite reading materials were the Carl Barks Donald Duck and Uncle Scrooge comic books. Once a week I’d accompany my mother to the A & P Supermarket, and she’d give me a nickel for a comic. I loved the irreverence of the characters and the energetic, abbreviated way in which the story hopped from one frame to the next. When grown-ups would ask me how it was that I knew the meaning of some fancy word I might use, I enjoyed telling them I’d learned it from Donald Duck.

  Every Christmas morning, my mother would arrange a fan of books around the base of the tree for me and big brother Embry. Some of the books were science fiction.

  I recall being absorbed by Lee Sutton’s Venus Boy, Andre Norton’s Star Man’s Son 2250 A.D., and a half dozen Robert Heinlein books, including Door Into Summer and Revolt in 2100. Embry was less interested in science fiction than I, but my neighbor and best friend Niles Schoening shared my fascination. We regularly went to the downtown Louisville Free Public Library to pore over their SF holdings—which filled but a single shelf. I remember marveling over the riches to be found in books with titles like The Best Science Fiction of 1949.

  When we were fourteen or fifteen, Niles and I discovered beer, Zen Buddhism, and the beatniks. Jack Kerouac’s On the Road spoke to me like nothing I’d ever read before. To be out in the world, free as a bird, drinking, smoking, meeting women and yakking all night about God—yes!

  Brother Embry was more an aficionado of the juvenile delinquent and hot-rodder culture. He souped up a series of Model A and Model T Fords purchased from farmers who had them in their barns. But he was interested in the beats as well. Niles and I found a set of bongos, copies of Dig magazine, and dozens of back issues of Evergreen Review in Embry’s basement lair.

  These were the old digest-sized issues of Evergreen Review. Raw youth that I was, I initially combed through them in search of titillation. Instead I found excerpts of William Burroughs’s Naked Lunch, poems by Allen Ginsberg and, somehow the most heartening, story after story by Beat unknowns. Men and women writing about their daily routines as if life itself were strange and ecstatic. I wanted to be a beatnik.

  When I was fifteen, Embry and I were in the back yard playing with our rusty old swing set—seeing who could jump the furthest. The chain of the swing broke; I flew through the air and landed badly, rupturing my spleen. Oddly enough, I knew it was my spleen, as I’d recently been studying a paperback book on karate. The pain in my side was at the location marked “spleen
” on my book’s vulnerability chart. The surgeon, a family friend, never got over the fact that little Rudy Rucker had known he’d hurt his spleen.

  Although I didn’t realize it till years later, I would have died of internal bleeding in less than an hour if my father hadn’t rushed me to the hospital to have my spleen removed. Experiencing the anesthetic was very strange—going from the light into the dark and back into the light. It set me to thinking about the fact that one of these days I’d become unconscious for good. Bam and then—nothing.

  While I was in the hospital, my mother brought me a paperback copy of Untouched By Human Hands, a collection of science fiction stories by Robert Sheckley. Somewhere Vladimir Nabokov writes about the “initial push that sets the heavy ball rolling down the corridors of years,” and for me the push was Sheckley’s book. I thought it was the coolest thing I’d ever seen, and I knew in my heart of hearts that my greatest ambition was to become a science fiction writer. Sheckley’s work was masterful, and it had a jokey edge that—to my mind—set it above the more straightforward work of the other SF writers. Most of all, there was something about his style that gave me a sense that I could do it myself. He wrote like I thought.

  And thus, in later years, I became a beatnik-influenced science fiction writer with a cartoony, humorous edge.

  I was born near Louisville on March 22, 1946—the singular cusp of the zodiac, where the world snake bites its tail.

  My earliest memory is of fingerpainting the white expanse of my bed’s footboard with the contents of my diaper. I didn’t yet know it smelled bad. I remember the morning sun slanting in, my mother appearing behind me, her cry of dismay.