Posts Tagged ‘logic’

The Imitation Game: Part 1

Imitation Game posterToday we had a wonderful event at the Filmhouse cinema in Edinburgh talking about The Maths of the Imitation Game. This is the film which tells the story of mathematician Alan Turing and his work codebreaking at Bletchley Park during the Second World War.

I’m going to admit up front: I liked the film. I’ve met other people who’ve been foaming at the mouth with anger over inaccuracies in the film, both with the historical aspects and also with how Turing was portrayed. I agree that the film isn’t perfect – they had to take a lot of liberties with how things were presented in order to make the story appeal to a mass audience. Events certainly did not happen the way the film depicts. And I do take issue with the film’s insinuation that Turing assisted Soviet spying, and also that Turing would have told classified secrets to a police officer. But I also think the film gets a lot of things right, it tries its best to explain key aspects of the story, and is wonderfully acted, especially by Cumberbatch as Turing.

If nothing else, the film is a great platform to start discussions about the important (theoretical) work that Turing did in his life and the repercussions of that work today. This is what our event at the Filmhouse was all about. We had three speakers talking about different aspects of his work, and I’ll summarise those discussions here. I’ll break it down into three blog posts as there is a lot to say about each one.

First up, Dr John Longley from the School of Informatics talked about Turing’s early work on computability. In our lives we are used to having different machines for different tasks: a toaster that warms your bread, a dishwasher to wash your plates and a blender to mash your food. We wouldn’t expect a single machine to perform all these different tasks. Yet, walk through to your study and you’ll find a machine on which you can do many things: play solitaire, manage your accounts, watch videos, search for prime numbers. Nowadays we aren’t at all surprised that a computer can do so much, but in Turing’s day such a machine was inconceivable. In fact, it was Turing who proposed that such a machine could exist. He had the idea of a ‘universal machine‘ which could emulate the output of any other given machine.

Every machine takes some sort of input, performs a certain task and then gives an output. The toaster’s input is your bread, which is heated according to the settings you’ve told it, and its output is some toasted bread. The Enigma machine takes as input the key presses of letters, it performs an encryption, and it outputs letters forming a coded message. For Turing’s universal machine, the input is a sequence of symbols that provide the instructions for what another simulated machine does and the input to this machine. The output is then the answer that the simulated machine would have provided if you had given it this particular input. This idea that the input may itself comprise a set of instructions was groundbreaking. Today we simply call this kind of input ‘software’.

Turing’s invention of the universal machine was designed to answer a long-standing problem in mathematics: can the answer to every mathematical question be determined mechanically? This was posed by David Hilbert in 1928. When Turing was only 23 years old, he showed that the answer to this question was negative, and he did this by coming up with something called the Halting problem.

Turing's bombe

Will Turing’s machine output the correct Enigma settings, or could it keep searching forever? This is called the Halting problem.

This simply asks: given a particular input to a machine, is it possible to determine whether the machine will ever halt and give an output? For example, in the film the machine (called “Christopher”) that Turing has invented is checking through possible settings of Enigma and everyone is waiting for it to tell them what the correct answer is. Will it ever stop, or will it keep whirring away for ever, stuck in some logical loop that prevents it from finishing? If you pull the plug, how can you be sure that in the next minute it wouldn’t have told you the answer? Turing proved that there is no single algorithm that can decide whether a given arbitrary program will halt for a given input. The halting problem is ‘undecidable’.

The conclusion from his work is that there are some questions in mathematics that are unknowable –  there is no computer program that will ever tell us whether they are true or false. However, this begs the question: is the human mind the same as a computer? Or could a brain do computations, do mathematics, that a machine could not? If so, what makes a brain different from a computer?

This question fascinated Turing and led him to invent The Imitation Game, which gives the film its title. Rather than asking the question “Can machines think?” which is very abstract and hard to pin down, he instead asked whether it was possible for a machine to imitate a human so well that another human could not tell that it was really a machine. In a Turing test, person A can interrogate player B by asking a series of questions. Turing said that if the interrogator decides as often as not that player B is a real person, then the machine has passed the test. Despite predicting that computers would be built to pass the test by the year 2000, it was only in June this year (2014) that a computer was said to have passed the test. This was a computer masquerading as a 13 year old Ukrainian boy, who fooled 33% of a panel of judges over the course of a 5-minute conversation.

What do you think? Could computers come to imitate humans one day? Is it just a case of having more computing power, or is it possible that brains can do things that computers fundamentally cannot?

Many thanks to John Longley for the material on which this blog post is based.

Read The Imitation Game: Part 2 about Turing’s role in codebreaking during World War 2 and moral questions about codebreaking today…