Alan Turing

his life

overview

Alan Turing was a British pioneering computer scientist, mathematician, logician, cryptanalyst and theoretical biologist. He was highly influential in the development of computer science, providing a formalisation of the concepts of algorithm and computation with the Turing Machine , which can be considered a model of a general purpose computer. Turing is widely considered to be the father of theoretical computer science and artificial intelligence.

During the second world war, Turing worked for the British code breaking centre he devised a method for breaking German ciphers, it was an electromagnetically machine that could find settings for the Enigma machine.

Early life

Alan Turing was born at Paddington, London. His father, Julius Mathison Turing, was a British member of the Indian Civil Service and he was often abroad. Alan's mother, Ethel Sara Stoney, was the daughter of the chief engineer of the Madras railways and Alan's parents had met and married in India. When Alan was about one year old his mother re-joined her husband in India, leaving Alan in England with friends of the family. Alan was sent to school but did not seem to be obtaining any benefit so he was removed from the school after a few months.

Next he was sent to Hazlehurst Preparatory School where he seemed to be an 'average to good' pupil in most subjects but was greatly taken up with following his own ideas. He became interested in chess while at this school and he also joined the debating society. He completed his Common Entrance Examination in 1926 and then went to Sherborne School. Now 1926 was the year of the general strike and when the strike was in progress Turing cycled 60 miles to the school from his home, not too demanding a task for Turing who later was to become a fine athlete of almost Olympic standard. He found it very difficult to fit into what was expected at this public school, yet his mother had been so determined that he should have a public school education. Many of the most original thinkers have found conventional schooling an almost incomprehensible process and this seems to have been the case for Turing. His genius drove him in his own directions rather than those required by his teachers.

He was criticised for his handwriting, struggled at English, and even in mathematics he was too interested with his own ideas to produce solutions to problems using the methods taught by his teachers. Despite producing unconventional answers, Turing did win almost every possible mathematics prize while at Sherborne. In chemistry, a subject which had interested him from a very early age, he carried out experiments following his own agenda which did not please his teacher.


An event which was to greatly affect Turing throughout his life took place in 1928. He formed a close friendship with Christopher Morcom, a pupil in the year above him at school, and the two worked together on scientific ideas. Perhaps for the first time Turing was able to find someone with whom he could share his thoughts and ideas. However Morcom died in February 1930 and the experience was a shattering one to Turing. He had a premonition of Morcom's death at the very instant that he was taken ill and felt that this was something beyond what science could explain. He wrote later "It is not difficult to explain these things away - but, I wonder!"

Despite the difficult school years, Turing entered King's College, Cambridge, in 1931 to study mathematics. This was not achieved without difficulty. Turing sat the scholarship examinations in 1929 and won an exhibition, but not a scholarship. Not satisfied with this performance, he took the examinations again in the following year, this time winning a scholarship. In many ways Cambridge was a much easier place for unconventional people like Turing than school had been. He was now much more able to explore his own ideas and he read Russell's Introduction to mathematical philosophy in 1933. At about the same time he read von Neumann's 1932 text on quantum mechanics, a subject he returned to a number of times throughout his life.


The year 1933 saw the beginnings of Turing's interest in mathematical logic. He read a paper to the Moral Science Club at Cambridge in December of that year of which the following minute was recorded "A M Turing read a paper on "Mathematics and logic". He suggested that a purely logistic view of mathematics was inadequate; and that mathematical propositions possessed a variety of interpretations of which the logistic was merely one."


durring the war and adulthood

Of course 1933 was also the year of Hitler's rise in Germany and of an anti-war movement in Britain. Turing joined the anti-war movement but he did not drift towards Marxism, nor pacifism, as happened to many.

Turing graduated in 1934 then, in the spring of 1935, he attended Max Newman's advanced course on the foundations of mathematics. This course studied Gödel's incompleteness results and Hilbert's question on decidability. In one sense 'decidability' was a simple question, namely given a mathematical proposition could one find an algorithm which would decide if the proposition was true of false. For many propositions it was easy to find such an algorithm. The real difficulty arose in proving that for certain propositions no such algorithm existed. When given an algorithm to solve a problem it was clear that it was indeed an algorithm, yet there was no definition of an algorithm which was rigorous enough to allow one to prove that none existed. Turing began to work on these ideas.

