Tikalon Blog is now in archive mode.
An easily printed and saved version of this article, and a link
to a directory of all articles, can be found below: |
This article |
Directory of all articles |
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).
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.
References:
- Still No Pardon for Alan Turing; Watch the Film Breaking the Code, Open Culture, February 10, 2012.
- Jon Gold, "Tech world preps to honor 'Father of Computer Science' Alan Turing, as centenary nears," Network World, June 11, 2012.
- A. M. Turing, "I. - Computing Machinery And Intelligence," Mind, vol. LIX, no. 236 (October 1, 1950), pp. 433-460.
- S. Barry Cooper, "The Incomputable Alan Turing," arXiv Preprint Server, June 8, 2012.
- A. M. Turing, "The Chemical Basis of Morphogenesis," Philosophical Transactions of the Royal Society of London,vol. 237, no. 641 (August 14, 1952), pp. 37-72; available as a PDF file, here.
- Breaking the Code: Biography of Alan Turing (Derek Jacobi, BBC, 1996)
Permanent Link to this article
Linked Keywords: Computer scientist; Computer science; Alan Turing; homosexuality; science; mathematics; code-breaking; World War II; slate; Stephen Kettle; Bletchley Park; ton; Wikimedia Commons; Alan Turing Year; Turing Centenary Advisory Committee; Alan Turing Centenary Conference; School of Computer Science; University of Manchester; Tony Hoare; Donald Knuth; Roger Penrose; Association for Computing Machinery; Turing award; Nobel Prize; Vinton G. Cerf; Robert E. Kahn; Ron Rivest; Adi Shamir; Leonard Adleman; public key cryptography; Turing test; artificial intelligence; mimic intelligence; computer program; physicist; scientific modelling; idealized system; friction; mechanics; computer; Turing machine; binary; logic gate; Halting problem; algorithm; Entscheidungsproblem; Hilbert; undecidable; axiom; Cantor's diagonal argument; infinity; cardinal number; crypyanalysis; Bletchley Park; electromechanical computer; electronic computer; relay; Bombe; Bombe glacée; mathematician; Irving J. ("I.J.") Good; Good–Turing frequency estimation; statistics; probability; lottery; lot; tiger; The Chemical Basis of Morphogenesis; reaction–diffusion; Quantum Zeno effect; quantum uncertainty; elementary particle; decay; Einstein-Podolsky-Rosen paradox; BBC; drama; biography; asteroid; 10204 Turing.