Overview of Computability and Unsolvability

Burroughs B5500 stack architecture system 1960s.

Overview of Computability and Unsolvability

April 21, 1997

Computability and Unsolvability concerns itself with the existence of exclusively mechanical procedures that solve diverse problems. Automata Theory is a branch of pure mathematics that holds interest for nonmathematicians because its utility in philosophy and theoretical computer science. The Gödel Incompleteness Theorem and the existence of ultimately unsolvable problems are results of Computability and unsolvability research which have philosophical implications. Another important result of the field is the existence of the universal Turing Machine which has served fruitfully as an abstract model of the digital computer; this result is one of the sources of the origin of automata theory as an important field of theoretical computer science. In particular this result has modeled those problems which could conceivably be modeled for solution by any deterministic computing device. The unsolvability of the halting problem is another noteworthy result of research in these areas. The halting problem asks whether there is a general procedure that can determine whether any given set of program instructions contains non terminating sub procedures. The programmer who has tried to debug code of a hard to find infinite loop can continue to despair as no foolproof debugging tool for such situations will ever be found.

The primary work of contemporary mathematicians consists in determining the truth or falsehood of various propositions concerning mathematical objects. For example, real numbers, rational numbers, continuously differentiable functions, etc. However, computability and unsolvability has as its main subject of investigation the existence of algorithms or effective computational procedures which are able to solve various problems. The theory of computability and unsolvability is also known as the theory of recursive functions. A recursive procedure or function is defined as one which can repeat itself indefinitely until a given condition is met, e.g. finding a solution to the problem it was to solve.

For thousands of years questions of what is logically possible and how that knowledge can be applied to outstanding problems have perplexed and encouraged mathematicians and scientists. Developments in theoretical mathematics have often pointed the way to later developments in the sciences and especially to the models used to analyze the data those sciences are concerned with. The classic example of the preceding is Issac Newton’s contemporaneous development of the calculus and Newtonian physics. It is also the case that the prior existence of hyperbolic geometry facilitated Einstein’s development of his relativity theories. One such modeling application is seen in the automation of algorithms that determine the computability of a given problem or that attempt to automate the search for the solution to an outstanding problem. This is seen as particularly valuable in modeling other complex scientific problems and extensive and complicated software projects. Artificial intelligence and mathematical combinatorics are just two of the areas where computability research has played a role.

One example of a long standing problem only recently solved by the electronic computer is Robin’s Theorem. Complex iterative procedures involving binary data trees in computer science are in the province of the field. These data structures seem particularly well suited to the demands of computability and unsolvability research and vice versa; recursive and iterative algorithms can be used to traverse these structures and the nodes of the tree can be used to store relevant data for later retrieval by these processes. The automated generation of theorems and their proofs by effective computational procedures is the main area of research that I will be investigating. The axioms of a given mathematical logic can be viewed as the building blocks of proofs, really sequences of consequences of the given axioms, from which an effective computational procedure can derive a valid theorem by stringing together the consequences of the logical axioms into its proof.

In conclusion the investigation of the field will center around two main questions. 1) What are the principal recent results and encouraging areas of current research in the field? 2) How is this research being implemented? In particular with regard to the use of high performance computing devices to implement this research.