Alan Turing’s 100th Birthday today

Alan Turing is not as well known as Albert Einstein, yet he arguably had a greater impact on the 20^th Century and was no less a genius. Turing was not only one of the great minds of the 20^th Century but one of the great minds in Western philosophy. In fact, in January, Nature called him “one of the top scientific minds of all time”. He literally invented the modern computer in his head in the 1930s as a thought experiment, whilst simultaneously solving one of the great mathematical problems of his age: the so-called ‘halting problem’. I’ve described this in a previous post (Jan. 2008) whilst reviewing Gregory Chaitin’s book, Thinking about Godel and Turing, but the occasion warrants some repetition.

The 2 June 2012 edition of New Scientist had a feature on Turing by John Graham-Cumming, and it covers in greater detail and erudition anything I can write here. For the public at large, Turing is probably best known for his role at Bletchley Park, in the 2^nd World War, deciphering the Enigma code used by German U-boats. Turing’s contribution remained ‘classified’ until after his death, though, according to Wikipedia, he received an OBE ‘for his work at the Foreign Office’. Turing worked with Gordon Welchman on the Bombe, a machine they designed to run ‘cribs’ to decipher the enigma code. And, with mathematician Bill Tutte, he also developed a method to decode the Tunny cipher, which was used for high-level messages in Hitler’s command.

Turing also developed a ‘portable’ code called ‘Delilah’, which was unique in that it depended on clock-arithmetic, making it very difficult to decode compared to other ciphers. According to Graham-Cumming, the details of this have only recently been declassified.

Turing also became fascinated with mathematics in nature in his childhood, like the recurrence of Fibonacci sequences in spiral patterns in daisy petals and sunflower heads. In 1952 he published a paper on “The chemical basis of morphogenesis”, whereby ‘…specific chemical reactions were responsible for the irregular spots and patches on the skin of animals like leopards or cows, and the ridges inside the roof of the mouth.’ He provided a mathematical model (a computer simulation) of 2 chemicals interacting via diffusion and reaction in a chaotic yet repetitive fashion that would result in a variegated pattern. He speculated that this could become manifest as a literal pattern on animal skins if the 2 chemicals either turned on or off specific cells. Again, according to Graham-Cumming, as recently as January this year, researchers at King’s College London demonstrated Turing’s theory ‘…that 2 chemicals control the ridge patterns inside a mouse’s mouth.’

But, in scientific and mathematical circles, Turing is best known for his ‘proof’ of the ‘halting problem’, which is actually very simple to formulate but difficult to prove. Basically, Turing conjured a thought experiment of a machine that could compute an algorithm until it either found an answer or it didn’t, which meant it could run forever (the ‘halting problem’). Turing was able to prove that one could not determine in advance whether the algorithm would stop or not. An example is Goldbach’s conjecture, which can be easily formulated by an algorithm and run on a computer. At present there is no proof of the Goldbach conjecture but it has been derived by computers up to 100 trillion or 10¹⁴. Obviously, if we knew it could stop or not we could determine if it was true or not to infinity. The same is true for Riemann’s hypothesis, probably the most famous unsolved problem in mathematics. Chaitin (mentioned above) has invented a term, Ω (Omega) to provide a probability of Turing’s algorithm stopping. To quote from a previous post:

Chaitin claims that this is his major contribution to mathematics, arising from his invention of the term ‘Ω’ (Omega), though he calls it a discovery, to designate the probability of a programme ‘halting’, otherwise known as the ‘halting probability’.

But it was in conjuring his ‘thought experiment’ that Turing mentally invented what we now call a computer. I expect computers would have been invented without Turing in the same way relativity would have been discovered without Einstein, yet that is not to diminish either man’s genius or singular contribution. Turing’s insight was to imagine a ‘tape’ of infinite length with instructions that not only performed the algorithm but performed actions on the tape itself. It’s what we recognise today as software. Turing realised that this allowed a ‘universal’ machine to exist, now called a ‘universal Turing machine’, because the tape could instruct one machine to do what all possible machines could do. All modern computers are examples of Universal Turing Machines, including the one I’m using to write and post this blog.

One cannot discuss Turing without talking about the circumstances of his death, because it was a tragedy comparable to the deaths of Socrates and Lavoisier. Turing was persecuted for being a homosexual after he went to the Police to report a burglary. He was given a choice of imprisonment or ‘medical castration’ by hormone treatment, which he accepted. In 1954, at the relatively young age of 41, he committed suicide and the world lost a visionary, a genius and a truly great mind. John Graham-Cumming, the author of the 5 page feature in New Scientist, successfully campaigned for an official apology for Turing from the UK government in 2009. Given the current debate about gay marriage, it is apposite to remember the injustice that was done just over half a century ago to one of the greatest minds of all time. I’ve no doubt that there are many people who believe that Turing could have been ‘cured', such is the ignorance that still pervades many of the world’s societies, and is often promulgated by conservative religious groups, who have a peculiarly backward and anachronistic view of the world. Turing was ahead of his time in many ways, but in one way, tragically.

Addendum: For more detailed information, there is the Wiki site linked above, and Andrew Hodges dedicated Site. The Stanford Encyclopedia of Philosophy gives a good account of Turing’s seminal work in artificial intelligence. Andrew Hodges gives a good account of his untimely attitude to being openly homosexual and an insight into his modest character. There is a very strong sense of an extraordinary visionary intellect who was a victim of prejudice.