Communications of the ACM

Embodied and disembodied computing at the Turing Centenary.

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.