Collected Essays (67 page)

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.

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

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.

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.