What did Turing do for us?
This year is a special year for me, and for many other mathematicians like me. This year we shall be celebrating 'Turing Year'; that is the centenary of the birth of one of our greatest 20th century mathematicians, Alan Turing. There are many special events planned for this year to mark the occasion, with even the Royal Mail announcing a postage stamp of Turing for their 'Britons of Distinction' series.
And it won't just be mathematicians that will be celebrating, as Turing is one of the rare figures in mathematics that has crossed over into the public consciousness. Yet many people may still be unaware why we consider Turing to be so significant. What did Turing ever do for us?
Alan Turing was a mathematician, cryptographer, and a pioneer of computer science. Today, Turing may best be known for his work at Bletchley Park during World War II, and his part in breaking the German Enigma code. Yet by this time Turing was already well known as a mathematician. As a young man, his idea of a 'Universal Machine', a hypothetical type of computer, resolved one of the most important problems in 20th century mathematics.
The 'Decision Problem', or 'Entscheidungsproblem' in the original German, was initially expressed in 1900 as part of the famous 'Hilbert Problems'- 23 unsolved problems in mathematics, set by David Hilbert as the most important mathematical challenges for the 20th century. In them, Hilbert asked whether we could find a set of 'basic truths' (or 'axioms') from which we could prove all statements in mathematics, without giving any contradictory answers such as 1=0. Hilbert also asked whether there was an algorithm that could determine if a statement was true or false, even if no proof or disproof was known. In other words, Hilbert was asking whether mathematics was 'complete', 'consistent' and 'decidable'.
The first two questions were answered in 1930 by Kurt Gödel who discovered that it was impossible for any set of axioms in arithmetic to be both complete and consistent. This was a major blow for Hilbert's dream. However, the third question, that of whether mathematics was decidable, was still open and would remain so for another six years. So it was, in the Spring of 1935, a young Masters student at King's College, Cambridge, decided to take on the remaining question of decidability.
Alan Turing was born on the 23rd of June 1912. He spent his childhood in Hastings and Sherborne in Dorset, where he attended Sherborne School. Gifted at maths and science, Turing went on to study mathematics at Cambridge. It was there, inspired by the lectures of Max Newman, that Turing decided to take on the Decision Problem.
Turing imagined a hypothetical machine, (now called a 'Turing machine' that would read a tape of symbols, one at a time, then either rewrite or erase the symbol, before then shifting the tape to the left or right. In fact, originally Turing describes a person slavishly performing these operations. He called this person the 'computer'.
Some Turing machines would run forever, some would halt quite quickly, and for others it depended on the input. Turing asked if some method existed that always allowed us to determine whether a computer program and input would eventually halt, or run forever. He proved that a general algorithm to solve this problem, for all possible program and input pairs, cannot exist - making it an example of an undecidable problem. An astounding example that disproved Hilbert's question on decidability.
As it happens, Turing had been beaten to the punch. Unknown to him, the Princeton mathematician Alonzo Church had independently described an equivalent undecidable problem earlier in the year. Yet Turing's halting problem is regarded as the more intuitive and easier to understand. Subsequently, Alan went on to Princeton to study under Church where he gained his PhD. It was then, after returning to Cambridge, that Turing started working part time for the Government Code and Cypher School - the UK's code breakers.
For many years, even before the Second World War, the German military had been using a cipher machine to encrypt their secret message, a machine called Enigma. The Enigma machine was about the size of a typewriter, except instead of having a carriage and paper like a normal typewriter it had a second set of letters that lit up; this was called the lampboard. Typing a message on the keyboard resulted in letters lighting up on the lampboard, so if you pressed 'A' on the keyboard, the letter 'H' might then light up on the lampboard - this was your code!
The Enigma Machine was essentially a simple circuit, connecting a battery to a bulb. Pressing a key on the keyboard would complete a circuit, and illuminate a letter on the lampboard. The standard Enigma Machine had over 150 million million million daily settings, but this is not why Enigma was so hard to break. Inside, Enigma contained three moving parts, called rotors. These rotors would turn after pressing a key, making the wires of the circuit rotate, thus changing the circuit completely. So if you now pressed 'A' for a second time it may not be the same letter as before. Double letters, for example, may not become double letters in the code. It was these rotors that made Enigma so difficult to break. A day after the UK declared war with Germany, Turing reported to Bletchley Park for work on breaking the German cipher.
Turing's contribution to the effort at Bletchley Park was indispensible. Not only did he make the first breakthroughs with the Naval Enigma code, allowing Britain's food and supplies to be shipped across the Atlantic, but, along with Gordon Welchman, designed a machine to break Enigma. This code breaking machine was called the Bombe, a name chosen to honour the earlier Polish code breaking machine called Bomba. The Bombe worked using the mathematical principle of contradiction. Given an Enigma code, the code breakers would try and guess a short phrase, or 'crib', that might appear in the message. They would input this guess into the Bombe and, if this input did not result in a valid Enigma code, it would be rejected. However, if left to continue, all other deductions made by the Bombe Machine were then equally invalid, and so could all be rejected at once as fruit of the poison tree. On a good day, the Bombe machine could find the Enigma setting in 15 minutes. In 1945 Turing received an OBE for his work at Bletchley Park, even though the work remained top secret for another 30 years.
Now working at Manchester University, Turing continued to make significant contributions in computing until his death in 1954. Alan Turing was gay at a time when it was illegal to be gay. So when this was discovered Alan was given the choice of imprisonment or to undergo hormone treatment. Turing chose the unpleasant hormone treatment. He was then treated as a security risk and lost his job consulting for the code breakers at GCHQ. In the end, Turing committed suicide by biting from an apple laced with cyanide. In 2009 the British government made an official public apology for the way Turing was treated after the war. There is currently an e-petition to get Turing a full pardon, representing not just Turing, but all gay men subjected to these laws. You may sign the petition here.
Turing's legacy is huge. We live in a world full of computers, thanks to the work of Alan Turing. There have been many accolades and tributes to Turing since his death. Since 1966 the Turing award has been given annually by the Association for Computing Machinery, widely considered as equivalent to the Nobel Prize for computing. In Manchester's Sackville Park there is a statue of Turing sitting on a bench, titled 'Father of Computer Science'. Before his death, Turing had taken an interest in mathematical biology, investigation the appearance of Fibonacci numbers in plant structures and pattern formation in animal markings. This work is considered seminal in the field, which goes to show the breadth of Turing's genius, and only leaves us to wonder what else he could have achieved.