Read more: “Instant Expert: Alan Turing’s legacy“
The ideas of British scientist Alan Turing shaped our world. He laid the foundations for modern computers and the information technology revolution, as well as making far-sighted predictions on artificial intelligence, the brain and even developmental biology. He also led vital codebreaking efforts for the Allies in the second world war. This legacy will be celebrated worldwide on 23 June – the 100th anniversary of his birth.
Understanding why Turing’s achievements matter today begins with the story of how he set out to solve one of his era’s biggest mathematical conundrums – and in the process defined the basis of all computers
Advertisement
The first computer
Up until the second world war, the word “computer” meant a person, often a woman, who did calculations either manually or with the help of a mechanical adding machine. These human computers were an essential part of the industrial revolution and performed often repetitive calculations, such as those necessary for the creation of books of log tables.
But in 1936, Turing, aged just 24, laid the foundations for a new type of computer – one we would still recognise today – and so played a seminal role in the information technology revolution.
Turing did not set out to invent the model for the modern computer, though. He wanted to resolve a conundrum in mathematical logic. In the mid-1930s, he decided to attack the fearsomely named – or “decision problem” – posed by mathematician David Hilbert in 1928.
At the time, mathematics was searching for concrete foundations and Hilbert wanted to know if all mathematical statements (such as 2 + 2 = 4) were “decidable”. In other words: does a step-by-step procedure exist that can determine whether any given statement in mathematics is true or false?
This was a fundamental question for mathematicians. Although it is easy to say with certainty that a statement like 2 + 2 = 4 is true, more complex logical statements are trickier to ascertain. Take the Riemann hypothesis, proposed by Bernhard Riemann in 1859, which makes specific predictions about the distribution of prime numbers among natural numbers. Mathematicians suspect it is true, but they still don’t know for certain.
If Hilbert’s proposed step-by-step procedure could be found, it would mean that, eventually, a machine could be devised to give mathematicians a firm answer to any logical statement they wanted to test. All the big open questions in mathematics could be resolved.
It may not have been apparent then, but what Hilbert was searching for was a computer program. Today we call his proposed step-by-step procedure an “algorithm”. But neither computers nor programs existed in the 1930s – Turing had to define the concept of computation itself in order to tackle the Entscheidungsproblem.
In 1936, Turing published a paper that provided a definitive answer to Hilbert’s question: no procedure exists for determining whether any given mathematical statement is true or false. Moreover, many of the important unresolved questions in mathematics are “undecidable” (). This was good news for human mathematicians, because it meant that they would never be replaced by machines. But with his paper, Turing had achieved more than the resolution of Hilbert’s question. To arrive at his result, he had also come up with the theoretical basis for modern computers.
Before Turing could test Hilbert’s proposal, he needed to define what a step-by-step procedure was, and the sort of device that might perform it. He did not need to build such a machine, but he did need to lay out how it would work hypothetically.
First, he imagined a machine capable of reading symbols from a paper tape. You would feed the paper tape in, and the machine would examine the symbols, then make a decision about what to do next by following a set of internal rules. It could, for example, add two numbers that were written on the tape and print the result further along the tape. This would later come to be known as a Turing machine (see diagram). However, because each individual Turing machine had predefined internal rules – essentially a fixed program – it could not be used to test Hilbert’s question.
Turing realised that it would be possible to make a machine that could initially read a procedure from the tape, and use that to define its internal rules. By doing so, it was programmable, and could perform the same actions of any individual Turing machine, which had fixed internal rules. That flexible device, which we call a universal Turing machine, is a computer.
How so? The procedure written on the tape can be thought of as software. Turing’s universal machine would essentially be loading the software from the tape into itself, just as we do today with a program from a disc or download: one minute your computer is a word processor, the next it is a music player.
Once Turing had this theoretical computer, he could answer the question of what was “computable”. What could a computer do and not do?
To disprove Hilbert’s proposed procedure, Turing needed to find just one logical statement that a computer cannot ascertain is true or false. To do this, he identified a specific question: could a computer examine a program and decide whether it will “stop” or run forever if left unchecked? In other words, could a computer determine whether it was true or false that a program would stop? The answer, he demonstrated, is that it cannot. Hilbert’s procedure therefore did not exist, and the Entscheidungsproblem was resolved. In fact, Turing’s conclusion was that there are infinitely many things a computer cannot do.
While Turing was attacking the decision problem, US mathematician Alonzo Church was taking a pure-mathematics approach to it. Church and Turing published their papers almost simultaneously. Turing’s paper defined the notion of “computable”, whereas Church’s had “effective calculability”. The two are equivalent. This result, the Church-Turing thesis, underlies our concept of the limits of computers and creates a direct link between an esoteric question in mathematical logic and the computer you own.
As computers get ever more advanced, they operate within the same limits that Church and Turing described. Even though modern computers are stunningly powerful compared with the behemoths of the 1940s, they can still only perform the same tasks as a universal Turing machine.
“As computers get ever more advanced, they still operate within the limits Turing described”
