Solved, For All Practical Purposes

Moshe Y. Vardi’s Editor’s Letter "Solving the Unsolvable" (July 2011) raised an important point—that we should reconsider the meaning of unsolvability, especially in terms of its practical application. Even though a problem (such as the Halting Problem) may be theoretically unsolvable, we should, perhaps, still try to solve it.

The proof of undecidability is based on the possibility of self-application; that is, a program cannot look at itself and decide if it is itself stuck in a loop; from a practical point of view, this situation is not relevant. Why even write such a program? The proof does not say I cannot write a server program that looks at running applications to determine if any of them is in a loop.

The same reliance on self-application applies to the Post Correspondence Problem (PCP), a string-matching problem also theoretically unsolvable. The proof does not say PCP is undecidable for any practical problem, only for one using self-application. However, the proof does say if I try to simulate a Turing Machine program that looks to see if it is itself in a loop, then, as in the Halting Problem, PCP is theoretically unsolvable. But from a string-matching point of view, this potential insight about unsolvability is again hardly relevant to the programmer. Perhaps, for all cases of practical interest, PCP is indeed solvable.

The same point applies to the many other theorems that relate to the unsolvability of certain problems. It may be the problems are very difficult to solve; likewise, it may be very difficult to devise a solution for a reasonable sub-problem or solve a sub-problem in polynomial time. In any case, the question of unsolvability might simply be a red herring.

Henry Ledgard, Toledo, OH

Back to Top

Author’s Response:

I do not agree that unsolvability is a "red herring" but a fundamental limit on computability. We do not have an algorithm for program termination. My point was we should take a sober view of unsolvability, recognizing that many unsolvable problems can, in practice, be solved.

Moshe Y. Vardi, Editor-in-Chief

Back to Top

To Program, Imagine All Contingencies

In his Viewpoint "Non-Myths About Programming" (July 2011), Mordechai Ben-Ari said programming requires logical thinking, which is certainly true, but to write a program that interacts with anything—API, device, UI—a programmer must also be able to imagine all contingencies and define appropriate responses. Such talent is orthogonal to following a theorem proof or manipulating algebraic expressions that would be needed for, say, a good grade in high school mathematics.

Tom Moran, Saratoga, CA

Back to Top

Author’s Response:

I agree the definition of logical thinking should be as broad as possible. However, it is an empirical question whether success in high school mathematics predicts the logical thinking needed for programming. I conjecture that the correlation is positive (not 1.0, but certainly not 0.0, orthogonal) and thus a reasonable predictor for use by a guidance counselor.

Mordechai Ben-Ari, Rehovot, Israel

Back to Top

Where Privacy Ends

Besides being a great article on its subject, Stephen B. Wicker’s "Cellular Telephony and the Question of Privacy" (July 2011) also identified a game-changing direction in privacy. Consider that the word "privacy" is oxymoronic when discussing radio transmission; by definition, a radio sends our stuff to places totally beyond our control or authority; think postcard rather than envelope. We can’t give away something and still claim to own it and presume we can tell everyone else how to use it. To my knowledge, no legal precedent exists to empower a nail maker to decree all builders use its products only pointy-side down.

This is a trend (and fallacy) sanctified by the software industry (and others), claiming "It’s mine, even when we have it." Absurd, of course, though it seems to function as the basis for everything from copyright law to digital privacy.

Utterances overheard at a distance are not private; neither are postcards, signs in the front yard, or a radio or wire-line signal. A government might wish to guarantee a certain right of privacy for some particular technology, except that such a guarantee would be a matter of contract law, not of practical expedience. The postal service guarantees privacy (within limits) as part of its service. The phone company does not. I know of no service that allows remote talking that also guarantees confidentiality. The guarantee is to try to ensure confidentiality, or good faith.

Our expectation of privacy ends when the communication leaves our point of control, save for specific guarantees from the final authority, in the U.S., the Federal Government.

What Wicker called "context information" cannot be made private by definition (or the service stops). Presuming protection of related content is just silly; A gives it to B, and B may now do whatever it wants with it or whatever it thinks it can get away with. Wrangling legalisms about what is permitted is the equivalent of rearranging deck chairs as the ship of privacy heads for the bottom.

David Byrd, Arlington, VA

Back to Top