Book: Alan Turing - His Work and Impact

Editors: S Barry Cooper and Jan van Leeuwen

This book, to be published by Elsevier in the first half of 2012, will include a generous selection from the 4 volume set of the Collected Works of A. M. Turing, published by North-Holland in 1992/2001, together with a wide spectrum of accompanying short commentaries from world-leading experts on the significance and contemporary impact of the work. The book is intended to appear in time for the 2012 centenary of Turing's birth in London.

The aim is to deliver a more modern perspective than to be found so far in the literature; and to give meaning to the various works of Turing, bringing out the way in which they formed the beginnings of several fields that blossomed later on. The sequencing will be revised from the Collected Works, making it an exciting book, embedded in the story of Turing's scientific endeavours, more in the style of the Mathematical Logic volume of the Collected Works.

To be a worthy contribution to the Turing Centenary, the book will give a wide coverage of the many ways in which Turing's work has impacted on current research and understanding of the world. In order to do this, the contributors of commentaries have been chosen from many different fields and backgrounds, and their pieces accompanying particular Turing items will be short, not more than 8 pages, and typically 3 to 5 pages. The authors are encouraged to be brief, concise, and lively in their presentation. Personal viewpoints will be encouraged, though independently refereed and if necessary balanced with alternative views.

Guide for Authors:

All contributions should be prepared using LaTeX. Authors can find generic guidance via the Elsevier page Preparing Documents with LaTeX.

Authors should not worry too much about formatting issues initially, but should use use the elsarticle document class, downloadable from the elsarticle LaTeX document class webpage. You can also find there information on how to get Elsevier author support. See here for more details on the volume concept and formatting details.

Contributors:

Samson Abramsky Henk Barendregt Anthony Beavers Verónica Becher Henri Berestycki Meurig Beynon Mark Bishop Lenore Blum Rodney Brooks Cristian Calude Gregory Chaitin Jack Copeland Martin Davis Daniel Dennett Artur Ekert Solomon Feferman Luciano Floridi Juliet Floyd Lance Fortnow Nicholas Gessler Rainer Glaschick David Harel John Harper Dennis Hejhal Andrew Hodges Douglas Hofstadter Toby Howard Martin Hyland Cliff Jones

Richard Jozsa David Levy Philip Maini Hans Meinhardt Peter Millican James D. Murray Andrew Odlyzko Piergiorgio Odifreddi Christos Papadimitriou Michael Rathjen Bernard Richards Tony Sale Peter T. Saunders Klaus Schmeh Wilfried Sieg Aaron Sloman Alan Slomson Paul Smolensky Robert I. Soare Jonathan Swinton Christof Teuscher K. Vela Velupillai Paul Vitanyi Kevin Warwick/Huma Shah Frode Weierud Philip Welch Jiri Wiedermann Stephen Wolfram Sandy Zabell

Outline of contents, including selection of works by Turing:

The material will be organized within four parts, the content of each grouped around one of the major themes running through Turing's work. Each part will be introduced by the editors, and the individual items from Turing himself will be accompanied by two to five page commentary from the list of contributors above (which will be augmented and developed during the course of the preparation of the volume). A commentary will relate to an individual item (or in exceptional cases, preceding item), or possibly a subsequent group of items sharing a common theme. The names below each part are indicative, a number agreed with contributors, others under negotiation.

Part I: How Do We Compute? What Can We Prove?

