FTSE 100
Dow Jones

Monday, 14 September 2009

Alan Turing: apologies required

At the risk of incurring wrath from many quarters, I would like to see some apologies from several people regarding Alan Turing. Not in this case from Prime Ministers who have no personal responsibility for Alan Turing's treatment in the 1950's, but from those who have grossly hyped Turing's achievements.

A typical example is this from the Daily Kos:

If the name Alan Turing rings a bell, it's probably because of the Turing Test. But creating the famous Artificial Intelligence mind experiment was only one of Turing's many accomplishments. In WW2, it was Turing who cracked the Nazi code, saving countless lives and bringing the brutal war to an earlier end. He went on to become the father of the computer age. Turing invented the program, what we call software today, and laid the cornerstones for a network that connected defense computers by phone lines that would one day be called the Internet. Today, as you type on your keyboard, populate spreadsheets, and surf the web, you will be working on a modern incarnation of Turing's devices. How was this visionary genius treated by the western civilization he so ably helped preserve and enrich?

Now let's get this straight. Turing was a bright mathematician who achieved much, but was never as pre-eminent as today's writers suggest. As a mathematician working in Computation Theory, which I would classify as a distinct subset of Computer Science, his most notable theoretical achievement was the conception of the class of abstract finite state machine known as the Turing machine, which perhaps bears a resemblance to early computers because of theirsimplicity and use of external storage media, but were in fact far removed from the computers built fifteen years later.

The Turing machine abstraction was in fact no more than an equivalent model to the general recursive functions developed by Kleene and the work on effective procedures by Alonzo Church slightly before Turing. Whilst the Turing machine feels like a computer, they give no further insights into effectiveness of procedures than other methods.

The Entscheidungsproblem, a challenge posed by David Hilbert in 1928, questions whether there is an algorithm that takes as input a description of a formal language and a mathematical statement in the language and produces as outputs whether statement is true or false.

The problem was solved by Turing's supervisor at Princeton, Alonzo Church in 1936 with the concept of "effective calculability" based on his λ calculus and again less than one year later by Turing with his abstract Turing machines. The pair later showed that the two models of computation are equivalent. Turing clearly did outstanding work in the field, but it would be wrong to name his successes without mentioning the work of people such as Church, Gödel, Post, Kleene and even Hilbert.

Turing's war work was also valuable, but again contrary to what might have been gleaned from reports he was not working alone. He ran one of the important codebreaking huts and his expertise in statistical cryptanalysis improved on the work of the Polish Cipher Bureau who had first cracked the Enigma in 1932, but the Enigma "machine" was in fact a family of machines subject to constant improvements, and 10,000 people continued working at Bletchley Park for 3 years after Turing left Hut 8. In the later years of the war the Germans used Enigma machines less for high priority messages, preferring the Tunny sytem using teletype machines. Turing and others worked on this and collectively they designed the Colossus machines built by Post Office Engineers for the purpose.

After the war, Turing worked on the design of early computers, but his efforts at the NPL and later at Manchester, initially based on the Colossus machine built by the Post Office, came after the earlier and more widely published papers of John van Neumann at Princeton who had discerned the need for stored program computing machines while working on the wartime Manhatten project. Now there was a truly great mathematician who made many significant advances in set theory, functional analysis, quantum mechanics, ergodic theory, continuous geometry, economics and game theory, computer science, numerical analysis, hydrodynamics (of explosions) and statistics.

Indeed when Turings' ideas were first presented to the directors of the NPL, the preface acknowledged the advice that had been received from von Neumann. The NPL director, John Womersley, explained the need for a computer and argued that the UK had advantages because it was designed by the users, mathematicians, rather than electrical engineers. As it turned out the American engineers managed to build their designs while Turing's design for the ACE computer was discarded for a simpler design completed after Turing had left for the University of Manchester.

The Manchester Computer Laboratory designed the SSEM and the Manchester/Ferranti Mark I, but contrary to what Turing's web biographies imply, Turing was not involved in their design or construction, although he was one of the first and foremost users. The machines were actually designed and built by electrical engineers, not mathematicians like Turing. Meanwhile the mathematicians at Cambridge, Maurice Wilkes, David Wheeler and others, built EDSAC.

The later treatment of Turing was worse than heinous, but the removal of his security clearance, and bar from working with GCHQ was quite understandable given the legal standing of homosexuality at the time. That is not to say that the law was correct, merely that the law being what it was, the potential for blackmail was clear and the security risks were obvious.

So in summary, Turing was a highly gifted mathematician and deserved to become a Fellow of the Royal Society. One might even call him world class, but let us not get carried away. The British have very few great men in this field. Turing's machines are certainly intriguingly elegant as thought experiments even if cumbersome as anything other than a conceptual abstraction. Turing was a fine mathematician of the first half of the twentieth century, but in the same league as other British mathematicians as G.H. Hardy, Freeman Dyson or Paul Dirac? Not in my view, but that may be just because I have a better grasp of Turing's work.

In Computer Science I would rank him above such illustrious figures and personal favourites as Donald Knuth and Marvin Minsky, but to say that he "invented the algorithm" is nonsense. Numerical analysis, the study of algorithms for the problems of continuous mathematics, has been around since Babylonian times. Turing's solution to the Entscheidungsproblem, involving his notion of "computability" came after his supervisor's equivalent proof using the concept of "effective calculabilty".

And as for the claim that Turing "laid the cornerstones for a network that connected defense computers by phone lines that would one day be called the Internet", all I can say to that is "Bolt, Beranek & Newman".

No comments: