Software Design Using C++
Computer Science Theory
The idea here is to present some basic computer science theory that has practical implications. The areas discussed include unsolvable problems, exponential running times, the classification of problems, and proofs of program correctness.
The General Halting Problem
The question: Is there an algorithm which when given any program and any set of input data for the program, can decide in advance whether or not the program will run forever (i.e. never halt)?
Theorem: There can be no such decision algorithm (assuming Church's thesis, which in practice everyone accepts and which says that every function that is computable by some sort of algorithm is computable by a Turing machine).
Practical Conclusion: There are definite limits to what our computer programs can do. There may be no algorithms possible to do some desirable things. In other words, some problems are simply unsolvable.
Exponential Running Times
We have already learned that exponential running times are "horrible" and polynomial running times are fairly reasonable. It appears that some problems may have only exponential running time solutions. This means that except for extremely simple cases of these problems they cannot be solved in a reasonable amount of time on even the fastest of computers (and even though a correct computer program exists to calculate the solutions).
Example: The Traveling Salesperson Problem (TSP)
The problem: Given n interconnected cities and the distances between them, find the lowest-distance tour of all the cities, starting and ending with a given city. A tour never revisits a city (other than the starting city, which we obviously visit twice).
All known solutions of this problem require exponential running time. Thus as n increases, the running time increases at least as fast as some 2^n function (which may have a positive constant in front of the 2^n). When we have n = 10 cities, the problem is solvable in a reasonable amount of time. However, it has been calculated that by the time we reach just n = 30 cities, it would take about 84 trillion centuries on a supercomputer that could do a billion operations per second!
Other problems that we try to solve by computer may also turn out to require exponential running times and hence only be solvable in a reasonable amount of time for very small values of n.
A nondeterministic algorithm is one that assigns different cases of a problem to different processors. It assumes that as many processors are available as needed (an assumption that is not true of real parallel processing machines since they have a definite fixed number of processors).
A problem is NP-complete provided it is in NP and every problem in NP can be reduced to this problem in polynomial time. The TSP has been shown to be NP-complete. This means that if anyone ever does find a polynomial-time solution to the TSP, then all problems in NP will be solvable in polynomial time (hence proving that P = NP after all).
Finally, recall that the General Halting Problem is unsolvable. It, then, gives an example of a problem in the final box of our problem classification scheme.
Conclusion: There are many nasty problems (those not in P) that computers cannot solve at all or cannot solve in a reasonable length of time.
Various efforts have been made to give formal mathematical proofs of the correctness of programs. This would avoid the problem that testing can never guarantee 100% correctness. The difficulty is that formal proofs are very hard to produce and are so far only possible for very short programs (e.g. a few pages in length). Proofs of correctness for commercial software are not possible in the foreseeable future.
Other drawbacks include:
Suppose that array a contains integers at indices 0, 1, 2, etc. with -1 marking the last entry. An example of such an array is shown below:
To prove that the postcondition would hold requires proving the 3 steps given above. In outline the proof goes like this:
Back to the main page for Software Design Using C++