Next: The mathematics of creativity Up: expt72h Previous: Physics

# Hierarchies of truth and decidability

Hierarchies of truth and decidability

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