acm-header
Sign In

Communications of the ACM

Review articles

Turing's Titanic Machine?


Alan Mathison Turing, illustration

Credit: Gerard Dubois

Embodied and disembodied computing at the Turing Centenary.

The full text of this article is premium content


Comments


Anonymous

Lance calls Barry out http://blog.computationalcomplexity.org/2012/03/turings-titanic-machine.html


CACM Administrator

The following letter was published in the Letters to the Editor in the June 2012 CACM (http://cacm.acm.org/magazines/2012/6/149799).
--CACM Administrator

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.(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 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

REFERENCE

(1) Langdon, W.B. and Poli, R. Mapping non-conventional extensions of genetic programming. Natural Computing 7, 1 (Mar. 2008), 2143.


Displaying all 2 comments

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.
  

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account