by DK
A man provided with paper, pencil, and rubber, and subject to strict discipline, is in effect a universal machine.
Alan Turing
Clerks at work in Hut 8, Bletchley Park, UK, during World War II. At one point, Turing led the work of Hut 8, which deciphered communiqués between Adolf Hitler and his forces.
ALAN TURING
Born in London in 1912, Alan Turing was described as a genius by his teachers. After graduating with a first-class degree in mathematics from the University of Cambridge in 1934, he went on to study at Princeton in the US.
Returning to the UK in 1938, Turing joined the Government Code and Cypher School at Bletchley Park. After war broke out in 1939, he and others developed the Bombe, an electromechanical device that deciphered enemy messages. Following the war, Turing worked at Manchester University, where he designed the Automatic Computing Engine (ACE) and developed further digital devices.
In 1952, Turing was convicted of homosexuality, then a crime in the UK. He was also barred from working on codebreaking for the government. To avoid prison, Turing agreed to hormone treatment to reduce his libido. In 1954, he committed suicide.
Key work
1939 “Report on the Applications of Probability to Cryptography”
The halting problem
Turing approached this problem as a thought experiment. He began by imagining a machine that was able to say whether any algorithm (A) would halt (provide an answer and stop running) when given an input to which the answer was either Yes or No. Turing was not concerned with the physical mechanics of such a machine. Once he had conceptualized such a machine, however, he could theoretically take any algorithm and test it using the machine to see if it halted.
In essence, the Turing machine (M) is an algorithm that tests another algorithm (A) to see if it is solvable. It does this by asking: does A halt (have a solution)? M then reaches an answer of Yes or No. Turing then imagined a modified version of this machine (M*), which would be set up so that if the answer was Yes (A does halt), then M* would do the opposite—it would loop forever (and not halt). If the answer was No (A does not halt), then M* would halt.
Turing then took this thought experiment further by imagining that you could use the machine M* to test whether its own algorithm, M*, would halt. If the answer was Yes, the algorithm M* will halt, then the machine M* would not halt. If the answer was No, the algorithm M* never halts, then the machine M* would halt. Turing’s thought experiment had, therefore, created a paradox which could be used as a form of mathematical proof. It proved that, because it was impossible to know if the machine would ever halt or not, then the answer to the decision problem was No: there was no universal test for the validity of algorithms.
The Turing machine consists of a head that reads data from an infinitely long tape. The machine’s algorithm might either instruct the head or the tape to move—to go left, right, or stay still. The memory keeps track of changes and feeds them back into the algorithm.
We need to feed [information] through a processor. A human must turn information into intelligence or knowledge. We’ve tended to forget that no computer will ever ask a new question.
Grace Hopper
American computer scientist
Computer architecture
The Turing machine had not finished its job. Turing and others realized that this simple concept could be used as a “computer.” At the time, the term “computer” was used to describe a person who carried out complex mathematical calculations. A Turing machine would do so using an algorithm to rewrite an input (the data on the tape) into an output. In terms of computing ability, the algorithms at work in a Turing machine are the strongest type ever devised. Modern computers and the programs that run on them are effectively working as Turing machines, and so are said to be “Turing complete.”
As a leading figure in mathematics and logic, Turing made important contributions to the development of real computers, not just virtual ones. However, it was Hungarian mathematician John von Neumann who contrived a real-life version of Turing’s hypothetical device using a central processing unit (CPU) that converted an input to an output by calling up information stored in an internal memory and sending back new information to be saved. He proposed his configuration, known as the “von Neumann architecture,” in 1945, and today, a similar process is used in almost every computing device.
A Turing Bombe, used to decipher coded messages, has been rebuilt at the museum at Bletchley Park, the British code-breaking center during World War II.
Binary code
Turing did not initially envisage that his machine would use only binary data. He merely thought it would use code with a finite set of characters. However, binary was the language of the first Turing-complete machine ever built, the Z3. Constructed in 1941 by German engineer Konrad Zuse, the Z3 used electromechanical relays, or switches, to represent 1s and 0s of binary data. Initially referred to as “discrete variables,” in 1948 the 1s and 0s in computer code were renamed “bits,” short for binary digits. This term was coined by Claude Shannon, a leading figure in information theory—the field of mathematics examining how information could be stored and transmitted as digital codes.
Early computers used multiple bits as “addresses” for sections of memory—showing where the processor should look for data. These chunks of bits became known as “bytes,” spelled this way to avoid confusion with “bits.” In the early decades of computing, bytes generally contained 4 or 6 bits, but the 1970s saw the rise of Intel’s 8-bit microprocessors, and byte became the unit for 8 bits. The 8-bit byte was convenient because 8 bits have 28 permutations (256), and can encode numbers from 0 to 255.
Armed with a binary code arranged in sets of eight digits—and later even longer strings—software could be produced for any conceivable application. Computer programs are simply algorithms; the inputs from a keyboard, microphone, or touchscreen are processed by these algorithms into outputs, such as text on a device’s screen.
The principles of the Turing machine are still used in modern computers and look set to continue until quantum computing changes how information is processed. A classical computer bit is either 1 or 0, never anything in between. A quantum bit, or “qubit,” uses superposition to be both a 1 and 0 at the same time, which boosts computing power enormously.
The popular view that scientists proceed inexorably from well-established fact to well-established fact, never being influenced by any unproved conjecture, is quite mistaken.
Alan Turing
The Turing test
In 1950, Turing developed a test of a machine’s ability to exhibit intelligent behavior equivalent to, or indistinguishable from, that of a human. In his view, if a machine appeared to be thinking for itself, then it was.
The annual Loebner Prize in Artificial Intelligence (AI) was inaugurated in 1990 by American inventor Hugh Loebner and the Cambridge Center for Behavioral Studies, Massachusetts. Every year, computers using AI try to win the prize. The AIs must fool human judges into thinking they are human rather than a computer program. AIs who progress to the final take it in turns to communicate with one of four judges. Each judge is also communicating with a human and must decide whether the AI or the human is most humanlike.
Over the years the test has had many critics, who question its ability to truly judge the intelligence of an AI effectively or see the competition as a stunt that does not advance knowledge in the field of AI.
See also: Euclid’s Elements • Eratosthenes’ sieve • 23 Problems for the 20th century • Information theory • Cryptography
IN CONTEXT
KEY FIGURE
Frank Benford (1883–1948)
FIELD
Number theory
BEFORE
1881 Canadian astronomer Simon Newcomb notices that the pages most often referred to in logarithm tables are for numbers starting with 1.
AFTER
1972 Hal Varian, an American economist, suggests using Benford’s law
to detect fraud.
1995 American mathematician Ted Hill proves that Benford’s law can be applied to statistical distributions.
2009 Statistical analysis of the Iranian presidential election results shows that they do not conform to Benford’s law, suggesting that the election may have been rigged.
It might be expected that in any large set of numbers, those that start with the digit 3 would occur with roughly the same frequency as those that start with any other digit. However, many sets of numbers—a list of populations for US villages, towns, and cities, for example—show a distinctly different pattern. Often in a set of naturally occurring numbers, around 30 percent of the numbers have a leading digit of 1, around 17 percent have a leading digit of 2, and less than 5 percent have a leading digit of 9. In 1938, American physicist Frank Benford wrote a paper on this phenomenon; mathematicians later referred to it as Benford’s law.
Recurring pattern
Benford’s law is evident in many situations, from the lengths of rivers to share prices and mortality rates. Some types of data fit the law better than others. Naturally occurring data that extends over several orders of magnitude, from hundreds to millions, for example, fulfils the law better than data that is more closely grouped. The numbers in the Fibonacci sequence follow Benford’s law, as do the powers of many integers. Numbers that act as a name or label, such as bus or telephone numbers, do not fit.
When numbers are made up, they tend to have a more equal distribution of leading digits than if they followed Benford’s law. This has enabled investigators to use the law to detect financial fraud.
Funnily, of the 20 data sets that Benford collected, six of the sample sizes have leading digit 1. Notice anything strange about that?
Rachel Fewster
Statistical ecologist, New Zealand
See also: The Fibonacci sequence • Logarithms • Probability • Normal distribution
IN CONTEXT
KEY FIGURE
Claude Shannon (1916–2001)
FIELD
Computer science
BEFORE
1679 Gottfried Leibniz develops the ancient idea of binary numbering.
1854 George Boole introduces the algebra that will form the basis for computing.
1877 Austrian physicist Ludwig Boltzman develops the link between entropy (measure of randomness) and probability.
1928 In the US, Ralph Hartley, an electronics engineer, sees information as a measurable quantity.
AFTER
1961 German physicist Rolf Landauer shows that the manipulation of information increases entropy.
In 1948, Claude Shannon, an American mathematician and electronics engineer, published a paper called A Mathematical Theory of Communication. This launched the information age by unlocking the mathematics of information and showing how it could be transmitted digitally.
At the time, messages could only be transmitted using a continuous, analog signal. The main drawback to this was that waves become weaker the further they travel, and increasing background interference creeps in. Eventually, this “white noise” overwhelms the original message.
Shannon’s solution was to divide information into the smallest possible chunks, or “bits” (binary digits). The message is converted into a code made of 0s and 1s—every 0 is a low voltage and every 1 is a high voltage. In creating this code, Shannon drew on binary mathematics, the idea that figures can be represented by just 0s and 1s, which had been developed by Gottfried Leibniz.
Although Shannon was not the first to send information digitally, he fine-tuned the technique. For him, it was not simply about solving the technical problems of transmitting information efficiently. By showing that information could be expressed as binary digits, he launched the theory of information—with implications stretching into every field of science, and into every home or office with a computer.
Shannon demonstrates Theseus, his electromechanical “mouse,” which used a “brain” of telephone relays to find its way around a maze.
See also: Calculus • Binary numbers • Boolean algebra
IN CONTEXT
KEY FIGURE
Michael Gurevitch (1930–2008)
FIELD
Number theory
BEFORE
1929 Hungarian writer Frigyes Karinthy coins the phrase “six degrees of separation.”
AFTER
1967 American sociologist Stanley Milgram designs a “small world experiment” to investigate people’s degrees of separation and connectedness.
1979 Manfred Kochen of IBM and Ithiel de Sola Pool at MIT publish a mathematical analysis of social networks.
1998 In the US, sociologist Duncan J. Watts and mathematician Steven Strogatz produce the Watts–Strogatz random graph model to measure connectedness.
Networks are used to model relationships between objects or people in many disciplines, including computer science, particle physics, economics, cryptography, biology, sociology, and climatology. One type of network is a “six degrees of separation” social network diagram, which measures how connected people are to each other.
In 1961, Michael Gurevitch, an American postgraduate student, published a landmark study of the nature of social networks. In 1967, Stanley Milgram studied how many intermediate acquaintance links were needed to connect strangers in the US. He had people in Nebraska send a letter intended to eventually reach a specific (random) person in Massachusetts. Each recipient then sent the letter on to a person they knew to get it closer to its target destination. Milgram studied how many people each of the letters went through to reach their targets. On average, the letters that reached the target needed six intermediaries.
This “small world theory” predated Milgram. In a 1929 short story Chains, Frigyes Karinthy suggested that people’s average connection-number across the world might be six when the connecting factor is friendship. Karinthy, who was a writer, not a mathematician, coined the phrase “six degrees of separation.” Mathematicians have since tried to model the average degree of separation. Duncan Watts and Steven Strogatz showed that if you have a random network with N nodes, each of which has K links to other nodes, then the average path length between two nodes is ln N divided by ln K (where ln means the natural logarithm). If there are 10 nodes, each with four connections to other nodes, then the average distance between two nodes chosen at random will be ln10⁄ln4 ≈ 1.66.
The six degrees of separation theory shows how any two seemingly unconnected people can be connected in no more than six steps by their friends and acquaintances. This number may decrease with the growth of social media.
Other social networks
In the 1980s, friends of Hungarian mathematician Paul Erdős, who was well known for working collaboratively, coined the term “Erdős number” to indicate his degree of separation from other published mathematicians. Erdős’s coauthors had an Erdős number of 1, anyone who had worked with one of his coauthors had an Erdős number of 2, and so on. This concept captured the public’s imagination following an interview with American actor Kevin Bacon, in which he said he had worked with every actor in Hollywood or with someone who had worked with them. The term “Bacon number” was coined to indicate an actor’s degree of separation from Bacon. In rock music, connections to members of the heavy metal group Black Sabbath are indicated by the “Sabbath number.” To filter out the truly well-connected, there is the Erdős-Bacon-Sabbath number (the sum of someone’s Erdős, Bacon, and Sabbath numbers). Only a few individuals have single-digit EBS numbers.
In 2008, Microsoft conducted research to show that everyone on Earth is separated from every other person by only 6.6 people on average. As social media brings us ever closer, this number may reduce even further.
It is my hope that Six Degrees [a philanthropic project] will… [bring] a social conscience to social networking.
Kevin Bacon
See also: Logarithms • Graph theory • Topology • The birth of modern statistics • The Turing machine • Soc
ial mathematics • Cryptography
IN CONTEXT
KEY FIGURE
Edward Lorenz (1917–2008)
FIELD
Probability
BEFORE
1814 Pierre-Simon Laplace ponders the consequences of a deterministic universe where knowing all present conditions can be used to predict the future for all eternity.
1890 Henri Poincaré shows there is no general solution to the three-body problem, which predicts the motion of three celestial bodies kept in contact by gravity. Mostly, the bodies do not move in rhythmic, repeating patterns.
AFTER
1975 Benoit Mandelbrot uses computer graphics to create more complex fractals (shapes that self-repeat). The Lorenz attractor, which revealed the butterfly effect, is a fractal.
The idea that a butterfly flapping its wings in one part of the world could alter atmospheric conditions and eventually produce a tornado elsewhere has captured the popular imagination.
In 1972, Edward Lorenz, an American meteorologist and mathematician, delivered a talk titled “Does the flap of a butterfly’s wings in Brazil set off a tornado in Texas?” This was the origin of the term “butterfly effect,” which refers to the idea that a tiny change in atmospheric conditions (which could be caused by anything, not just a butterfly) is enough to alter weather patterns somewhere else in the future. If the butterfly had not made its small contribution to the initial conditions, then the tornado or other weather event would not have occurred at all, or would have struck some place other than Texas.