PDF version
of this book

**Next:** Formal logic **Up:** Mathematical structure
**Previous:** Structure and consciousness **Contents**

We do not think of mathematics as creative. It gives absolute truths like . However, the search for logical absolutes uncovered a hierarchy of problems that are logically determined yet unsolvable.

Logically determined unsolvable problems exist because one can
ask if a property is true for *any* or *all* integers.
For example the Halting Problem asks if a computer program will
*ever* halt^{5.1} This is not a question about
what the computer will do at some particular time. It is a question
about what it will do over an unlimited time.

Real computers halt when the power goes off. They have a limited amount of memory. The Halting Problem is about an abstract computer that runs forever and has no fixed limit on memory.

Computers follow an exact set of rules. One always know what the
next step is and thus what a computer will do at any time. But one
cannot, in general, know if it will it ever do something like halt.
If one waits long enough and it *does* halt, one knows that.
Until and unless the program halts. one cannot know if one has
waited long enough. To prove a computer *never* halts requires
something more than following the steps the computer takes.

There is nothing special about halting. An equivalent problem comes from asking if the computer program will ever accept more input. No doubt you have experienced this problem while waiting for a response from your computer. You don't know if it requires rebooting or will eventually respond.

The Halting Problem is at the base of an unlimited hierarchy of unsolvable problems. A step up the hierarchy asks if a computer program will generate an infinite number of outputs. Instead of asking will it ever do something one asks will it keep doing something again and again with no limit.

One can go to higher levels by interpreting a program's output as a new computer program. This is possible because all computer programs can be numbered. They are stored in computer memory as very long sequences of digits.

One can interpret any number as a computer program. Most numbers will not correspond to a meaningful program, but some will.

Using this idea one can ask if a program has an infinite number of outputs an infinite subset of which encode a computer program that itself has an infinite number of outputs. This method of defining higher levels of unsolvable problems can be iterated and generalized in obvious and very complex non obvious ways.

There is a hierarchy of axioms of mathematics that solves these
problems. A mathematical axiom is an assumption.
It cannot be derived from more basic axioms. It must be assumed as
true. The parallel postulate discussed in Section1.1 is an example. There is some
axiom that can correctly solve every Halting Problem, but no finite
set of axioms can solve all Halting Problems. In standard
mathematics this hierarchy is extended by adding axioms that assert
the existence of `large' infinite sets. Since the unsolvable
problems refer to mechanistic processes (what will a program do
*eventually*?) it is possible to extend this hierarchy by
adding axioms about such processes. The question of how best to
extend this hierarchy is addressed in Section 6.9.

PDF version
of this book

**Next:** Formal logic **Up:** Mathematical structure
**Previous:** Structure and consciousness **Contents**

home | consulting | videos | book | QM FAQ | contact |