computability and complexity

Interestingly, one of the important discoveries of 20th-cen-tury mathematics is that certain kinds of problems were not computable. The Turing machine and Alonzo Church’s lambda calculus provided equivalent models that could be used to determine what was computable (see Turing, Alan Mathison, and Church, Alonzo). Thus far, the equiva-lence between the Turing machine and actual computers has held. That is, any decision problem (a problem with a “yes” or “no” answer) that can in theory be solved with a Turing machine can in theory be solved by any actual com-puter. Conversely, if a problem can’t be solved by a Turing machine, it cannot be solved by a computer, no matter how powerful.

The Halting Problem

The Halting problem is a classic example of an undecidable problem (or proposition). The problem is this: Given any

computer program, can you determine whether the pro-gram will halt (end) given any input? There are specific programs that can be shown to halt on particular inputs. For example, this program:

If Input = 99 then end.

will obviously halt on an input of 99. But to decide whether a determination can be made for any program for any input, it is only necessary to construct a logical paradox. Assume that there is a program P that halts if and only if it receives input D. (Further assume that the program can print some-thing to let you know that it has halted.)

Since the input can be anything, you can let it be a copy of the program itself. The question then becomes: Will the program halt if it is given a copy of itself? Create a proce-dure (or subroutine) called HaltTest, and define it as:

If P halts then print “Halted” else print “Didn’t Halt.”

Now create another program called Main. It calls Halt-Test and is programmed to do the opposite of what HaltTest indicates.

If HaltTest (Main) prints “Yes” then loop forever else halt;

But what happens when Main is run? It calls HaltTest, giving itself (Main) as input. If HaltTest halts, then Main loops forever. But if HaltTest doesn’t halt, then Main halts. But this means that Main halts if it doesn’t halt, and doesn’t halt if it halts. This paradox shows that whether Main halts is undecidable.

The undecidability of the Halting problem has some interesting implications. For example, it means that there is no way a computer can reliably determine that a program does not contain an infinite loop. Also, because a math-ematical function f(x) is equivalent to a computer program with input x, similar proofs by contradiction can be written to show that it can’t be decided whether a program will halt on all inputs (which is equivalent to f(x) being defined for all x.) Nor can it be decided whether two different programs (or mathematical functions) are equivalent for all x.

It is important to realize that a program (or function) being undecidable in all cases doesn’t necessarily mean that it can’t be decided for some cases (or inputs). Indeed, the answer of the Halting Problem for any given input can be determined by feeding that particular input to the program, which will either halt or run forever.

Complexity

If a problem turns out to be computable, we then enter the realm of complexity—the analysis of how much com-putation will be required (see algorithm). Sometimes a designer can devise a significantly faster algorithm for a given problem (such as finding prime factors or sorting). However, other problems appear to have complexity based on an exponential expression, meaning that they become more complex much more rapidly as the input increases. An example is the Traveling Salesman Problem, which is to find the most efficient route for a person traveling to a num-ber of cities to visit each of the cities.

Mathematicians therefore categorize the complexity of problems as P (solvable in a polynomial period of time), EXP (requiring an exponential time), or an intermediate class NP, which means “nondeterministic polynomial.” An NP problem is one that can be solved in polynomial time if one is able to guess (and then verify) the answer. The Trav-eling Salesman Problem is believed to be in the NP class.

While abstruse, the study of computability and complex-ity has important implications for practical applications. For example, determining the complexity of a crypto-graphic algorithm can help determine whether the resulting encryption is strong enough to withstand the efforts of a feasible attacker.