Out Spotlight

Today’s Out Spotlight is a mathematical genius, a code breaker and the father of computer science and the modern digital computer.  Today’s Out Spotlight is Alan Turing.

British mathematician Alan Turing (1912-1954) masterminded cracking the German Enigma code during WW II, thus helping to shorten the war. He is also considered the father of computer science and the modern digital computer, with his invention of the Turing Machine (1936). His work continues to influence the field of artificial intelligence and the application of computer techniques in understanding biological forms and systems. He was a mathematical genius, and he was also homosexual.

Julius Mathison Turing,  a member of the Indian Civil Service  and his wife Ethel Sara Stoney, daughter of Edward Waller Stoney, chief engineer of the Madras Railways, wanted their children to be brought up in England, so they returned to Maida Vale, London, where  Alan Turing was born on June 23. 1912.  He had an older brother, John. His father's civil service commission was still active, and during his childhood  his parents travelled between Hastings, England  and India, leaving their two sons to stay with a retired Army couple. Very early in life, Turing showed signs of the genius he was later to display prominently.

His parents enrolled him at St Michael's, a day school at 20 Charles Road, St Leonards-on-Sea, at the age of six. The headmistress recognized his talent early on, as did many of his subsequent educators. In 1926, at the age of 14, he went on to Sherborne School, a famous independent school in the market town of Sherborne in Dorset. His first day of term coincided with the 1926 General Strike in Britain, but so determined was he to attend his first day that he rode his bicycle unaccompanied more than 60 miles (97 km) from Southampton to school, stopping overnight at an inn.

Turing's natural inclination toward mathematics and science did not earn him respect with some of the teachers at Sherborne, whose definition of education placed more emphasis on the classics. His headmaster wrote to his parents: "I hope he will not fall between two stools. If he is to stay at public school, he must aim at becoming educated. If he is to be solely a Scientific Specialist, he is wasting his time at a public school". Despite this, Turing continued to show remarkable ability in the studies he loved, solving advanced problems in 1927 without having even studied elementary calculus. In 1928, aged 16, Turing encountered Albert Einstein's work; not only did he grasp it, but he extrapolated Einstein's questioning of Newton's laws of motion from a text in which this was never made explicit.

While at Sherborne, the sixteen-year-old  fell in love with an older male schoolmate, Christopher Morcom, who died unexpectedly of bovine tuberculosis at the age of nineteen. Socially awkward, Turing exhibited some symptoms of the autistic spectrum, and Morcom had brought him out of his shell. Turing's religious faith was shattered by Morcom's death and he became an atheist.. Grief stricken following, he spent the next few years studying the question of how the human mind might survive death – Morcom's mind in particular. He adopted the conviction that all phenomena, including the workings of the human brain, must be materialistic,  but he still believed in the survival of the spirit after death.  This research led to the study of quantum-mechanical theory and ultimately to the concept of thinking machines.

After Sherborne, Turing went to study at King's College, Cambridge. He was an undergraduate there from 1931 to 1934, graduating with first-class honors in Mathematics. In 1935, at the young age of 22, he was elected a fellow at King's on the strength of a dissertation in which he proved the central limit theorem, despite the fact that he had failed to find out that it had already been proved in 1922 by Jarl Waldemar Lindeberg.

In 1928, German mathematician David Hilbert had called attention to the Entscheidungsproblem (decision problem). In his momentous paper "On Computable Numbers, with an Application to the Entscheidungsproblem" (submitted on 28 May 1936 and delivered 12 November), Turing reformulated Kurt Gödel's 1931 results on the limits of proof and computation, replacing Gödel's universal arithmetic-based formal language with what became known as Turing machines, formal and simple hypothetical devices. He proved that some such machine would be capable of performing any conceivable mathematical computation if it were representable as an algorithm. He went on to prove that there was no solution to the Entscheidungsproblem by first showing that the halting problem for Turing machines is undecidable: in general, it is not possible to decide algorithmically, whether a given Turing machine will ever halt.

