Man of great compute

New Statesman
A WWII enigma machine. Photo: Getty Images

Imagine choosing to undergo chemical castration by oestrogen injection. That was how much Alan Turing didn't want to go to prison in 1952, having been convicted of gross indecency as a practising homosexual. Now imagine being handed this choice by the regime you had saved, almost single-handedly, from the Nazi war machine. Small wonder Turing killed himself two years later.

The Leader of the Commons, Sir George Young, has said he will now reconsider whether the celebrated pioneer of computing deserves to remain under the shadow of the conviction. But he has also said it is hard to see how a pardon can be granted, because there is no precedent. How ironic: thanks to Turing's pioneering mathematical work, we can now prove that it is really hard to do some things, yet issuing a pardon for him is not one of them.

Turing came up with the framework for the modern digital computer in 1937-38. This vision is the basis of every computer ever built, from those assembled at the end of the Second World War to the supercomputers humming away to support the internet. He did even more than that. He also gave us the framework for thinking about the computer's limitations. He showed that it was impossible to say in advance whether a given program would go on for ever, or come to an end and spit out a result.

Subsequent research has shown that this fundamental roadblock is closely related to the question of whether there might be quick solutions to certain "hard" mathematical processes. In this context, hard doesn't mean "quite difficult"; it means there is no known way to solve the problem in a reasonable time.

We now know, for instance, that the console games Pac-Man, Super Mario Bros, Donkey Kong and The Legend of Zelda are all mathematically hard. Thanks to Turing, we have an excuse for all those years of trying and failing to complete them.

We rely on some things being hard. For instance, there is no mathematical routine for finding a large number's "factors" - two numbers that, multiplied together, would give your large number. All you can do is start from two times two and begin the arduous process of finding the factors by trial and error. It is the mathematical hardness of doing this with truly giant numbers (composed of more than 1,000 binary digits) that guarantees the security of financial transactions on the internet.

Hard luck

It's good to know what's hard. When your internet shopping is being despatched, the courier doing the delivery tries to find the most fuel- and time-efficient route - but it knows not to waste effort trying to find a route where the driver will pass each delivery point only once. We know, thanks to Turing's initial work, that this, too, is uncomputable.

As is the map-labelling problem. Fitting words on to a GPS map might seem like a trivial matter, but it is not. Maps that work at varying scales cannot be labelled consistently without the labels overlapping at some scales or being in the wrong place at others.

Google didn't waste resources trying and failing to achieve this. It knew from work that can be traced back to Turing that dynamic digital mapping requires fudges and compromises.

In 2009, Gordon Brown issued an apology for the way Turing was treated in the years following the Second World War. Turing cracked the Nazis' Enigma codes and placed Britain at the centre of the computing revolution. Nonetheless, the prospects for a pardon remain poor.

Clearly, we should add "getting Britain to show appropriate gratitude" to the list of things that are unfathomably hard.

Sign an e-petition to have Alan Turing pardoned at: https://submissions.epetitions.direct.gov.uk/petitions/23526