Communications of the ACM

Letters to the editor

The Halting Problem in the Clear Light of Probability

By CACM Staff
Communications of the ACM, June 2012, Vol. 55 No. 6, Pages 6-7
10.1145/2184319.2184321
Comments

S. Barry Cooper's article "Turing's Titanic Machine?" (Mar. 2012) considered 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.¹ 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 programs are typically short since the program counter might fall into a tight loop in which a small number of instructions repeats infinitely. Likewise, most traces in human-written software cover only a small fraction of the program. In both human-written and random programs most of the code is not run, so might as well be random. Studying random execution paths could give results on the ineffectiveness 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.

Software engineers do not write random programs; neither does genetic programming. Both human-written and genetic-programming programs contain many repeated instructions, or clones not found in their random counterparts. However, studying random programs helps reveal the fundamental nature of coding. For example, I proved that the fitness of lossless functions (such as in reversible and quantum computing) follows a Gaussian distribution. Also if inputs are unprotected, traditional computing quickly loses information. Loss of information provides a theoretical justification for common heuristics (such as write-protecting inputs). Meanwhile, information theory (in particular Shannon entropy) can be used as part of the fitness calculation a programmer would use to guide artificial evolution.

W. B. Langdon, London

Back to Top

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 deployed/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/leverage); and
• This is why it works (institutionalize/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 repeat-able 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

Back to Top

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, in clear violation of the International Covenant on Civil and Political Rights to which Bahrain has acceded.

When he was released on bail in September 2011, a Bahraini colleague brought to his attention my January letter. Jahromi himself then took the initiative to send me an email message explaining what had happened. He also said how much he appreciated Communications for publicizing his situation. Following several delays, a trial was held January 19, 2012. Though the Bahrain Public Prosecutor recommended the charges be dropped, as they related to "freedom of speech," consistent with the Bahrain Independent Commission of Inquiry, Jahromi was convicted and sentenced to four months in prison and ordered to pay a fine of approximately $1,400. As he had already been imprisoned for five months, the court simultaneously suspended the four months. However, Jahromi had also been suspended from his university positions without pay from the date of his arrest, and the university did not reinstate him following the January 19 court ruling.

On February 20, 2012, Jahromi sent me another email message saying he had been reinstated in the university but not to his old positions. On March 20, 2012, he sent yet another email message, and then a clarification April 10, 2012, saying he had at last been reinstated to his old positions by the university. However, the government had not returned his passport or ID card, which it took from him April 14, 2011. Hence, he is not allowed to travel or attend scientific conferences outside Bahrain. He has since appealed and will continue to do so until all his rights are restored.

In his last email message, he thanked those who had supported him, including the Committee of Concerned Scientists (I am Vice-Chair, Computer Science), Scholars at Risk, the Committee on Academic Freedom in the Middle East and North Africa of the Middle East Studies Association, and Islamic Human Rights (London).

Publicity due to Communications and other organizations may have played a crucial role, helping pressure the government of Bahrain to abide by its commitment to human rights. Communications has always played an important role in publishing scientific results but also by giving worldwide attention when scientific freedom and human rights of computer professionals are violated or at risk. While human rights remain a problem in Bahrain, it is uplifting to know that Jahromi has had at least some of his restored. We now look forward to the time when all are restored.

Jack Minker, College Park, MD

Back to Top

Survival and Computation

Daniel Reed's blog (Sept. 2, 2011) and Douglas Robertson's related letter "Insight, Not Numbers" (Apr. 2012) speculated on why we compute, suggesting two noble motivations: "know and understand" and "insight." Robertson also added interesting comments regarding algorithmic information theory. However, both authors seemed to take a purely philosophical or research perspective, ignoring the large number of real-world corporate examples in which the primary motivation for computing is that many businesses would otherwise be unable to deliver services and products to their customers or manage, organize, store, or access in a timely fashion the ever-increasing data needed to run a large enterprise, especially one for which "information" is a key part of its products.

Reed's description of "the exhilaration when the idea takes shape in code, then begins to execute" is something that first attracted me to computing and I have always regarded it as a "perk" of the profession. However, it was always the need to solve utilitarian problems to improve the corporate ability to process data and support customers that justified my paycheck.

In real-world corporate computing, the idea of information conservation is not a limiting factor for computation, as one does not deal with a closed system. Every second of every day new data pours in from customers and corporate processes alike, accumulating in large databases. The challenge is to determine what data is no longer useful and how and when to discard it.

Joel C. Ewing, Bentonville, AR

Back to Top

The String at t in C

Something seemed wrong in the following code portion of the letter by Paul W. Abrahams "Still Paying for a C Mistake" (Apr. 2012):

copies the string at s to the string at t. Given that assignments happen from right to left, would it not have made more sense to say it copies the string at t to the string at s? That is, would a simple x=y assign y to x?

Robert Wilkens, Levittown, NY

Back to Top

Author's Response:

Wilkins is right. I should have said the code copies the string at t to the string at s. It was a slip-up, though, fortunately, the intent and the repair are obvious to anyone who knows C.

Paul W. Abrahams, Deerfield, MA

Back to Top

The Post Office Deficit and Technology

Though Michael A. Cusumano offered interesting ideas as to new postal services in his Viewpoint "Can Services and Platform Thinking Help the U.S. Postal Service?" (Apr. 2012), he failed to explore his reference to the "annual obligations for retiree health benefits" at the depth it deserves.

The Postal Accountability and Enhancement Act of 2006 (PAEA) requires the USPS to pre-fund retiree benefits for employees who have not been hired yet—and, with the 75-year pre-fund mandate, possibly even for those not even born yet. By requiring this transfer of funds from the USPS to the U.S. government general fund, the USPS is required to make the U.S. budget deficit look smaller at the cost of an artificial deficit in its own budget. Consumer advocate Ralph Nader once said that if not for PAEA, the USPS would have a surplus of at least $1.5 billion.¹

Though computer science is naturally drawn to technological solutions, legal and social pressure is sometimes a more appropriate place to look for the source (and solution) of a problem.

John J. Deltuvia, Jr., Jackson, NJ

Back to Top

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.

---

No entries found