Embedded Files
I collect historical anecdotes when something that was not possible from a theoretical point of view turned out to be quite achievable and useful in practice.
Photo of an article "Neural Net Worth" by Neil Savage in CACM Magazine.
There is a widespread belief that it is not possible to make a program, which can determine all bugs in other applications. John MacCormick in his book "What can be computed?" gives a problem of finding all bugs in computer programs as an example of an uncomputable problem, i.e., a problem which is not computable in theory and practice. From the theory, this is absolutely true. It is proved that there is no way to build such a program. Neither today nor in the future.
However, this is only partially true in reality. What was proved is that there is no way to predict whether a given program stops (halts) in the future for any given input looking only at the source code of the program. Right, this is true if we assume all possible programs. Meaningful (useful) programs, meaningless (useless) programs, it doesn't count. Then with a few logical steps, one can show that there is no way to write a program which finds all bugs in any computer program. In reality, we tend to write only a small subset of all possible programs—the useful ones. And we do so in specific ways, which are far from an arbitrary sequence of commands. They have internal structure, they express particular patterns in source code and in their behavior. In fact, the programs that find bugs not only possible to write, but they already exist!
The table from the book "What can be computed?" by John MacCormick, it divides all problems into three main categories: Tractable problems (computable in theory and in practice), Intractable problems (computable in theory, however in practice there is no effective algorithm yet), Uncomputable problems (not computable in theory and in practice, ever).
A note from my "personal Google." It holds two quotes from CACM Magazine about the program called Terminator, which quite often can prove that given program stops in the future for any given input. "Quite often" here means often enough to use it in practice at Microsoft.
Do you have other examples? I would love to hear about them!
Report abuse