Turing was elected a fellow of King's College, Cambridge, in 1935 for a dissertation On the Gaussian error function which proved fundamental results on the probability theory, namely the central limit theorem. Although the central limit theorem had recently been discovered, Turing was not aware of this and discovered it independently. In 1936 Turing was a Smith's Prizeman.


Turing's achievements at Cambridge had been on account of his work in probability theory. However, he had been working on the decidability questions since attending Newman's course. In 1936 he published On Computable Numbers, with an application to the Entscheidungsproblem. It is in this paper that Turing introduced an abstract machine, now called a "Turing machine", which 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.

The Turing machine could write a symbol on the tape, or delete a symbol from the tape. Turing wrote

Some of the symbols written down will form the sequences of figures which is the decimal of the real number which is being computed. The others are just rough notes to "assist the memory". It will only be these rough notes which will be liable to erasure.

He defined a computable number as real number whose decimal expansion could be produced by a Turing machine starting with a blank tape. He showed that π was computable, but since only countably many real numbers are computable, most real numbers are not computable. He then described a number which is not computable and remarks that this seems to be a paradox since he appears to have described infinite terms, a number which cannot be described in finite terms. However, Turing understood the source of the apparent paradox. It is impossible to decide (using another Turing machine) whether a Turing machine with a given table of instructions will output an infinite sequence of numbers.


Although this paper contains ideas which have proved of fundamental importance to mathematics and to computer science ever since it appeared, publishing it in the Proceedings of the London Mathematical Society did not prove easy. The reason was that Alonzo church published An unsolvable problem in elementary number theory in the American Journal of Mathematics in 1936 which also proves that there is no decision procedure for arithmetic. Turing's approach is very different from that of church but Newman had to argue the case for publication of Turing's paper before the London mathematical society would publish it. Turing's revised paper contains a reference to church's results and the paper, first completed in April 1936, was revised in this way in August 1936 and it appeared in print in 1937.


A good feature of the resulting discussions with Church was that Turing became a graduate student at Princeton University in 1936. At Princeton, Turing undertook research under Church's supervision and he returned to England in 1938, having been back in England for the summer vacation in 1937 when he first met Wittgenstein . the major publication which came out of his work at Princeton was Systems of Logic Based on Ordinals which was published in 1939. Newman writes in [13]:-

This paper is full of interesting suggestions and ideas. ... [It] throws much light on Turing's views on the place of intuition in mathematical proof.

Before this paper appeared, Turing published two other papers on rather more conventional mathematical topics. One of these papers discussed methods of approximating Lie group by finite groups. The other paper proves results on extensions of groups, which were first proved by Reinhold Baer, giving a simpler and more unified approach.


Perhaps the most remarkable feature of Turing's work on Turing machines was that he was describing a modern computer before technology had reached the point where construction was a realistic proposition. He had proved in his 1936 paper that a universal Turing machine existed "... which can be made to do the work of any special-purpose machine, that is to say to carry out any piece of computing, if a tape bearing suitable "instructions" is inserted into it."

turing test

The Turing test is a test of a machine's ability to exhibit intelligent behaviour equivalent to, or indistinguishable from, that of a human. Alan Turing proposed that a human evaluator would judge natural language conversations between a human and a machine that is designed to generate human-like responses.

turing machine

A Turing machine is a hypothetical machine thought of by the mathematician Alan Turing in 1936. Despite its simplicity, the machine can simulate ANY computer algorithm, no matter how complicated it is! Above is a very simple representation of a Turing machine.

his death

On 8 June 1954, Turing's housekeeper found him dead. He had died the previous day. A post-mortem examination established that the cause of death was cyanide poisoning. When his body was discovered, an apple lay half-eaten beside his bed, and although the apple was not tested for cyanide, it was speculated that this was the means by which a fatal dose was consumed. An inquest determined that he had committed suicide, and he was cremated at working crematorium on 12 June 1954. Turing's ashes were scattered there, just as his father's had been