Computable numbers

Almost simultaneous with his election to a Fellowship was the publication of his first paper, a slight improvement on earlier work by the master mathematician John von Neumann. As it happened, von Neumann arrived in Cambridge shortly afterwards to spend the summer away from his home university of Princeton in America. Turing almost certainly attended his course of lectures; but his main problem now lay in choosing his field of research.

His interest in mathematical logic had been aroused by M.H.A. Newman's lectures in 1935. These included problems posed at the end of the 19th century by the German mathematician David Hilbert. One of these remained unsolved and in 1928 Hilbert himself proposed the Entscheidungs problem - "to find a method for deciding whether or not a given formula is a logical consequence of some other given formulae". (The mathematical details are discussed in references 1 and 2.)

Turing solved the remaining problem and went on to postulate a logical machine that could solve any problem of logic provided it was given a suitable set of instructions. This ran counter to the prevalent belief that different calculating machines were needed for different mathematical problems. Turing showed that it was possible logically, if not physically, to have one machine to do all. The concept was soon to be known as a "Turing machine". Within ten years such machines had, as Candy put it, "descended from the sky to the firm ground of information technology".

Turing's paper was called "On Computable Numbers, with an application to the Entscheidungsproblem" - Computable Numbers for short. Alan Turing had solved a major problem of mathematics with a fresh, direct and "simple" approach. Though it would take a little time to establish his reputation, that reputation was now assured.

He was not the only one to tackle the problem, however, for it had just been solved by an established American mathematician, Alonzo Church, at Princeton University. Though Turing's approach was radically different from Church's, the discovery of Church's work must have been a painful experience. Max Newman wrote to Church asking for help in getting Turing to Princeton so that he could be at the centre of things for a time and "so that he should not develop into a confirmed solitary". Alan Turing duly sailed for America on September 23,1936.

Princeton University had acquired the status of being the place for a mathematician to be. The Institute for Advanced Study had been set up there in 1932 and the double institute, as it could be viewed, attracted leading scientists to its bosom; Einstein was there, for example.

As with many great ideas when they are new, "Computable Numbers" did not cause a sensation though Church's review of it coined the expression "Turing machine". Turing described his work at a poorly-attended seminar and the paper was published whilst he was at Princeton. He was offered a second year in America, accepted, and submitted for a Ph.D. after a brief return to Cambridge.

Дата добавления: 2015-11-14