Copeland B. Jack - The essential Turing

The Essential Turing

Alan M. Turing

Seminal Writings in Computing, Logic, Philosophy,
Artificial Intelligence, and Artificial Life
plus The Secrets of Enigma

Edited byB. Jack Copeland

Great Clarendon Street, Oxford OX2 6DP

Oxford University Press is a department of the University of Oxford.
It furthers the Universitys objective of excellence in research, scholarship,
and education by publishing worldwide in

Oxford New York

Auckland Cape Town Dar es Salaam Hong Kong Karachi
Kuala Lumpur Madrid Melbourne Mexico City Nairobi
New Delhi Taipei Toronto Shanghai

With offices in

Argentina Austria Brazil Chile Czech Republic France Greece
Guatemala Hungary Italy Japan South Korea Poland Portugal
Singapore Switzerland Thailand Turkey Ukraine Vietnam

Published in the United States
by Oxford University Press Inc., New York

In this volume the Estate of Alan Turing 2004

Supplementary Material the several contributors 2004

The moral rights of the author have been asserted

Database right Oxford University Press (maker)

First published 2004

All rights reserved. No part of this publication may be reproduced,
stored in a retrieval system, or transmitted, in any form or by any means,
without the prior permission in writing of Oxford University Press,
or as expressly permitted by law, or under terms agreed with the appropriate
reprographics rights organization. Enquiries concerning reproduction
outside the scope of the above should be sent to the Rights Department,
Oxford University Press, at the address above.

You must not circulate this book in any other binding or cover
and you must impose this same condition on any acquirer.

British Library Cataloguing in Publication Data

Data available

Library of Congress Cataloging in Publication Data

Data available

ISBN 0198250797
ISBN 0198250800 (pbk.)

10 9 8 7 6 5 4 3

Typeset by Kolam Information Services Pvt. Ltd, Pondicherry, India
Printed in Great Britain
on acid-free paper by Biddles Ltd., Kings Lynn, Norfolk

Work on this book began in 2000 at the Dibner Institute for the History of Science and Technology, Massachusetts Institute of Technology, and was completed at the University of Canterbury, New Zealand. I am grateful to both these institutions for aid, and to the following for scholarly assistance: John Andreae, Friedrich Bauer, Frank Carter, Alonzo Church Jnr, David Clayden, Bob Doran, Ralph Erskine, Harry Fensom, Jack Good, John Harper, Geoff Hayes, Peter Hilton, Harry Huskey, Eric Jacobson, Elizabeth Mahon, Philip Marks, Elisabeth Norcliffe, Rolf Noskwith, Gualtiero Piccinini, Andrs Sicard, Wilfried Sieg, Frode Weierud, Maurice Wilkes, Mike Woodger, and especially Diane Proudfoot. This book would not have existed without the support of Turings literary executor, P. N. Furbank, and that of Peter Momtchiloff at Oxford University Press.

B.J.C.

Jack Copeland

Jack Copeland

Alan Turing, Emil Post, and Donald W. Davies

Jack Copeland

Patrick Mahon

Jack Copeland

Alan Turing, Richard Braithwaite, Geoffrey Jefferson, and Max Newman

Jack Copeland

Jack Copeland

Alan Mathison Turing was born on 23 June 1912 in London;he died on 7 June 1954 at his home in Wilmslow, Cheshire. Turing contributed to logic, mathematics, biology, philosophy, cryptanalysis, and formatively to the areas later known as computer science, cognitive science, Artificial Intelligence, and Artificial Life.

Educated at Sherborne School in Dorset, Turing went up to Kings College, Cambridge, in October 1931 to read Mathematics. He graduated in 1934, and in March 1935 was elected a Fellow of Kings, at the age of only 22. In 1936 he published his most important theoretical work, On Computable Numbers, with an Application to the Entscheidungsproblem [Decision Problem] (). This article described the abstract digital computing machinenow referred to simply as the universal Turing machineon which the modern computer is based. Turings fundamental idea of a universal stored-programme computing machine was promoted in the United States by John von Neumann and in England by Max Newman. By the end of 1945 several groups, including Turings own in London, were devising plans for an electronic stored-programme universal digital computera Turing machine in hardware.

In 1936 Turing left Cambridge for the United States in order to continue his research at Princeton University. There in 1938 he completed a Ph.D. entitled Systems of Logic Based on Ordinals, subsequently published under the same title (). Now a classic, this work addresses the implications of Gdels famous incompleteness result. Turing gave a new analysis of mathematical reasoning, and continued the study, begun in On Computable Numbers, of uncomputable problemsproblems that are too hard to be solved by a computing machine (even one with unlimited time and memory).

Turing returned to his Fellowship at Kings in the summer of 1938. At the outbreak of war with Germany in September 1939 he moved to Bletchley Park, the wartime headquarters of the Government Code and Cypher School (GC & CS). Turings brilliant work at Bletchley Park had far-reaching consequences. having been classified until recently.

In 1945, the war over, Turing was recruited to the National Physical Laboratory (NPL) in London, his brief to design and develop an electronic digital computera concrete form of the universal Turing machine. His design (for the Automatic Computing Engine or ACE) was more advanced than anything else then under consideration on either side of the Atlantic. While waiting for the engineers to build the ACE, Turing and his group pioneered the science of computer programming, writing a library of sophisticated mathematical programmes for the planned machine.

Turing founded the field now called Artificial Intelligence (AI) and was a leading early exponent of the theory that the human brain is in effect a digital computer. In February 1947 he delivered the earliest known public lecture to mention computer intelligence (Lecture on the Automatic Computing Engine ().

In the end, the NPLs engineers lost the race to build the worlds first working electronic stored-programme digital computeran honour that went to the Computing Machine Laboratory at the University of Manchester in June 1948. The concept of the universal Turing machine was a fundamental influence on the Manchester computer project, via Newman, the projects instigator. Later in 1948, at Newmans invitation, Turing took up the deputy directorship of the Computing Machine Laboratory (there was no Director). Turing spent the rest of his short career at Manchester University. He was elected a Fellow of the Royal Society of London in March 1951 (a high honour) and in May 1953 was appointed to a specially created Readership in the Theory of Computing at Manchester.

It was at Manchester, in March 1952, that he was prosecuted for homosexual activity, then a crime in Britain, and sentenced to a period of twelve months hormone therapythe shabbiest of treatment from the country he had helped save, but which he seems to have borne with amused fortitude.