Undecidability | Research & Encyclopedia Articles

Undecidability

Certain problems that occur in the theory of computation and elsewhere do not have solutions. In those cases it is not that a solution cannot be found easily, nor even that a solution, if found, would be too hard, or perhaps take too long, to implement on a real existing computer. It is simply that there is no well-defined procedure guaranteed to answer the question "yes" or "no" in all cases. In logical terms, neither a well-formed statement nor its negation may be logically implied by a logical system, so it is possible that the algorithm may not halt on either a "yes" or a "no." Problems for which a solution exists, but where the solution cannot be efficiently implemented on existing computers, are called intractable problems. Those for which no general solution exists at all, are called undecidable problems. The study of undecidable problems--or, more generally, the question of which problems are undecidable--is called undecidability.

The earliest and best-known result in undecidability is the famous Halting Problem for Turing machines. Alan Turing, a British mathematician, defined an abstract mathematical model of a computer, which has become known as a Turing machine in his honor. In layman's terms, the Halting Problem simply says that a Turing machine cannot predict or model its own behavior. It is thus always meaningful to ask, "Will this computer program halt if given such-and-such input?"; it is intuitively obvious, however, that there is no computer program that would always be able to answer that question, because it would have to be able to answer the question about itself as well. Turing's genius was in perceiving this now obvious result and proving it in rigorous mathematical terms in the 1930s, even before there were any computers or computer programs. One obvious consequence of the undecidability of the Halting Problem, as evident here, is that human programmers are always necessary, that computer programming cannot be left entirely to computers themselves.

One of the most significant aspects of undecidability is that it extends well beyond questions of mere logic or computation. Many interesting questions in number theory, algebra, combinatorics, graph theory, linguistics, physics, and so on have been shown to be undecidable. Undecidability proofs usually take the form of showing that a certain problem is reducible to the Halting Problem, i.e., that if one were able to solve that certain problem, then one could use that fact to find a solution for the Halting Problem as well. And since we know that there is in fact no solution for the Halting Problem, there must be none for the other problem under consideration as well. Similarly, one is able to build up a group of undecidable problems, and whenever a question arises about a new candidate problem, one can find a proof of undecidability simply by showing that the candidate is reducible to one of the known undecidable problems.

At first it may appear that undecidability is a very negative and depressing thing to know, since it forever places the answers to certain important and useful questions beyond the pale of our understanding. However, mathematicians and computer scientists may welcome proof that a certain question is undecidable because it frees them from the task of finding a solution for it. Indeed, it is better also to be aware early that a task one is attempting is not feasible, than to discover the fact after one has expended a great deal of wasted effort. For this reason, undecidability has been at the forefront of topics of research since the time of Turing. An important result in undecidability, probably the best-known to computer scientists other than the Halting Problem itself, is called Rice's Theorem, after the mathematician who first proved it. Essentially this theorem states that no non-trivial question one could ask about an infinite set is decidable.

It is important to note, however, that proving that a problem is undecidable does not mean that we give up all hope whenever it arises. In most cases this only means that a general solution cannot be found for all cases of the problem. However, it is quite likely that specific cases of the problem will have solutions. For example, there is no computer program that will tell us if any computer program has errors; but there certainly can be a program that will answer the question for a certain large class of useful programs. Having such a program, known in the programming community as a debugger, is of such great benefit that very few working programmers devote any thought to the question of undecidability.