Book: Alan Turing - His Work and Impact (Authors' Page)

Editors: S Barry Cooper and Jan van Leeuwen

This book, to be published by Elsevier in the second half of 2011, 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 2 or 3 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:

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 brief critique of the Newman biographical memoir.
  2. On Computable Numbers, with an Application to the Entscheidungsproblem, Proc. Lond. Math. Soc. (2) 42, pp 230-265 (1936)
    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
    Jack Lutz: Touching on various issues:
    a. Essential roles in the subsequent development of Kolmogorov complexity and algorithmic randomness.
    b. Current/ongoing issues regarding the meanings of the thesis and universality in physical/geometric contexts like molecular programming and algorithmic self-assembly.
    c. Gödel's contrast of the absoluteness of computability with the relative nature of provability and definability.
    d. Impact on complexity theory, especially the P versus NP problem.
    Peter Millican: Commentary from a general philosophical and cultural point of view
    Piergiorgio Odifreddi and S. Barry Cooper: Turing's Church - an updated discussion of the ramifications of the Church-Turing Thesis, taking the relevant 20 pages from Classical Recursion Recursion Theory as starting point
    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. On Computable Numbers, with an Application to the Entscheidungsproblem - correction, Proc. Lond. Math. Soc. (2) 43, pp 544-546 (1937)
    Jack Lutz: The significance of this correction for computable analysis
  4. 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
  5. 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
  6. 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
  7. 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
    Jack Lutz: The significance of the oracle Turing machine for computational complexity, algorithmic randomness, and computable analysis
    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
  8. (with M. H. A. Newman) A Formal Theorem in Church's Theory of Types J. Symbolic Logic 7 pp 28-33 (1942)
  9. 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
  10. Practical Forms of Type Theory, J. Symbolic Logic 13, pp 80-94 (1948)
  11. 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)

Other commentaries from:
Hyland.

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)
  3. Some Calculations of the Riemann Zeta-function, Proc. London Math. Soc. (3) 3 pp 99-117 (1953)
    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 3 papers (and the unpublished item with Skewes below) to Hejhal's work and number theory, cf. Turing: A Bit Off the Beaten Path
  4. (with S. Skewes) On a Theorem of Littlewood (unpublished, in Collected Works), (more relating to the Zeta function)
  5. 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
  6. Solvable and Unsolvable Problems, Science News 31, pp 7-23 (1954) (popular writing, could go into Part I)
    Wilfried Sieg: Normal Forms for Puzzles: A Variant of Turing's Thesis
  7. The Word Problem in Compact Groups (unpublished, in Collected Works)
  8. On Permutation Groups (unpublished, in Collected Works), (relates to Turing's interest in the Enigma machine)
  9. 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)
  10. 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
    Jack Lutz: The challenges that this work poses for present-day research on finite-state dimension, meta-normality, data compression, and ergodic number theory
    Philip Welch:
  11. Would also include here the Enigma material from the Mathematical Logic volume:
    Turing's treatise on the Enigma (Prof's Book)
    Jack Copeland: A brief commentary on an interesting extract from the full 'Treatise on the Enigma'
    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
    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
    Report by Turing on U. S. Navy cryptanalytic work and their machinery, November 1942. National Archives, HW 57/10 (released October 2004)
    Klaus Schmeh: Why Turing Cracked The Enigma And The Germans Didn't
    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.
    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
    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 Early Programming on the Manchester Machines
    Bernard Richards: Recollections of Turing in the Lab and how he programmed the Mark I computer

Other commentaries from:
Hyland.

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: 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)
    Anthony Beavers: Alan Turing: Mathematical Mechanist
    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.
    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:
    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):
    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
    Solvable and Unsolvable Problems, Science News 31, pp 7-23 (1954)
    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."
    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.
  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
  6. Finally, we include Gödel's brief critique of Turing, in the Collected Works, vol. II, item 1972a:
    Gödel, K., Some Remarks on the Undecidability Results, in Collected Works, II, pp 305-306
    Solomon Feferman: Gödel's remarks on "a philosophical error in Turing's work" revisited.

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)
    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: Why Turing Hadn't Thought of Using His Machines for Biological Systems
  2. (with C.W. Wardlaw) A Diffusion Reaction Theory of Morphogenesis in Plants (in the Collected Works, a version appearing in a paper by Wardlaw: A commentary on Turing's diffusion-reaction theory of morphogenesis, New Phytol. 52, pp 40-47)
  3. 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
    Jonathan Swinton: Turing's Life in Pictures: the Search for Fibonacci
    Aaron Sloman: Evolution of Biological Virtual Machinery - Report on work in progress, related to presentations, supervenience and causation in virtual machinery
  4. Finally, the short piece on: Outline of the Development of the Daisy

Other commentaries from:
Floridi, Gessler, Millican, Richards, Swinton.

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