Monday, April 4, 2011

Little Problems, Big Problems, and Reductionism

Small, simple problems can be solved completely.  A "hello world" program can be written that is bug free. An application in propositional logic is not subject to Godel's incompleteness theorem and may be provably correct.
The operation of a Turing machine, however, may prove inconsistent and typical real world computer programs contain bugs.
We can try, then, to decompose big problems into a set of small, simple ones which can be solved independently and then combined (reductionism).  Of course, the interconnections between the little pieces can not be too complex and numerous or we may fail during the recombination step. 
Large, difficult problems that are NOT decomposable may have to be APPROXIMATED by some decomposition that we hope is "close enough."  There may be several such approximations that give different answers to the original problem.

No comments:

Post a Comment