Turing machines, coin tosses and internet security

Professor Rod Downey explains why Alan Turing should in fact be most famous for his entirely hypothetical device called the Turing Machine.

8 April 2015

The movie The Imitation Game tells the story – albeit not very accurately – of Alan Turing and the WWII code breakers of Bletchley Park. But Alan Turing should be most famous, says Victoria University of Wellington’s Professor Rod Downey, for an entirely hypothetical device called the Turing Machine, invented to disprove an obscure problem in logic. Rod Downey – winner of the 2011 Hector Medal, a Fellow of the Royal Society of New Zealand and principal investigator on six Marsden Fund grants – explains.

What did you think of the movie?

I did not like the movie very much, for many reasons which I’ve listed in my talk. The good was that the movie correctly placed Turing as a leading figure in winning the WWII and as a one of the great minds of the 20th Century. But the story was so far from reality, slandered really fine people, and was so muddled that I felt disappointed, manipulated and angry. The veracity is akin to that of Braveheart. I don’t know why the movie makers had to reduce everything to such terrible stereotypes such as Turing as a “uber-nerd” and the “four people save the world” story; or have the unnecessary spy subtext, which suggests that Turing was some kind of traitor and coward.

What is a Turing Machine?

A Turing Machine is an abstract “paper” model of computation of an imaginary device which might be able to simulate human decision procedures. Arguably, this is an abstract device capable of performing any “algorithmic process”. With hindsight, it is viewed as the conceptual basis for computers, and with it you can explore what’s possible for computers. Researchers have now been working in computability theory for 70 years. Computers are ubiquitous in modern life, so a classic solution to an obscure problem in logic could be one of the most important discoveries for mankind.

Do you work in the same areas as Alan Turing?

All of my work has related to computation, answering questions like ‘what is possible on a machine?’, ‘how fast can we do it?,’ and generally understanding computation.

For example, I co-invented an area called parameterized complexity. This is a sub-area of complexity theory which seeks to understand how quickly you can perform computational tasks. This is implicit in Alan Turing’s work. There are computational tasks that we think cannot be done quickly in their full form: trying all possibilities it would take far too long on any computer ever. What Mike Fellows and I did was develop a complexity theory to exploit the structure of the data coming in. For example, if you are working out the best way to deliver beer around the city, then it makes a difference if the city is flat.

I also look at algorithmic randomness, which you can imagine by thinking about flipping a coin. If you tossed a coin 100 times and got 100 heads, that would seem suspicious in spite of the fact that this outcome is as likely as one you would actually get. We can reconcile this by giving meaning to the concept of a random string of coin tosses by using computation. Suppose we had an algorithm which could tell us what to bet on for the next coin toss. If a sequence was random, then surely no machine could bet and make money in the long run. There is a whole mathematical theory around this.

How is it useful to know when something is random?

Use of random and “pseudo-random” sequences are everywhere in mathematics, statistics and computer science. One example relates to data compression because things that are random turn out to be algorithmically incompressible. If you are sending a data stream of coin tosses, and you know that every second one is going to be tails, then you can save half the information by not sending every second one. So we can use regularities to compress info. If something is truly random then the only way to send the pattern is by sending itself. Understanding how compression works is essential for internet transmission, and information theory.

Randomness can also be used to help algorithms to solve problems. For example, there are particular equations that are always zero, whatever numbers are used, called identity polynomials. An example in two variables would be xy-yx which is always 0 no matter what x or y is. Amazingly, many many computational tasks can be turned into polynomial identity testing (PIT), to see whether an equation is zero in disguise. If you put in random numbers for the variables, and get an answer of zero, then the equation is almost certainly an identity polynomial. If it is non-zero then it is definitely not. So this is a “randomised” algorithm for PIT, but we have no idea if there is an efficient non-randomised one, and this is a big problem in computer science.

What sort of problems would efficient non-random polynomial identity testing help with?

One example would be a road map between lots of cities, and trying to decide whether you can get drive through all of them without repetition of a city. This is extremely hard and the only way we know how to solve this is to try all the possibilities. If you had 100,000 cities, then you’d be trying 2^100,000 possibilities. That’s more than the number of atoms in the universe. If we had an efficient way of doing it, the number of possibilities might be a polynomial in 100, 000 like 100,000² instead. This is the famous P vs NP problem, and if there was an efficient way of doing this, the implications would be huge – there would be no internet security, for example. But more importantly our life would be revolutionised. There is a prize called the Clay prize offering a million US dollars to anyone solving this problem.

Do you think the P vs NP problem will ever be solved?

There was a leading 19th century mathematician called David Hilbert who, like most mathematicians of his generation, believed that all mathematics was decidable – that you could build a machine to discover everything, including what was provable and what was not. It was through tackling that decision problem that Turing came up with his model for the Turing Machine, as a formal model of a decision procedure. But Turing’s Machine, and work by others, showed that is not possible. So perhaps our intuition is not so good. Perhaps someone will amaze us all and revolutionise life by showing P=NP. The Japanese have a major science challenge to decide this.

Problems can take very long time to solve. Recently a problem called the Kepler Conjecture, which has been around for 400 years, was solved. It basically proves that the most efficient way to stack oranges is that way that it is always done.

We can already use PIT to solve whether it’s possible to go through a limited number of cities, say 50, without going back. We can convert that problem into a bunch of polynomials and find a quick way of doing it. We’re constantly having this battle with this complexity of the world. But you don’t say that beer can’t be delivered because it can’t be done as efficiently as possible. You just do it approximately. This is similar to what Alan Turing and all the people at Bletchley Park did during the war. They found ways of cutting down the number of possibilities they were dealing with. You say, if I can’t solve this problem, can I do this other one?

- Lynley Hargreaves, Sciblogs, 1 April 2015