Here would appear much of the content of the Mathematical Logic volume of the Collected Works. The organization of the material in this volume is more thematic, an example which it is intended to extend to this new collection. A number of very famous papers here. Intend to omit the 2 unpublished manuscripts from 1941 (Some theorems about Church's system) and 1943-44 (Practical forms of type theory II).

1. The Royal Society obituary, and the Robin Gandy letter (included under Loose Ends in the Mathematical Logic volume of the Collected Works):
   Alan Mathison Turing, M. H. A. Newman, in Biographical Memoirs of the Royal Society, 1955
   Handwritten letter from Robin Gandy to M. H. A. Newman, June 1954. Summarises Turing's unfinished work as it stood at the time of his death, including a description of Turing's ideas about quantum mechanics.
   • Andrew Hodges: A comment on Newman's Biographical Memoir
   
2. On Computable Numbers, with an Application to the Entscheidungsproblem, Proc. Lond. Math. Soc. (2) 42, pp 230-265 (1936)
   + ibid - correction, Proc. Lond. Math. Soc. (2) 43, pp 544-546 (1937)
   • Samson Abramsky: Two Puzzles About Computation - On the basic assumptions of: what we compute, and why we compute.
   Re 'what we compute' - Turing took traditional mathematical objects, real numbers, functions etc. as the things to be computed. In subsequent work in Computer Science, the view of computation has broadened enormously. In the work on concurrent processes, the behaviour is the object of interest. There is indeed a lack of a clear-cut Church-Turing thesis in this wider sphere of computation - computation as interaction, as Robin Milner put it.
   Re `why we compute', I have a conceptual discussion of the `quasi-paradox' of computation which runs parallel to the `quasi-paradox of deduction'. That is, it is surprisingly hard to explain, in any precise, quantitative sense, what we gain from inference, since indeed the conclusions are logically `contained' in the premises.
   • Henk Barendregt and Antonino Raffone: Cognition as a Discrete, Deterministic, and Universal Turing Machine Process - "mind states" and neurocognition
   • Meurig Beynon: Turing's Approach to Modelling States of Mind
   • Cristian Calude, Ludwig Staiger and Michael Stay: Halting and Non-Halting Turing Computations
   • Gregory Chaitin: From the Halting Problem to the Halting Probability
   • Martin Davis: Three Proofs of the Unsolvability of the Entscheidungsproblem
   • Artur Ekert: √ NOT   - Our knowledge of logic is inextricably linked with our knowledge of physical reality. The discovery of quantum mechanics in particular has provided practical instances of this and has changed our understanding of the nature of computation.
   • Rainer Glaschick: Turing Machines in Münster
   • Christos Papadimitriou: Alan and I
   • Aaron Sloman: Virtual Machinery and Evolution of Mind (Part 1)
   • Robert I. Soare: Turing and the Art of Classical Computability
   • Jan van Leeuwen and Jiri Wiedermann: Unexpected Computational Power of Non-Terminating Circular A-Machines - Turing machines and Unbounded Computation
   • K. Vela Velupillai: Reflections on Wittgenstein's Debates with Turing during his Lectures on the Foundations of Mathematics
   • Paul Vitanyi: Turing Machines and Understanding Computational Complexity
   • Philip Welch: Toward the Unknown Region: On Computing Infinite Numbers
   • Stephen Wolfram: The Importance of Universal Computation
   
3. Church, A., Review of Turing 1936-7, Journal of Symbolic Logic 2, p 42 (1937)
   • Andrew Hodges: Church's Review of Computable Numbers - Comment on Church's 'very significant' review
   
4. Computability and λ-definability, J. Symbolic Logic 2 pp 153-163 (1937)
   • Henk Barendregt, Giulio Manzonetto and Rinus Plasmeijer: The Imperative and Functional Programming Paradigm - functional vs imperative programming
5. The p-function in λ-K-conversion, J. Symbolic Logic 2 p 164 (1937), and
   Turing's proof that every typed lambda term has a normal form. Manuscript undated but probably 1941 or 42.
   Publ. in An early proof of normalization by A. M. Turing by R. O. Gandy, in Hindley and Seldin, 1980, pages 453-455
   • Henk Barendregt and Giulio Manzonetto: Turing's Contributions to Lambda Calculus - on the later importance of this work of Turing
   
6. Systems of Logic based on Ordinals , Proc. Lond. Math. Soc (2) 45 pp 161-228 (1939)
   • Alastair Abbott, Cris Calude and Karl Svozil: A Quantum Random Oracle
   • Solomon Feferman: Turing's Thesis: Ordinal Logics and Oracle Computability - dealing with Turing's Princeton PhD dissertation and the resulting 1939 ordinal logics paper, and based on the 2006 article in the AMS Notices 53, no. 10 (Nov. 2006), pp 1200-1207
   • Michael Rathjen: Turing's "Oracle" in Proof Theory - A brief commentary on Turing's impact on proof theory, focusing on the oracle idea from this paper on ordinal logics
   • Philip Welch: Truth and Turing: Systems of Logic Based on Ordinals
   
7. Practical Forms of Type Theory, J. Symbolic Logic 13, pp 80-94 (1948)
   • Robin Gandy: Background remarks from his Collected Works PREFACE to the paper
8. The Use of Dots as Brackets in Church's System, J. Symbolic Logic 7, pp 146-156 (1942)
   • Lance Fortnow: Turing's Dots - insights into computer science before there was computer science
   
9. The Reform of Mathematical Notation (1944-45, unpublished, in Collected Works)
   • Juliet Floyd: Turing, Wittgenstein and Types: Philosophical Aspects of Turing's "The Reform of Mathematical Notation and Phraseology" (1944-5)
   • Stephen Wolfram: Computation, Mathematical Notation, and Linguistics - Mathematical Notation and The Poetry of Function Naming (cf. online items Mathematical Notation: Past and Future and The Poetry of Function Naming)

Part II: Hiding and Unhiding Information: Cryptology, Complexity and Number Theory.

This might include a number of the writings previously included in the Pure Mathematics volume of the Collected Works, relating as they do to cryptanalysis and computer science. The problems with divisions between volumes which particularly affects this one, are brought out well in the introduction by the editor, J. L. Britton. Inclusions:

1. On the Gaussian Error Function, King's College Fellowship dissertation (1935) (Preface in the Collected Works; available in full at the Turing Digital Archive, item AMT/C/28).
   • Sandy L. Zabell: Alan Turing and the Central Limit Theorem - An update of the 1995 American Math. Monthly article
2. A Method for the Calculation of the Zeta-function, Proc. London Math. Soc. (2) 48 pp 180-197 (1945, submitted 1939),
   Some Calculations of the Riemann Zeta-function, Proc. London Math. Soc. (3) 3 pp 99-117 (1953) and
   (with S. Skewes) On a Theorem of Littlewood (unpublished, in Collected Works), (more relating to the Zeta function)
   • Dennis Hejhal and Andrew Odlyzko: Alan Turing and the Riemann Zeta Function and
   • Dennis Hejhal: A Few Comments About Turing's Method - Commentary arising from the importance of the above papers (including the unpublished item with Skewes) to Hejhal's work and number theory, cf. Turing: A Bit Off the Beaten Path
3. Solvable and Unsolvable Problems, Science News 31, pp 7-23 (1954) (popular writing, could go into Part I or III)
   • Gregory Chaitin: Turing's Small Gem "This lovely paper by Turing beautifully illustrates Hilbert's remark in his 1900 Paris International Congress of Mathematicians paper on Mathematical Problems that one does not truly understand something until one can explain it to the first man that one meets on the street."
   • Wilfried Sieg: Normal Forms for Puzzles: A Variant of Turing's Thesis
   • K. Vela Velupillai: Turing on 'Solvable and Unsolvable Problems & Simon on 'Human Problem Solving' - Turing's fundamental work on Solvable and Unsolvable Problems, Intelligent Machinery and Computing Machinery and Intelligence had a profound effect on the work of Herbert Simon, the only man to win both the ACM Turing Prize and the Nobel Memorial Prize in Economics, particularly in defining boundedly rational economic agents as information processing systems (IPS) solving decision problems. A summary of this line of work and research forms the substance of this contribution.
   
4. The Word Problem in Semi-groups with Cancellation, Ann. of Math. 52 (2), pp 491-505 (1950)
   • Gregory Chaitin: Finding the Halting Problem and the Halting Probability in Traditional Mathematics, with reference to normal numbers, Part II, item 9
5. On Permutation Groups (unpublished, in Collected Works), (relates to Turing's interest in the Enigma machine)
   • John Leslie Britton: Introduction taken from the Collected Works
   
6. Rounding-off Errors in Matrix Processes, Quart. J. Mech. Appl. Math. 1, pp 287-308 (1948)
   • Lenore Blum: Alan Turing and the Other Theory of Computation - 'This has had almost as much impact in the numerical/scientific computing community as Turing's On Computable Numbers has had in the discrete computing community' (see her 2004 Notices of the AMS Where Turing meets Newton article)
7. A Note on Normal Numbers (unpublished, in Collected Works - see also slightly different manuscript version surviving in the Turing Digital Archive)
   • Verónica Becher: Turing's Note on Normal Numbers - concerning correctness of Turing's algorithm, cf. Britton's comment in the Collected Works
   • Andrew Hodges: Computable Numbers and Normal Numbers - 'normal numbers' and the emergence of computable numbers
8. Would also include here the Enigma material from the Mathematical Logic volume:
   Turing's treatise on the Enigma (Prof's Book)
   • Tony Sale: Alan Turing, the Enigma and the Bombe
   - an explanation of the part of the Prof's Book starting on p.96, about Turing's arriving at the ideas for the Bombe
   • Klaus Schmeh: Why Turing Cracked The Enigma And The Germans Didn't
   • Frode Weierud: Prof's Book: Seen in the Light of Cryptologic History - A short background on the Prof's Book; how it materialised in 1939-40; Alan's early days in the cottage with Dilly Knox
   
9. Also the innovative:
   Speech System 'Delilah' - report on progress, 6 June 1944. Three-page typescript report in the National Archives, HW 62/6
   • John Harper: Turing's Voice Secrecy System 'Delilah' Resurrected - Commentary on the recently discovered full report, on Turing's role at Hanslope Park, and on the current rebuild project.
   
10. And a selection of papers related to programming, from:
    Checking a Large Routine (Paper for the EDSAC Inaugural Conference, 24 June 1949, original typescript reproduced in the Collected Works)
    An early program proof by Alan Turing, L. Morris and C. B. Jones, Ann. Hist. Computing 6 (2) pp 129-143 (1984)
    • Cliff Jones: Turing's "Checking a Large Routine" - An update on the Ann. Hist. Computing article, indicating what followed
    
11. Programmers' Handbook for the Manchester electronic computer, Manchester University Computing Laboratory (1950)
    Local Programming Methods and Conventions, in the Manchester University Computer Inaugural Conference, July 1951
    • Toby Howard: Turing's Contributions to the Early Manchester Computers
    • Bernard Richards: Recollections of Life in the Laboratory with Alan Turing

Part III: Building a Brain: Intelligent Machines, Practice and Theory.

The only significant omission here from the Mechanical Intelligence volume of the Collected Works would be Turing's 1945 ACE report (and The Automatic Computing Engine, Lectures given at the Ministry of Supply, December 1946 and January 1947, by Turing and J. H. Wilkinson). This is very long, and not a light read. It is, of course, hugely important in understanding Turing's thinking on this important piece of early computer history. It was thought that Checking a Large Routine was not so necessary, but, as so often with Turing, it turns out to have significance (for complexity theory) -- now in Part II above. Inclusions:

1. Lecture to the London Mathematical Society on 20 February 1947 (in A. M. Turing's ACE Report of 1946 and Other Papers, eds. B. E. Carpenter and R. W. Doran, MIT Press, 1986, Volume 10 in the Charles Babbage Institute reprint series for the History of Computing), (more readable guide to the ACE computer)
   • Anthony Beavers: Alan Turing: Mathematical Mechanist - bringing out how this and Intelligent Machinery (see below) show a direct connection to the informational mechanisms of the late 19th and early 20th centuries and point toward the future as well
2. Intelligent Machinery, report written by Turing for the National Physical Laboratory, 1948 (in the Collected Works, and in The Essential Turing, typographically reset), (essential, of course, an important item for many - see the 9 page introduction to the Mechanical Intelligence volume by editor Darrel Ince)
   • Rodney Brooks: The Case for Embodied Intelligence - How Turing foresaw the importance of the body for intelligent understanding of the world. And why he rejected it temporarily for reasons of practicality. And how that set the stage for the first 40 years of AI research.
   • Nicholas Gessler: The Computist, the Cryptographer and the Physicist
   • Douglas Hofstadter: The Gödel-Turing Threshold and the Human Soul - universal Turing machines and strange loops: the complementary strengths and weaknesses of universal Turing machines and of human brains
   • Paul Smolensky: Multiple Dualities of Mind and Machine: Two Routes for Mapping Cognition to Computation
   • Christoff Teuscher: A Modern Perspective on Turing's Unorganized Machines
   • Stephen Wolfram: Intelligence and the Computational Universe - The Quest to Make the World Data Computable
3. Computing Machinery and Intelligence, Mind 49, pp 433-460 (1950) (the celebrated MIND article)
   • Mark Bishop: The Phenomenal Case of the Turing Test and the Chinese Room - Under the skin: disarming the Turing Test with a joke - critiquing the Mind article and the adequacy of the Turing Test.
   • Gregory Chaitin: Mechanical Intelligence versus Uncomputable Creativity - "It is a delightful paradox that Turing argues that we are machines while all the while emphasizing the importance of what machines cannot do. Like a good philosopher, he cannot help seeing the good arguments on both sides. He thus provides ammunition to both parties."
   • Daniel Dennett: Turing's "Strange Inversion of Reasoning" - Turing and Darwin
   • Luciano Floridi: Levels of Abstraction and the Turing Test
   • David Harel: A Turing-like Test for Modeling Nature
   • Peter Millican: The Philosophical Significance of the Turing Test and the Turing Machine
   • Huma Shah: Conversation, Deception and Intelligence: Turing's question-answer game
   • Aaron Sloman: The Mythical Turing Test
   • Aaron Sloman: Virtual Machinery and Evolution of Mind (Part 2)
   • Kevin Warwick: Turing's Future
   
4. And 2 popular articles, both quite includable, given that the first relates to Turing's seminal role in relation to computer chess, and the second talks approachably about the incomputable (and is not so easy to place - currently in Part III - 23/10/2011, moved to Part II as fits with word problems):
   Chess, a subsection of chapter 25, Digital Computers Applied to Games, of Faster than Thought, ed. B. V. Bowden, Pitman, London (1953) (in Collected Works)
   • David Levy: Alan Turing on Computer Chess
   • Alan Slomson: Turing and Chess
   
5. Copeland has 3 interesting radio broadcasts from 1951-52. It would be nice to include these:
   Intelligent Machinery: A heretical theory, a talk given by Turing at Manchester, included (ed. B. J. Copeland) in K. Furukawa, D. Michie, S. Muggleton (eds.), Machine Intelligence 15, Oxford University Press (1999) and in The Essential Turing.
   Can digital computers think?, Radio broadcast, 1951 not included in the Collected Works, but included (ed. B. J. Copeland) in K. Furukawa, D. Michie, S. Muggleton (eds.), Machine Intelligence 15, Oxford University Press (1999), and in The Essential Turing
   • Jack Copeland: Turing and the Physics of the Mind
   Can automatic calculating machines be said to think? Radio broadcast, 1952: discussion with M. H. A. Newman, G. Jefferson, R. B. Braithwaite, included (ed. B. J. Copeland) in K. Furukawa, D. Michie, S. Muggleton (eds.), Machine Intelligence 15, Oxford University Press (1999), and in The Essential Turing.
   • Richard Jozsa: Quantum Complexity and the Foundations of Computing

Part IV: The Mathematics of Emergence: The Mysteries of Morphogenesis.

Aim to include here everything of Turing's from the Morphogenesis volume of the Collected Works, and to consult with Jonathan Swinton and others concerning the possible unpublished work. (Some general remarks for this section received from Gregory Chaitin.) So would include:

1. The Chemical Basis of Morphogenesis, Phil. Trans. R. Soc. London B 237 pp 37-72 (1952), (the famous 1952 paper)
   • Henri Berestycki: Alan Turing and Reaction-Diffusion Equations
   • Gregory Chaitin: From Turing to Metabiology and Life as Evolving Software - Connects the work on morphogenesis to Turing's earlier work relating to incomputability and mind, and to the later developments in biology and its mathematics.
   • Philip Maini: Turing's Theory of Morphogenesis - His 1952 paper for morphogenesis → its impact on biology with applications, predictions, iterations back and forth with experiments - successes and failures. In parallel, how it has generated mathematical analysis and questions therein.
   • James D. Murray: After Turing - The Birth and Growth of Interdisciplinary Mathematics and Biology
   • Hans Meinhardt: Traveling Waves and Oscillations Out of Phase: an almost forgotten part of Turings paper - Focussing on the almost forgotten part in Turing's morphogenesis paper, the three-component systems. One needs the three-component systems to handle Phyllotaxis correctly.
   • Peter T. Saunders: Defeating the Argument from Design - Turing's insight in biology
   • K. Vela Velupillai: Four Traditions of 'Emergence': Morphogenesis, Ulam-von Neumann Cellular Automatas, the Fermi-Pasta-Ulam Problem and British 'Emergentism' - Two strands of thought, one directly inspired by this paper, the other only indirectly related to it, form the basis of this brief note. The first is Ilya Prigogine's imaginative use of the notion of a Turing Bifurcation. The second is what has come to be called British Emergentism.
   • Stephen Wolfram: The Mechanisms of Biology - Why Turing Hadn't Thought of Using His Machines for Biological Systems
2. Morphogen Theory of Phyllotaxis (what Saunders calls "Turing's major unfinished work", in 3 parts):
   I. Geometrical and Descriptive Phyllotaxis
   II. Chemical Theory of Morphogenesis
   III. (written by B. Richards) A Solution of the Morphogenetical Equations for the Case of Spherical Symmetry
   • Bernard Richards: Radiolaria: The Result of Morphogenesis
   • Aaron Sloman: Evolution of Biological Virtual Machinery - Report on work in progress, related to presentations, supervenience and causation in virtual machinery
   • Jonathan Swinton: Turing's Life in Pictures: the Search for Fibonacci
   
3. Finally, the short piece on: Outline of the Development of the Daisy

Bibliography.

The aim is to rectify the omission of a bibliography in the Collected Works. The essential reference here, and basis for such a bibliography (and for the references above), is Andrew Hodges' carefully researched webpage:

The Alan Turing Bibliography