Completed
second draft of this book

PDF version
of this book

**Next:** Formal logic **Up:** Mathematical structure
**Previous:** Mathematics 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
halt^{3.1} at *any* future 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. It can keep asking for another disk and can ask to read and write on any disk it previously used.

Computers follow an exact set of rules. We always know what the next step is and thus what a computer will do at any time. But we cannot in general know if it will ever do something like halt. If we wait long enough and it does halt we will know this. But we can never know if we have 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. We get an equivalent problem when we ask if the computer program will ever accept more inputs. No doubt you have experienced this problem while waiting for a response from your computer. You never know if it requires rebooting or will eventually respond.

The halting problem is at the first level of an unlimited hierarchy of unsolvable problems. The next level asks if a computer program has an infinite number of outputs.

For higher levels in the hierarchy one must interpret a program's output as a new computer program. This is possible because all computer programs can be interpreted as numbers. They are stored in computer memory as a very long sequence of digits. Computers translate programming instructions in a language that programmers use to the numeric code of the computer.

One can interpret any number generated by a computer program as another computer program. Most numbers will not correspond to a meaningful program for a particular computer but some will. Every program for a specific computer has a number that encodes it.

The next level in the hierarchy of unsolvable problems asks 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 second hierarchy that solves these problems. Every
Halting Problem can be solved at some level in this hierarchy, but
no single level can solve all Halting Problems. In formal
mathematics these hierarchies are implicitly 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 the
hierarchies by adding axioms about such processes. We will return
to the question of how best to extend these hierarchies in
Section 4.8.

To develop and explore these hierarchies we give an outline of the underlying mathematics. We talk about properties of computer programs to make abstract mathematics concrete and intuitive. Most of mathematics can be interpreted as properties of computer programs. This is another reason to doubt the existence of infinite totalities. For some of these interpretations we need to consider computer programs that follow an increasing number of divergent paths like biological evolution. But more about that later. We begin with formal logic where mathematics and the logical construction of computers both start.

Completed
second draft of this book

PDF version
of this book

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

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