Alan Mathison Turing (1912 - 1954)

Alan Turing was a British mathematician with stunningly original and pioneering ideas.

He was born in London and attended Cambridge University where he discovered for himself two important breakthroughs in twentieth century mathematics already discovered by others.

He became the chief code cracker in the British war effort against Germany and was eventually to commit suicide.

His life is extraordinary and it is no accident that part of it ended up as the inspiration for a play and a film - Enigma.

Turing’s work was original, but it came to the same conclusions as another mathematician, Church, who worked in America. Church published first, and this caused Turing difficulties (which were overcome) in getting his own paper published.

The amazing thing about Turing’s work was that he was describing a modern computer before technology had reached the point where construction was a realistic proposition. He wanted to actually build such a machine and in Cambridge just before the second World War started, he began work on an analogue mechanical device to investigate the Riemann hypothesis.

Turing was elected a fellow of King’s College, Cambridge for a dissertation On the Gaussian error function which proved fundamental results in probability. This result is known as The central limit theorem and it is as deep as the result that underpins much of modern statistics and statistical analysis.

Again Turing had been pipped to the post, but as usual he derived his version independently.

During the second World War, Turing worked as a cryptographer for the British Foreign Office, at Bletchley Park, where his skills were used in breaking the German Enigma Code.

This was a trial for Turing as the work was collaborative and team based. Nonetheless, a machine called the Bombe was built and this successfully decoded the messages sent by the Luftwaffe via Enigma machines.

The Enigma machines of the German navy were much harder to break but this was exactly the solitary challenge that Turing enjoyed.

Turing’s statistical approach, combined with captured information, ultimately led to the German navy signals being decoded. He was later awarded an OBE for this work.

After the war, Turing joined the National Physical Laboratory, in London, and was asked to build a computer - The Automatic Computing Engine (ACE). Turing completed the design phase, but then the problems started.

One important aspect of his design worried colleagues - the ‘memory’ unit. His proposed ‘storage size’ far outstripped existing resource and engineering capabilities and was considered far too ambitious.

He soon left, back to Cambridge for a short period and then to Manchester University to build another computer. He would not see it finished.

Turing also extended his mathematical work to the study of artificial intelligence and biological forms. In 1950 he proposed in a paper a procedure that came to be called the Turing Test, to determine whether machines could have the ability to “think” like a human, a test still used today in the field of artificial intelligence.

In 1951 Turing was named a Fellow of the Royal Society and in 1952 he began to publish his work on the application of mathematical theory to biological forms. He died in 1954.

Turing’s mathematics

Turing graduated in 1934 and immediately began studying an area of mathematics that would dominate all of his work - the foundations of mathematics. Gödel’s work on ‘decidability’ had made fundamental advances on that of Hilbert and Turing set to work in trying to understand and extend their results.

In one sense the problem is easy: given a mathematical proposition is there a way of deciding if the proposition is true or false. In most cases it was easy - either it could be proved as a theorem, or a counter example could be found. For example, let us consider the following propositions:

The first of these is false, since 15 is a triangular number but it isn’t even. The second is true and we can prove it by factorisation:

n^2-1=(n-1)(n+1)

(Notice that when n=2, the first factor would be 1). The third proposition leaves us in a quandary - we can’t prove it either way, and even after the continued work of many mathematicians, it remains that way. No one has found a proof; no one has proved that only a finite number of such prime occurrences exist.

The question is, can a procedure be found to prove that no solution - either way - exists? The first step was to develop a definition of a procedure that was rigorous enough to allow one to prove that none existed. Turing tackled this deficit.

Turing did this by a very clever invention - a machine. He launched this on the world in a a paper called “On Computable Numbers,” which introduced his virtual machine, a theoretical computing device now known as a Turing Machine.

The concept of this machine, which could theoretically perform any mathematical calculation, was to investigate ‘procedures’ in a systematic and abstract way. Such a machine moved from one state to another using a precise finite set of rules (given by a finite table) and depending on a single symbol it read from a tape.

It worked its way through the input data and its instructions and returned the results of its efforts by its finishing state. But sometimes, Turing discovered, the machine didn’t halt.

Turing had opened the way not only for understanding deep mathematical problems, but he’d invented modern computers as well. Here is the chart of a simple Turing machine to add two numbers,