While his proof was published shortly after Alonzo Church's equivalent proof in respect of his lambda calculus, Turing was unaware of Church's work at the time that he developed it. Turing's approach was considerably more accessible and intuitive than Church's. It was also novel in its notion of a 'Universal Machine' (now known as a Universal Turing machine), with the idea that such a machine could perform the tasks of any other machine, or in other words, is provably capable of computing anything that is computable. Turing machines are to this day a central object of study in theory of computation. In his memoirs Turing wrote that he was disappointed about the reception of this 1936 paper, which also introduced the notion of definable numbers, and that only two people had reacted – these being Heinrich Scholz and Richard Bevan Braithwaite.

From September 1936 to July 1938 he spent most of his time at the Institute for Advanced Study, Princeton, New Jersey, studying under Alonzo Church. In addition to his purely mathematical work, he studied cryptology and also built three of four stages of an electro-mechanical binary multiplier.  In June 1938 he obtained his PhD from Princeton University; his dissertation (Systems of Logic Based on Ordinals) introduced the concept of ordinal logic and the notion of relative computing, where Turing machines are augmented with so-called oracles, allowing a study of problems that cannot be solved by a Turing machine.

Back in Cambridge, he attended lectures by Ludwig Wittgenstein about the foundations of mathematics. The two argued and disagreed, with Turing defending formalism and Wittgenstein arguing that mathematics does not discover any absolute truths but rather invents them.  He also started to work part-time with the Government Code and Cypher School (GCCS).

During the Second World War, Turing was a leading participant in the breaking of German ciphers at Bletchley Park. The historian and wartime codebreaker Asa Briggs has said: “You needed exceptional talent, you needed genius at Bletchley and Turing's was that genius.”

From September 1938, Turing had been working part-time with the Government Code and Cypher School (GCCS), the British code breaking organization. He concentrated on Cryptanalysis of the Enigma, with Dilly Knox, a senior GCCS codebreaker.  Soon after the July 1939 Warsaw meeting at which the Polish Cipher Bureau had provided the British and French with the details of the wiring of Enigma rotors and their method of decrypting Enigma messages, Turing and Knox started to work on a less fragile approach to the problem. The Polish method relied on an insecure indicator procedure that the Germans were likely to change, which they did in May 1940. Turing's approach was more general, using crib-based decryption for which he produced the initial functional specification of the bomb.

On 4 September 1939, the day after the UK declared war on Germany, Turing reported to Bletchley Park, the wartime station of GCCS.  Specifying the bomb was the first of five major cryptanalytical advances that Turing made during the war. The others were: deducing the indicator procedure used by the German navy; developing a statistical procedure for making much more efficient use of the bombes dubbed Banburismus; developing a procedure for working out the cam settings of the wheels of the Lorenz SZ 40/42 (Tunny) dubbed Turingery and, towards the end of the war, the development of a portable secure voice scrambler at Hanslope Park that was codenamed Delilah.

By using statistical techniques to optimize the trial of different possibilities in the code breaking process, Turing made an innovative contribution to the subject. He wrote two papers discussing mathematical approaches which were entitled Report on the applications of probability to cryptography and Paper on statistics of repetitions which were of such value to GCCS and its successor GCHQ, that they were not released to the UK National Archives until April 2012, shortly before the centenary of his birth. A GCHQ mathematician said at the time that the fact that the contents had been restricted for some 70 years demonstrated their importance.

Turing had something of a reputation for eccentricity at Bletchley Park. He was known to his colleagues as 'Prof' and his Treatise on Enigma was known as 'The Prof's Book'.  While working at Bletchley, Turing, a talented long-distance runner, occasionally ran the 40 miles (64 km) to London when he was needed for high-level meetings, and he was capable of world-class marathon standards.

In 1945, Turing was awarded the OBE for his wartime services, but his work remained secret for many years.

Within weeks of arriving at Bletchley Park, Turing had specified an electromechanical machine that could help break Enigma more effectively than the Polish bomba kryptologiczna, from which its name was derived. The bombe, with an enhancement suggested by mathematician Gordon Welchman, became one of the primary tools, and the major automated one, used to attack Enigma-enciphered messages.

