PDF version of
this poster presentation

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

Hierarchies of truth and decidability

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.

PDF version of
this poster presentation

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

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