Tikalon Blog by Dev Gualtieri

Alan Turing

June 22, 2012

Tomorrow, Saturday, June 23, 2012, is the hundredth anniversary of the birth of computer science pioneer, Alan Turing (June 23, 1912 - June 7, 1954). Turing died by his own hand at the age of 41, probably a consequence of his being persecuted because of his homosexuality .[1] He packed as much science and mathematics into those 41 years as befits double that lifespan. He also saved many lives (possibly on both sides of the conflict, through the war's coming to an earlier end) through his code-breaking activities during World War II .

Alan Turing rendered in half a million pieces of slate by Stephen Kettle .

This statue, at Bletchley Park , weighs one and a half tons .

(Via Wikimedia Commons).

One consequence of this anniversary is that 2012 was designated as the Alan Turing Year by the Turing Centenary Advisory Committee .[2] The committee organized a conference, the Alan Turing Centenary Conference , beginning today, at the School of Computer Science , University of Manchester , where Turing worked from 1948-1954. The listed attendees include such luminaries as Tony Hoare , Donald Knuth , and Roger Penrose .

Turing was not just celebrated this year. Since 1966, the Association for Computing Machinery has presented the Turing award , which is the equivalent of a Nobel Prize in computing. Vinton G. Cerf and Robert E. Kahn , two of the founding fathers of the Internet, shared the 2004 award. The Rivest -Shamir -Adleman team, who made it a safer place through public key cryptography , received the 2002 award.

In non-technical circles, Turing is best known for the Turing test , which is a test of a machine's ability to mimic intelligence .[3] Essentially, a person converses with a both a human and a computer program using a text-only interface. If the person can't decide which is which, then the computer program passes the intelligence test. One interesting thing is that answers to questions need not be answered accurately. In fact, the computer program must mimic human ignorance as well as human intelligence to pass the test.

Just as physicists find utility in building idealized systems to elucidate principles, such as ignoring friction when investigating mechanics , Turing developed a model of a computer in 1936 that's now called the Turing machine . There are no binary logic gates in this computer, which is just supposed to be able to read and manipulate symbols on a tape according to a table of rules.

Turing used his machine to solve the problem of whether an arbitrary computer program will finish its computation, a problem known as the "Halting problem ." In 1936, he showed that it's impossible to decide by a general algorithm whether a program will finish.[4]

In 1937, Turing used his machine model in a proof that some "decision problems" (called an Entscheidungsproblem in deference to Hilbert , who introduced it) are undecidable .[4] Turing's synthesis of the problem was to state that it was equivalent to asking for an algorithm to decide whether a given statement is provable from axioms . Turing used a variation of Cantor's diagonal argument of the infinity of cardinal numbers .

Turing's most important applied work was in cryptanalysis at Bletchley Park during World War II. Electromechanical computers were de rigueur in those days before electronic computers . Most of these electromechanical computers were based on the abundantly available relays used in telephone switching applications. Turing was instrumental in the 1939 design of an electromechanical code-breaking machine known as the Bombe (see photograph).

Electromechanical Bombe cryptanalysis machine

The Bombe, an electromechanical cryptanalysis machine.

Its code name derives from Bombe glacée , a cannonball shaped frozen dessert.

(Photo by Ted Coles, via Wikimedia Commons).

Another spin-off of his cryptanalysis work was his development, with mathematician Irving J. ("I.J.") Good of Good–Turing frequency estimation , a statistical technique for prediction of the probability of occurrence of types of objects when there's prior, but imperfect, knowledge of their occurrence. The common example is drawing colored lots from a container. After drawing a few of different colors, it's possible to estimate the probability of the next lot being one of the colors already found, or an unknown color.

One interesting theory of Turing's related to the problem of how the tiger gets its stripes. His 1951 paper, "The Chemical Basis of Morphogenesis ,"[5] proposed a reaction–diffusion mechanism by which this can happen. Wrote Turing,

"...A system of chemical substances, called morphogens, reacting together and diffusing through a tissue, is adequate to account for the main phenomena of morphogenesis. Such a system, although it may originally be quite homogeneous, may later develop a pattern or structure due to an instability of the homogeneous equilibrium, which is triggered off by random disturbances."[5]

Just before his death, Turing became interested in the Quantum Zeno effect . Because of quantum uncertainty , a continuously observed particle should never decay . The importance of this effect is on an equal footing with the Einstein-Podolsky-Rosen paradox , getting 446,000 Google results, compared with 224,000 for Einstein-Podolsky-Rosen.

The BBC presented a dramatized biography of Turing, which is available online.[6] The asteroid , 10204 Turing , discovered on August 1, 1997 is named after Turing.

Alan Turing

References: