Collected Essays (66 page)

I would like to thank Masatoshi Murase for having organized this interesting conference, and Mark van Atten for his useful comments on an earlier draft of this paper.

References:

[Rucker 2007] Rudy Rucker,
Postsingular
, Tor Books, New York 2007.

[Rucker 2009] Rudy Rucker,
Hylozoic
, Tor Books, New York 2009.

[Skrbina 2005] David Skrbina, Panpsychism in the West, MIT Press, Cambridge MA 2005.

[Rucker 2005] Rudy Rucker,
The Lifebox, The Seashell and the Soul
,
Thunder’s Mouth Press, New York 2005.

[Wolfram 2002] Stephen Wolfram,
A New Kind of Science
, Wolfram Media, Champaign IL 2002.

[Langton 1990] Christopher G. Langton, “Computation at the edge of chaos,”
Physica D
,
42
, 1990.

[Damasio 1999] Antonio Damasio,
The Feeling of What Happens: Body and Emotion in the Making of Consciousness
, Harcourt, New York 1999.

[Walker 2004] John Walker, “Computation, Memory, Nature, and Life,” on his
website
.

[Rucker 2008] Rudy Rucker, “The Great Awakening,” in Damien Broderick, ed.,
Year Million: Science at the Far Edge of Knowledge
. Atlas Books, New York 2008.

Note on “Everything Is Alive”

Written in 2009.

Appeared in the Proceedings of the Kyoto “What is Life” Conference.

With friendly schoolgirls in a Kyoto bus, 2007.

In October, 2007, Sylvia and I got a free trip to Kyoto, where I spoke at a conference on the theme, “What is Life.” It was an eccentric mix of talks—a number of them were what most academics would call pseudoscience. Which might help explain my presence! I worked up a “rigorous” proof of the hylozoic hypothesis that every object is not only conscious but literally alive. Note that “hylozoism” is indeed a real word, you can look it up on Wikipedia. And I used this notion in my novel
Hylozoic.
Note that a crucial step of my proof of my tenet that “Everything is Alive” is based on a SFictional fantasy that appears in my novel. I enjoyed taking advantage of the intellectually loose nature of the conference to write an academic paper that is in some sense a flight of fancy. This said, I really do, when I remember to, believe that all the objects around
are
in a very real sense alive. Why not think this? It makes the world a cozier place.

An Incompleteness Theorem for the Natural World

Introduction

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.” [Gottfried Leibniz,
Die philosophischen Schriften
, edited by C. I. Gerhardt. Translation by George MacDonald Ross.]

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 (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, m
²
¹ n
⁵
+ 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.