It is my contention that these operations include all those which are used in the computation of a number.
Using the machine concept, Alan Turing went on to explain how there were various problems which could not be solved by machines. Any given special-purpose machine could have its functionality (its program) rendered into symbols, which could actually be put on the tape as data to be tested by another machine running a different program. By running one program to test another, Alan was able to find some mathematical equivalents to the Epimenides paradox (‘Epimenides the Cretan says that all Cretans are liars’). By producing contradictions, certain machines can be shown to be impossible: one example is a program to decide whether any particular program would ever lead to the machine printing the symbol ‘0’. The ‘halting problem’ – a program to see if any other program would run forever or halt at some stage – is a similar, more modern example; again, it can be proved by contradiction that such a program cannot be written.
TURING MACHINES – WHAT YOU NEED TO KNOW
Most people have got through life happily and successfully without knowing the first thing about Turing machines, and that’s fine. So you probably need to know nothing about them. But it might help a little to have some notion, in order to put the rest of Alan Turing’s life – much of which was founded on his greatest mathematical achievement, the paper on Computable Numbers – into context.
The machine which Alan Turing conceptualised has a read-write head and a long tape. It also has a set of instructions which tell it what to do when it finds itself in a particular ‘state’, or as he put it, ‘m-configuration’. So, for example, in State 1, it might view the tape, and if it is blank, print an asterisk, and then go to State 2. In State 2 it might just move the tape one place to the right, and then go to State 1. In State 1, if the tape is not blank, it might just go to State 2. (This might not be a very exciting set of instructions, but no matter.) The point here is that the instructions can all be coded into language or numerical form. Kurt Gödel had previously shown that formulae can be re-coded as numbers – and numbers can be handled like data.
Alan Turing’s ‘universal’ machine takes a tape which has the instructions-code for another machine – like the boring machine which just prints an endless set of asterisks wherever it finds a blank space – and by reading the code can mimic the behaviour of the boring machine. Or any machine. The self-referential nature of the universal machine, treating instructions as data, is what enabled him to make his mathematical proof for the Entscheidungsproblem.
However, the idea that instructions-code could be put onto a tape, or to express it differently, that a program for a machine could be a simple input (like the numbers you input into a cheap calculator when you want to perform simple addition), was very powerful. Here was the theoretical construct of a stored-program computer for which you could change the program.
A model ‘Turing machine’ created in the 1950s by Professor Gisbert Hasenjäger. Without their knowledge, they were to become opponents in the cryptographic war.
Troubles with the post
Alan’s first paper on computable numbers went astray in the mail.
Dear Mother, […]
I have just got my main paper ready & sent in. I imagine it will appear in October or November. The situation with regard to the note for Comptes Rendus was not so good. It appears that that man who I wrote to, and whom I asked to communicate the paper for me had gone to China, and moreover the letter seems to have been lost in the post, for a second letter reached his daughter.
And then M.H.A. Newman opened his own mail. Working in Princeton, New Jersey, the respected mathematician Alonzo Church had published his own paper, in the first edition of the Journal of Symbolic Logic – conveniently enough, the journal of the Association for Symbolic Logic, which Church himself had founded in 1935. Church had invented a mathematical grammar, called the lambda-calculus, and while Turing wrote in terms of ‘computability’ for mathematical functions carried out by his conceptual machine, Church wrote of ‘lambda-definability’. But they were basically the same thing, and both concepts were being used to shred the remaining vestiges of Hilbert’s plan for tidiness in mathematics. Church thought Newman would be interested; Newman certainly was.
Dear Professor Church,
An offprint which you kindly sent me recently of your paper in which you define ‘calculable numbers’, and shew that the Entscheidungsproblem for Hilbert logic is insoluble, had a rather painful interest for a young man, A.M. Turing, here, who was just about to send in for publication a paper in which he had used a definition of ‘Computable numbers’ for the same purpose. His treatment – which consists in describing a machine which will grind out any computable sequence – is rather different from yours, but seems to be of great merit, and I think it of great importance that he should come and work with you next year if that is at all possible.
Yours sincerely,
M.H.A. Newman
Alan’s work had, once again, been scooped. His letter to Mother continues:
Meanwhile a paper has appeared in America, written by Alonzo Church, doing the same things in a different way. Mr Newman and I have decided however that the method is sufficiently different to warrant the publication of my paper too. Alonzo Church lives at Princeton so I have decided quite definitely about going there. […]
Yours
Alan
Two could play at the editorial game, and M.H.A. Newman had influence with the London Mathematical Society. Accordingly, Alan Turing’s paper on Computable Numbers was ‘Received 28 May, 1936 – Read 12 November, 1936’ and finally published in the Proceedings of that Society in early 1937. Alan’s paper was different in concept from Church’s: the concept of a universal computing machine opened up for exploration a large number of new avenues in logic, and Alan only devoted a couple of pages to the Entscheidungsproblem. The wider view he offered meant that Alan’s paper became a foundation stone for a whole mathematical discipline, namely computability. And, because it laid down for the first time an account of a programmable computing machine, generations of computer science students have come to curse the name of Alan Turing because Computable Numbers appears on undergraduate reading lists: it is long, it uses symbols printed in German Gothic typeface, and, like John von Neumann’s German work on quantum mechanics, it is rather strong meat.
Many years later, Alan wrote a different version for more general readers, where the meat was cut up into more digestible pieces. Here is the introductory paragraph:
If one is given a puzzle to solve one will usually, if it proves to be difficult, ask the owner whether it can be done. Such a question should have a quite definite answer, yes or no, at any rate provided the rules describing what you are allowed to do are perfectly clear. Of course the owner of the puzzle may not know the answer. One might equally ask, ‘How can one tell whether a puzzle is solvable?’, but this cannot be answered so straightforwardly. The fact of the matter is that there is no systematic method of testing puzzles to see whether they are solvable or not. If by this one meant merely that nobody had ever yet found a test which could be applied to any puzzle, there would be nothing at all remarkable in the statement. It would have been a great achievement to have invented such a test, so we can hardly be surprised that it has never been done. But it is not merely that the test has never been found. It has been proved that no such test ever can be found.
M.H.A. Newman’s copy of Alan Turing’s most famous academic paper. Newman supervised this paper and (unlike his copies of Alan’s other offprints) it bears few annotations.
He illustrated this new paper with examples of the sliding-square puzzle, where 15 little squares bearing numbers or pictures can be moved within a 4x4 frame using the empty space. Here he uses plenty of pictures, no German Gothic, and far fewer pages, and games take the place of universal computing machines. Games were already occupying Alan’s mind back in 1936 as he thought through the implications of Computable Numbers.
Games were a homely sample of mathematical-logical problems, subject to sets of tidy rules, which could in theory be used to program notional computing machines. Any such program was fanciful, of course, not least because in 1936 there was no practical concept of a programmable computing machine. But Alan was happy to write down systematically the rules for things like the Japanese game with counters called Go.
Autumn leaves
Although Alan’s paper was ‘read’ on 12 November 1936, it was not he that was reading it. By this time he had arrived at Princeton. Through the persistence of Newman, Alonzo Church and John von Neumann – the latter by now a leading light at Princeton’s Institute for Advanced Study – had agreed to accommodate Alan Turing for a year at Princeton, and he had left for the United States on 23 September. Meanwhile there had been a round of leave-taking visits: to see Ethel and Julius, of course, though both of them being in the same place at the same time was becoming unusual; and, perhaps more enjoyably, a few days with the Morcoms. By this stage Isobel Morcom was unwell and largely confined to her bed:
SEPTEMBER, 1936.
Wednesday 9
Slept very late & feel much refreshed for first time for ages. Alan Turing came. He arrived in Bromsgrove at an earlier time than he had arranged. He has come for a farewell visit before going out to America for 9 months (Princetown) to study under 3 great authorities on his subject: Gödel (Warsaw) Alonso Church and Kleene. We had talk before dinner & again later to bring us up to date with our news.
Thursday 10
V1 & Alan tea up here with me. Had long talk with Alan about his work & whether in his subject, some abstruse branch of logic, one would come to ‘dead end’ etc.
Friday 11
Alan went down alone to church to see Chris’ window2 & the little garden which he hadn’t seen before since it was finished only the day he came to the dedication of the window. Alan taught me game called ‘go’ rather like ‘peggoty’.
Saturday 12
Came down dinner first time for 3 weeks.
Too little sleep. Many things to arrange this morning. Rupert3 & Alan had tea in my room & then I took them all by surprise by coming down to dinner. There were 10 of us – & jolly party. Gramophone concert. Rup’s latest cinema photos & the fishing one. Men billiards.
Sunday 13
Alan Rup and 2 girls (Enid & Jean) bathed at Cadbury’s pool. Rup & Alan tea with me. Alan tried to explain what he is working at. Had business talk to Enid & then came down while she Jean Rup & Alan were having supper. They went off to catch 7.45 New St.
Passport to Princeton: Alan Turing’s passport photograph.
The rules of Go. Alan’s drawings for Mrs Morcom.
Princeton was charming in the fall – discreet colonial-style elegance; sunshine and showers; lawns, leaves, trees, and attractive buildings; the greatest assembly of mathematical talent ever collected in one university; a touch of culture-shock for someone with traces of Raj imperiousness, educated at a British boarding school, and not accustomed to the extravagance of taxis.
ON BOARD CUNARD WHITE STAR ‘BERENGARIA’
Sept 28
It strikes me that Americans can be the most insufferable and insensitive creatures you could wish. One of them has just been talking to me and telling me of all the worst aspects of America with evident pride. However they may not all be like that.
The Graduate College, Princeton N.J
6 Oct
Passing the immigration officers involved waiting in a queue for over two hours with screaming children round me. Then, after getting through the customs I had to go through the ceremony of initiation to the U.S.A, consisting of being swindled by a taxi driver. I considered his charge perfectly preposterous, but as I had already been charged more than double English prices for sending my baggage, I thought it was possibly right. It seems that some things are ridiculously expensive here, but some definitely cheaper than in England; notably railway travel is very cheap $1 for 50 miles on the single journey. […]
These Americans have various peculiarities in conversation which catch the ear somehow. Whenever you thank them for anything they say ‘You’re welcome’. I rather liked it at first, thinking that I was welcome, but now I find it comes back like a ball thrown against a wall, and become positively apprehensive. Another habit they have is to make the sound described by authors as ‘Aha’. They use it when they have no suitable reply to a remark, but think that silence could be rude.
The Graduate College
Princeton N.J
Oct 14
My dear Mother,
You have often asked me about possible applications of various branches of mathematics. I have just discovered a possible application of the kind of thing I am working on at present. It answers the question ‘What is the most general kind of code or cipher possible’, and at the same time (rather naturally) enables one to construct a lot of particular and interesting codes. One of them is pretty well impossible to decode without the key and very quick to encode. I expect I could sell them to H. M. Government for quite a substantial sum, but am rather doubtful about the morality of such things. What do you think?
Church had me out to dinner the other night. Considering that the guests were all university people I found the conversation rather disappointing. They seem, from what I can remember of it, to have discussed nothing but the different states that they came from. Description of travel and places bores me intensely.
I had a nasty shock when I got into Church’s house. I think I had told you that Church was half blind in one eye. Well I saw his father in the house and he was quite blind (and incidentally very deaf). I should have thought very little of it had it not been for Church being rather blind himself. Any hereditary defects of that kind give me the shudders. […]
Yours
Alan
Looking Glass Zoo
One imagines that the Americans found Alan, and his enthusiasm for mathematical puzzles, just as peculiar. Alonzo Church, and his work on symbolic logic, were the reasons Alan was in Princeton; most of the other mathematicians whom Alan had hoped to find at Princeton were, for one reason or another, away. It was not obvious that the fastidious Church, whose lectures were so precisely careful as to be ponderous as well as pedantic, would get along with the untidy and atheistic Turing who would spin off new, partly thought-out ideas as randomly as he dressed. An obituary of Church, written to accompany Church’s collected works, described his style:
Alonzo Church had the polite manners of a gentleman who had grown up in Virginia. He was never known to be rude, even with people with whom he had strong disagreements. A deeply religious person, he was a lifelong member of the Presbyterian church. In his habits he was careful and deliberate – very careful and very deliberate. The students in his classes would discover this on the first day, when they saw how he would erase a blackboard. The material he wrote out on paper (he did not type) was often done in several colors of ink – sometimes colors made by mixing bottles together – and always done in his distinctive unslanted hand-writing. He was a master at using white-out fluid to eliminate imperfections.
Notwithstanding the shaky start, there was ample hospitality: an invitation to spend Thanksgiving in New York with one of the local Anglo-Catholic clergy; a weekly Sunday social event hosted by the Graduate College Dean, Dr Luther P. Eisenhart; and hockey matches becoming a regular fixture. By November, Alan was settling in.
Alonzo Church, Alan Turing’s supervisor at Princeton.
GRADUATE COLLEGE
PRINCETON UNIVERSITY
Nov. 11
My dear Mother,
It appears that Dean Underhill1 has been writing to one of his friends in New York to let him know that I am here. Said friend has written to ask me to stay with him some weekend in the comparatively near future. Certainly these Americans are astoundingly hospitable.
One of the Commonwealth Fellows, Francis Price, arranged a hockey match the other day between the Graduate College and Vassar, a wome
n’s college (amer)/university (engl.) some 130 miles away. He got up a team of which only half had ever played before. We had a couple of practice games and went to Vassar in cars on Sunday. It was raining slightly when we arrived, and what was our horror when we were told the ground was not fit for play. However we persuaded them to let us play a pseudo-hockey game in their gymn. at wh. we defeated them 11-3. Francis is trying to arrange a return match, which will certainly take place on a field. […]
Prof Page 8
