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

# Logically determined unsolvable problems

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