The bombe searched for possible correct settings used for an Enigma message (i.e. rotor order, rotor settings and plugboard settings), using a suitable crib: a fragment of probable plaintext. For each possible setting of the rotors (which had of the order of 1019 states, or 1022 for the four-rotor U-boat variant), the bombe performed a chain of logical deductions based on the crib, implemented electrically. The bombe detected when a contradiction had occurred, and ruled out that setting, moving on to the next. Most of the possible settings would cause contradictions and be discarded, leaving only a few to be investigated in detail. The first bombe was installed on 18 March 1940. More than two hundred bombes were in operation by the end of the war.

Turing decided to tackle the particularly difficult problem of German naval Enigma "because no one else was doing anything about it and I could have it to myself". In December 1939, Turing solved the essential part of the naval indicator system, which was more complex than the indicator systems used by the other services. That same night he also conceived of the idea of Banburismus, a sequential statistical technique (what Abraham Wald later called sequential analysis) to assist in breaking naval Enigma, "though I was not sure that it would work in practice, and was not in fact sure until some days had actually broken". For this he invented a measure of weight of evidence that he called the Ban. Banburismus could rule out certain sequences of the Enigma rotors, substantially reducing the time needed to test settings on the bombes.

In 1941, Turing proposed marriage to Hut 8 co-worker Joan Clarke, a fellow mathematician and cryptanalyst, but their engagement was short-lived. After admitting his homosexuality to his fiancée, who was reportedly "unfazed" by the revelation, Turing decided that he could not go through with the marriage.

Turing travelled to the United States in November 1942 and worked with U.S. Navy cryptanalysts on Naval Enigma and bombe construction in Washington, visiting their Computing Machine Laboratory at Dayton, Ohio. His reaction to the American Bombe design was far from enthusiastic:

    It seems a pity for them to go out of their way to build a machine to do all this stopping if it is not necessary. I am now converted to the extent of thinking that starting from scratch on the design of a Bombe, this method is about as good as our own. The American Bombe program was to produce 336 Bombes, one for each wheel order. I used to smile inwardly at the conception of test (of commutators) can hardly be considered conclusive as they were not testing for the bounce with electronic stop finding devices.

During this trip, he also assisted at Bell Labs with the development of secure speech devices.

He returned to Bletchley Park in March 1943. During his absence, Hugh Alexander had officially assumed the position of head of Hut 8, although Alexander had been de facto head for some time—Turing having little interest in the day-to-day running of the section. Turing became a general consultant for cryptanalysis at Bletchley Park.

Alexander wrote as follows about his contribution:

    There should be no question in anyone's mind that Turing's work was the biggest factor in Hut 8's success. In the early days he was the only cryptographer who thought the problem worth tackling and not only was he primarily responsible for the main theoretical work within the Hut but he also shared with Welchman and Keen the chief credit for the invention of the Bombe. It is always difficult to say that anyone is absolutely indispensable but if anyone was indispensable to Hut 8 it was Turing. The pioneer's work always tends to be forgotten when experience and routine later make everything seem easy and many of us in Hut 8 felt that the magnitude of Turing's contribution was never fully realized by the outside world.

In July 1942, Turing devised a technique termed Turingery (or jokingly Turingismus) for use against the Lorenz cipher messages produced by the Germans' new Geheimschreiber (secret writer) machine. This was a teleprinter rotor cipher attachment codenamed Tunny at Bletchley Park. Turingery was a method of wheel-breaking, i.e. a procedure for working out the cam settings of Tunny's wheels. He also introduced the Tunny team to Tommy Flowers who, under the guidance of Max Newman, went on to build the Colossus computer, the world's first programmable digital electronic computer, which replaced a simpler prior machine (the Heath Robinson), and whose superior speed allowed the statistical decryption techniques to be applied usefully to the messages. Some have mistakenly said that Turing was a key figure in the design of the Colossus computer. Turingery and the statistical approach of Banburismus undoubtedly fed into the thinking about cryptanalysis of the Lorenz cipher, but he was not directly involved in the Colossus development.

 Following his work at Bell Labs in the US, Turing pursued the idea of electronic enciphering of speech in the telephone system, and in the latter part of the war, he moved to work for the Secret Service's Radio Security Service (later HMGCC) at Hanslope Park. There he further developed his knowledge of electronics with the assistance of engineer Donald Bayley. Together they undertook the design and construction of a portable secure voice communications machine codenamed Delilah. It was intended for different applications, lacking capability for use with long-distance radio transmissions, and in any case, Delilah was completed too late to be used during the war. Though Turing demonstrated it to officials by encrypting and decrypting a recording of a Winston Churchill speech, Delilah was not adopted for use. Turing also consulted with Bell Labs on the development of SIGSALY, a secure voice system that was used in the later years of the war.

