DOI: 10.1145/2184319.2184321

The halting Problem in
the Clear Light of Probability

S.Barry Cooper’s article “Turing’s Titanic Ma- chine?”(Mar.2012)con- sidered Alan Turing’s contributions to computability theory, concentrating on the halting problem; that is, decide whether a given program will stop or continue indefinitely. The fact that in general no one can know makes it undecidable. Moreover, it is fundamental to many proofs of undecidability and algorithm complexity, and computer scientists have used it to devise a hierarchy of complexity classes. However, such complexity analysis has also led to seeming contradictions.

Boolean satisfiability (SAT) has been proved NP-complete, so reasonable-size SAT problems should not be solvable, yet in practice some have been solved quickly. Just as there are Turing machines that do not halt, some SAT problems cannot be solved. But how many Turing machines stop? And how many SAT problems can be solved?

Cooper considered relatively recent work on non-classical computers (such as biological computation and quantum computers) and even mentioned evolving intelligent machines. For example, by recasting Turing’s halting problem in a probabilistic light, we were able to show that programs (in a minimal computer architecture) do not, on average, halt. 1 We addressed the halting problem from a probabilistic point of view; that is, if a random program starts, it is, with overwhelming probability, not going to stop.

Execution traces of random pro-
grams are typically short since the
program counter might fall into a
paths could give results on the ineffec-
tiveness of random testing of human-
written programs and its inability to
cover the software under test and lead
to improved search-based and other
testing methods.

Reference

1. langdon, W.b. and Poli, r. Mapping non-conventional extensions of genetic programming. Natural Computing 7, 1 (Mar. 2008), 21–43.

 

Guard Against innovation for its own sake

Peter J. Denning’s Viewpoint “The Idea Idea” (Mar. 2012) resonated with me due to discussions I had at Hewlett-Packard on how best to lead process improvement and innovation. New practices capable of delivering at the bleeding edge must be scouted and de-ployed/replicated. It is usually only after such an effort that a practice gains a theoretical basis, a two-step sequence that goes like this:

˲It works ( replicate/deploy/lever-age); and

˲ This is why it works ( institutional-ize/educate).

During my stint, 1997–2000, as a member of the Software Engineering Process Group (SEPG) at Hewlett-Packard India Software Operations facilitating process improvement across all business lines, SEPG and line management concluded the best ideas originate as new practices in working teams. Teams were therefore encouraged to submit their own best practices to help identify such ideas, which were then analyzed for soundness and selected for deployment and replication. The teams were encouraged to maintain documentation using Deming/Shewart’s Plan, Do, Check, Act (PDCA) at the project level and the Initiating Diagnosing Establishing Acting Leveraging (IDEAL) model at the SEPG level so they could quantify and demonstrate improvement. (PDCA and IDEAL both overlap the Prime Innovation Pattern outlined by Denning.) Selected best practices were then engineered as repeatable processes and institutionalized through associated training and tools. What we wished to guard against was innovation for its own sake.

Ideas generated by research teams often entail too much risk to deploy as-is in industry without first undergoing feasibility studies. For one thing, they often do not scale well, as when, say, a toy programming language is used to make a (perhaps valid) point in a research paper. For another, they may be solutions looking for a problem or inventions without a context—yet.

Mallika Chellappa, Bangalore, india

 

Jahromi Partially Restored With two letters to the editor— “Reinstate Jahromi” (Jan. 2012) and “Justice for Jahromi” (Nov. 2011)—I wrote that Masaud Jahromi, a professor and chair, telecommunications engineering, at the University of Ahlia in Bahrain, had been arrested and imprisoned in April 2011 for speaking at a rally in the Kingdom of Bahrain,