From 1945 to 1947 Turing lived in Richmond, London while he worked on the design of the ACE (Automatic Computing Engine) at the National Physical Laboratory (NPL). He presented a paper in  February 1946, which was the first detailed design of a stored-program computer. Von Neumann's incomplete First Draft of a Report on the EDVAC had predated Turing's paper, but it was much less detailed and, according to John R. Womersley, Superintendent of the NPL Mathematics Division, it "contains a number of ideas which are Dr. Turing’s own” Although ACE was a feasible design, the secrecy surrounding the wartime work at Bletchley Park led to delays in starting the project and he became disillusioned. In late 1947 he returned to Cambridge for a sabbatical year. While he was at Cambridge, the Pilot ACE was built in his absence. It executed its first program on May 10, 1950. Although Turing's ACE was never built, a number of computers around the world owe a lot to it, for example, the English Electric DEUCE and the American Bendix G-15.

According to the memoirs of the German computer pioneer Heinz Billing from the Max Planck Institute for Physics, published by Genscher, Düsseldorf (1997), there was a meeting between Alan Turing and Konrad Zuse. It took place in Göttingen in 1947. The interrogation had the form of a colloquium. Participants were Womersley, Turing, Porter from England and a few German researchers like Zuse, Walther, and Billing.

In 1948, he was appointed Reader in the Mathematics Department at the University of Manchester. In 1949, he became Deputy Director of the Computing Laboratory there, working on software for one of the earliest stored-program computers—the Manchester Mark 1. During this time he continued to do more abstract work, and in "Computing machinery and intelligence" (Mind, October 1950), Turing addressed the problem of artificial intelligence, and proposed an experiment which became known as the Turing test, an attempt to define a standard for a machine to be called "intelligent". The idea was that a computer could be said to "think" if a human interrogator could not tell it apart, through conversation, from a human being. In the paper, Turing suggested that rather than building a program to simulate the adult mind, it would be better rather to produce a simpler one to simulate a child's mind and then to subject it to a course of education. A reversed form of the Turing test is widely used on the Internet; the CAPTCHA test is intended to determine whether the user is a human or a computer.

In 1948, Turing, working with his former undergraduate colleague, D. G. Champernowne, began writing a chess program for a computer that did not yet exist. In 1952, lacking a computer powerful enough to execute the program, Turing played a game in which he simulated the computer, taking about half an hour per move. The game was recorded. The program lost to Turing's colleague Alick Glennie, although it is said that it won a game against Champernowne's wife.

Shortly after the he became a professor at Cambridge University, he fell in love with a student, Neville Johnson, and was surprisingly open about his sexual orientation, given the mores of the time. In 1952 a young man from Manchester attempted to blackmail him for his homosexuality, leading Turing to go to the police to report the attempt at extortion. Instead of deciding to prosecute the extortionist, they arrested Turing on twelve counts of gross indecency. He would not deny the charges, taking the stance that he had done nothing wrong. The court disagreed, and Turing's security clearances were withdrawn, putting an end to his brilliant work. To avoid a prison term, Turing agreed to be subjected to experimental hormone treatments designed to curb his homosexual desires. Massive doses of estrogen caused him to grow breasts and become chemically depressed. His life thus ruined, he committed suicide in 1954, by ingesting a cyanide injected apple two weeks before his 42nd birthday. In 2009 the British government issued a formal apology for the way Turing was treated after WW II.

This year will be the centennial celebration of Turing’s life and scientific impact, with a number of major events taking place throughout the year. Most of these will be linked to places with special significance in Turing’s life, such as Cambridge, Manchester and Bletchley Park.

 A blue plaque outside the 4-star luxury Colonnade Hotel in London indicates where Turing was born one hundred years ago, on June 23, 1912, when the hotel served as a hospital.