# Alan Turing: His Work and Impact

## 1st Edition

**Editors:**S. Cooper J. van Leeuwen

**eBook ISBN:**9780123870124

**Hardcover ISBN:**9780123869807

**Imprint:**Elsevier Science

**Published Date:**3rd May 2013

**Page Count:**944

## Description

In this 2013 winner of the prestigious R.R. Hawkins Award from the Association of American Publishers, as well as the 2013 PROSE Awards for Mathematics and Best in Physical Sciences & Mathematics, also from the AAP, readers will find many of the most significant contributions from the four-volume set of the *Collected Works of A. M. Turing*. These contributions, together with commentaries from current experts in a wide spectrum of fields and backgrounds, provide insight on the significance and contemporary impact of Alan Turing's work.

Offering a more modern perspective than anything currently available, *Alan Turing: His Work and Impact* gives wide coverage of the many ways in which Turing's scientific endeavors have impacted current research and understanding of the world. His pivotal writings on subjects including computing, artificial intelligence, cryptography, morphogenesis, and more display continued relevance and insight into today's scientific and technological landscape. This collection provides a great service to researchers, but is also an approachable entry point for readers with limited training in the science, but an urge to learn more about the details of Turing's work.

## Key Features

- 2013 winner of the prestigious R.R. Hawkins Award from the Association of American Publishers, as well as the 2013 PROSE Awards for Mathematics and Best in Physical Sciences & Mathematics, also from the AAP
- Named a 2013 Notable Computer Book in Computing Milieux by
*Computing Reviews* - Affordable, key collection of the most significant papers by A.M. Turing
- Commentary explaining the significance of each seminal paper by preeminent leaders in the field
- Additional resources available online

## Readership

Researchers and scientists interested in the context and significance of Turing's impact on artificial intelligence, artificial neural networks, morphogenesis, cryptology, the philosophy of mind, mathematics, computing, computer science, informatics, morphogenesis, philosophy and the wider scientific world.

## Table of Contents

List of Contributors

Introduction

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

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

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

Part IV. The mathematics of emergence: the mysteries of morphogenesis

Alan Mathison Turing by Max Newman

Andrew Hodges Contributes: A Comment on Newman’s Biographical Memoir

Alan Mathison Turing: 1912–1954

On Computable Numbers, with an Application to the Entscheidungsproblem – A Correction

Christos Papadimitriou on — Alan and I

On Computable Numbers, with an Application to The Entscheidungsproblem

On Computable Numbers, With an Application to The Entscheidungsproblem. A Correction

Examining the Work and Its Later Impact: Stephen Wolfram on — The Importance of Universal Computation

Martin Davis Illuminates — Three Proofs of The Unsolvability of The Entscheidungsproblem

Samson Abramsky detects — Two Puzzles About Computation

Paul Vitanyi Illustrates the Importance of — Turing Machines and Understanding Computational Complexity

Gregory Chaitin traces the path — From the Halting Problem to the halting probability

Robert Irving Soare expands on — Turing and the Art of Classical Computability

Rainer Glaschick takes us on a trip back to — Turing Machines in Munster

From K. Vela Velupillai — Reflections on Wittgenstein’s Debates with Turing during his *Lectures on the Foundations of Mathematics*

Jan van Leeuwen and Jin Wiedermann on — the computational power of turing’s Non-Terminating Circular A-Machines

Meurig Beynon puts an empirical slant on — Turing’s Approach to Modelling States of Mind

Henk Barendregt and Antonio Raffone explore — Conscious Cognition as a Discrete, Deterministic and Universal Turing Machine Process

Aaron Sloman develops a distinctive view of — Virtual Machinery and Evolution of Mind (Part 1)

Artur Ekert on the physical reality of —

Cristian Calude, Ludwig Staiger and Michael Stay on — Halting and Non-Halting Turing Computations

Philip Welch leads us — Toward the Unknown Region: On Computing Infinite Numbers

On Computable Numbers, with an Application to the Entscheidungsproblem by A. M. Turing – Review by: Alonzo Church

Andrew Hodges finds significance in — Church’s Review of Computable Numbers

Computability and *λ*-Definability

Henk Barendregt, Giulio Manzonetto and Rinus Plasmeijer trace through to today — The Imperative and Functional Programming Paradigm

Computability and *λ*-Definability

The -Function in λ-*K* Conversion

Henk Barendregt and Giulio Manzonetto point out the subtleties of —Turing’s Contributions to Lambda Calculus

The -Function in λ-*K*-Conversion

Systems of Logic Based on Ordinals

Solomon Feferman returns to —Turing’s Thesis: Ordinal Logics and Oracle Computability

Systems of Logic Based on Ordinals

Examining the Work and Its Later Impact: Michael Rathjen looks at — Turing’s ‘Oracle’ in Proof Theory

Philip Welch takes a set-theoretical view of — Truth and Turing

Alastair Abbott, Cristian Calude and Karl Svozil describe — A Quantum Random Oracle

Practical Forms of Type Theory

Some background remarks from Robin Gandy’s — Preface

Practical Forms of Type Theory

The use of Dots as Brackets in Church’s System

Lance Fortnow discovers — Turing’s dots

The Use of Dots as Brackets in Church’s System

The Reform of Mathematical Notation and Phraseology

Stephen Wolfram connects — Computation, Mathematical Notation and Linguistics

The Reform of Mathematical Notation and Phraseology

Examining the Work and Its Later Impact: Juliet Floyd explores — Turing ,Wittgenstein and Types: Philosophical Aspects of Turing’s ‘The Reform of Mathematical Notation and Phraseology’ (1944–5)

On the Gaussian error function

Sandy L. Zabell delivers an authoritative guide to — Alan Turing and the Central Limit Theorem

Turing’s ‘Preface’ (1935) to ‘On the Gaussian error function’

Some Calculations of the Riemann Zeta function: On a Theorem of Littlewood

Dennis Hejhal and Andrew Odlyzko take an in-depth look at — Alan Turing and the Riemann Zeta function

And Dennis Hejhal adds — A Few Comments About Turing’s Method

Some Calculations of the Riemann Zeta-Function

On A Theorem of Littlewood

Solvable and Unsolvable Problems

Gregory Chaitin recommends — Turing’s Small Gem

Solvable and Unsolvable Problems

Examining the Work and Its Later Impact: **Wilfried Sieg focuses on —** Normal Forms for Puzzles: AVariant of Turing’s Thesis

**K. Vela Velupillai connects –**: Turing on ‘ Solvable and Unsolvable Problems’ and Simon on ‘Human Problem Solving’

The Word Problem in Semi-Groups with Cancellation

Gregory Chaitin on — Finding the Halting Problem and the Halting Probability in Traditional Mathematics

While John L. Britton gives us a brief – Introduction to the mathematics

The Word Problem in Semi-Groups with Cancellation

On Permutation Groups

John Leslie Britton’s informative — Introduction

On Permutation Groups

Rounding-off Errors in Matrix Processes

Lenore Blum brings into view —Alan Turing and the Other Theory of Computation

Rounding-Off Errors in Matrix Processes

A Note on Normal Numbers

Andrew Hodges on an interesting connection between — Computable Numbers and Normal Numbers

A Note On Normal Numbers

Examining the Work and Its Later Impact Verónica Becher takes a closer look at — Turing’s Note On Normal Numbers

Turing’s Treatise on the Enigma (Prof’s Book)

Frode Weierud on Alan Turing, Dilly Knox, Bayesian statistics, decoding machines and — Prof’s Book: Seen in the Light of Cryptologic History

Excerpts from the ‘Enigma Paper’

Further Aspects of the Work and Its History Tony Sale delves into the cryptographic background to — Alan Turing, the Enigma and the Bombe

Klaus Schmeh looks at – Why Turing Cracked the Enigma and the Germans Did Not

Speech System ‘Delilah’ – Report on Progress

Andrew Hodges Sets the Scene For — The Secrets of Hanslope Park 1944–1945

Top Secret: Speech System ‘Delilah’ – Report on Progress

Examining the Work and Its Later Impact: Craig Bauer presents — Alan Turing and Voice Encryption: A Play in Three Acts

John Harper reports on the — Delilah Rebuild Project

Checking a Large Routine

Cliff B. Jones gives a modern assessment of — Turing’s “Checking a Large Routine”

Friday, 24th June. Checking a large routine. by Dr. A. Turing

Excerpt from: Programmer’s Handbook for the Manchester Electronic Computer Mark II: Local Programming Methods and Conventions

Toby Howard describes — Turing’s Contributions to the Early Manchester Computers

Excerpt from: Programmer’s Handbook for the Manchester Electronic Computer Mark II

Turing’s Lecture to the London Mathematical Society on 20 February 1947

Anthony Beavers pays homage to —Alan Turing: Mathematical Mechanist

Lecture to the London Mathematical Society on 20 February 1947

Intelligent Machinery

Rodney A. Brooks and — The Case for Embodied Intelligence

Intelligent Machinery

Examining the Work and Its Later Impact: Christof Teuscher proposes — A Modern Perspective on Turing’s Unorganised Machines

Nicholas Gessler connects past and future — The Computerman, the Cryptographer and the Physicist

Stephen Wolfram looks to reconcile — Intelligence and the Computational Universe

Paul Smolensky asks a key question — Cognition: Discrete or Continuous Computation?

Tom Vickers recalls — Alan Turing at the NPL 1945–47

Douglas Hofstadter engages with — The Gödel–Turing Threshold and the Human Soul

Computing Machinery and Intelligence

Gregory Chaitin discovers Alan Turing ‘The Good Philosopher’ at both sides of — Mechanical Intelligence Versus Uncomputable Creativity

Computing Machinery and Intelligence

Examining the Work and Its Later Impact: Daniel Dennett is inspired by — Turing’s “Strange Inversion of Reasoning”

Aaron Sloman draws together —Virtual Machinery and Evolution of Mind (Part 2)

Mark Bishop examines — The Phenomenal Case of the Turing Test and the Chinese Room

Peter Millican on recognising intelligence and — The Philosophical Significance of the Turing Machine and the Turing Test

Luciano Floridi brings out the value of — The Turing Test and the Method of Levels of Abstraction

Aaron Sloman absolves Turing of —The Mythical Turing Test

David Harel proposes — A Turing-Like Test for Modelling Nature

Huma Shah engages with the realities of — Conversation, Deception and Intelligence: Turing’s Question-Answer Game

Kevin Warwick looks forward to — Turing’s Future

Digital Computers Applied to Games

Alan Slomson introduces — Turing and Chess

Digital Computers Applied to Games

Examining the Work and its Later Impact: David Levy delves deeper into — :Alan Turing on Computer Chess

Can Digital Computers Think?: Intelligent Machinery: A Heretical Theory: Can Automatic Calculating Machines Be Said To Think?

B. Jack Copeland introduces the transcripts — Turing and the Physics of the Mind

Can Digital Computers Think?

Intelligent Machinery: A Heretical Theory

Can Automatic Calculating Machines be Said to Think?

Examining the Work and Its Later Impact: Richard Jozsa takes us forward to — Quantum Complexity and the Foundations of Computing

The Chemical Basis of Morphogenesis

Peter Saunders introduces — Alan Turing’s Work in Biology

And Philip K. Maini wonders at — Turing’s Theory of Morphogenesis

The Chemical Basis of Morphogenesis

Examining the Work and Its Later Impact Henri Berestycki on the visionary power of – Alan Turing and Reaction–Diffusion Equations

Hans Meinhardt focuses on — Travelling Waves and Oscillations Out of Phase: An Almost Forgotten Part of Turing’s Paper

James D. Murray on what happened — After Turing – The Birth and Growth of Interdisciplinary Mathematics and Biology

Peter T. Saunders observes Alan Turing — Defeating the Argument from Design

Stephen Wolfram fills out the computational view of — The Mechanisms of Biology

K. Vela Velupillai connects — Four Traditions of Emergence: Morphogenesis, Ulam-von Neumann Cellular Automata, The Fermi-Pasta-Ulam Problem, and British Emergentism

Gregory Chaitin takes the story forward — From Turing to Metabiology and Life as Evolving Software

The Morphogen Theory of Phyllotaxis: I. Geometrical and Descriptive Phyllotaxis: II. Chemical Theory of Morphogenesis: III. (Bernard Richards) A Solution of the Morphogenical Equations for the Case of Spherical Symmetry

Bernard Richards recalls Alan Turing and — Radiolaria: the Result of Morphogenesis

The Morphogen Theory of Phyllotaxis: Part I. Geometrical and Descriptive Phyllotaxis

Part II. Chemical Theory of Morphogenesis

Part III. A Solution of the Morphogenetical Equations for the Case of Spherical Symmetry

Examining the Work and Its Later Impact: Peter Saunders comments on the background to —: Turing’s Morphogen Theory of Phyllotaxis

Jonathan Swinton explores further —: Turing, Morphogenesis, and Fibonacci Phyllotaxis: Life in Pictures

Aaron Sloman travels forward to —: Virtual Machinery and Evolution of Mind (Part 3): Meta-Morphogenesis: Evolution of Information-Processing Machinery

Outline of the Development of the Daisy

Jonathan Swinton’s updating of the texts — An Editorial Note

Outline of the Development of the Daisy

Afterword

Einar Fredriksson Recalls the — History of the Publication of the Collected Works of Alan M. Turing

Mike Yates Writing in *The Independent*, Friday 24 November 1995 — Obituary: Robin Gandy

Bernard Richards shares with us — Recollections of Life In the Laboratory With Alan Turing

Bibliography

A Bibliography of Publications of Alan Mathison Turing

Index

## Details

- No. of pages:
- 944

- Language:
- English

- Copyright:
- © Elsevier Science 2013

- Published:
- 3rd May 2013

- Imprint:
- Elsevier Science

- eBook ISBN:
- 9780123870124

- Hardcover ISBN:
- 9780123869807

## About the Editor

### S. Cooper

Barry Cooper is Professor of Mathematical Logic at the University of Leeds. A graduate of the University of Oxford, his research follows that of Alan Turing in its focus on the nature of mental and physical computation. Author and editor of numerous books, including Computability Theory, New Computational Paradigms, and Computability in Context, he is a leading advocate of multidisciplinary research at the interface between what is known to be computable, and theoretical and practical incomputability. For more information, http://www1.maths.leeds.ac.uk/.

### Affiliations and Expertise

Professor of Mathematical Logic, University of Leeds, Leeds, UK

### J. van Leeuwen

Jan van Leeuwen is professor at the Department of Information and Computing Sciences at Utrecht University. He received a Ph.D. in mathematics in 1972 from the same institution. After having held several positions in computer science in the US, he returned to Utrecht as a faculty member in 1977. He was head of department from 1977 to 1983 and from 1991 to 1994, and served as dean from 1994 to 2009. His research interests extend to many branches of the theory and philosophy of computer science. He is a member of the Academia Europae, is the first recipient of a Distinguished Lorentz Fellowship Prize in the Netherlands, and holds an honorary doctorate from RWTH Aachen University. For more information, http://www.cs.uu.nl/staff/jan.html.

### Affiliations and Expertise

Professor of Computing Science, Utrecht University, The Netherlands

## Awards

2013 PROSE Awards - Winner, Award for Excellence in Physical Sciences and Mathematics: Association of American Publishers, Alan Turing: His Work and Impact PROSE Award 2013, Book: Mathematics, American Association of Publishers PROSE Award 2013, Book: Best in Physical Sciences & Mathematics, American Association of Publishers PROSE Award 2013, R.R. Hawkins Award, American Association of Publishers Notable Computing Books 2013: Computing Milieux, Computing Reviews

## Reviews

“The ‘tour de force’ is that it is quite possible, even recommended, to read the book not linearly but by selecting pieces randomly, just for fun…We…urge readers of this brief review to read the book. We are sure that they will definitely enjoy it. It is quite possible that they will also find there ideas or flashes of inspiration for their own research.”*--EMS Newsletter*,June-2014

"It is a rather remarkable achievement that the editors have managed to engage so many leading figures, 70 of them in all, and with such evident commitment…It is a fitting tribute to Turing's legacy*…"--**LMS Newsletter,*October 1 2013

"This thick volume is a collection of Turing’s most significant papers along with commentary by people that appreciated and furthered his ideas. What will astound even the people that know the work of Turing is the breadth of his interests and depth of his competence."--*MAA.org,* Jan 2 2014

"There is a lot to be learned from his outlook and temperament, and *Alan Turing: His Work and Impact* can serve as both an instructional and an inspirational text."--*Notices of the AMS,* Sep 1 2014

"The massive volume is a collection of Turing's key publications as well as commentaries about the papers. The volume is organized in four parts, with each section arranged by publication year of the papers…Given the number of minds involved in this undertaking, the editors must be congratulated…Summing Up: Highly recommended*."--**CHOICE Reviews Online,* December 2013

"The volume is an excellent introduction to many exciting topics that Turing greatly contributed to, and in some cases founded, from computability theory to programming languages, complexity theory, the philosophy of mind, artificial intelligence, and the emergence of structure in biology…Readers of almost any background and any level will find something fascinating, something to capture their imaginations, in this volume."--*ComputingReviews.com,* September 17, 2013

"Introductions and commentaries are written by outstanding specialists in the given domains -- altogether by 70 contributors. They provide insight into the significance and contemporary impact of Turing's work…The book is published in a beautiful and careful way. It is a remarkable contribution to the celebration of the centenary of Alan Turing's birth. It is indispensable for all interested in Turing's work."--

**Zentralblatt MATH 1270-2013**

"…much of what’s presented is for specialists…But there’s still plenty even for a non-mathematician like me, some of it surprisingly moving…no matter how well you know the life and work of Turing, you’ll learn something from this book."--

*OECD Insights blog,*August 26, 2013"This accessible book is an essential read for those interested in Turing’s work and provides a more contemporary perspective than anything else that is available."--

*CyberTalk,*September 2013*"*This volume contains a mix of writings — some excerpts by Turing, but mostly writings about him and his work by those who understand his genius and his legacy. The writings include first person narratives of what he was like and what it was like to work with him, personal accounts of career-changing encounters with his thinking, and commentary on particular aspects of his work."--

*Reference and Research Book News,*August 2013*"The new testament of computer science has come, 101 years after the birth of founding prophet Alan Turing…How big is the incomputable universe? Can digital machines think? Do daisies emerge from pure chemistry? If your soul craves answers to such questions, this is your new bible."--*

**"**

*Nature,*June 19, 2013**makes Turing's most important papers readily accessible and affordable. With the four volumes of the previously published "Collected Works" now scarce and very expensive, this volume fills a pressing need in Turing scholarship. Moreover, the commentaries associated with Turing's papers in this volume offer new and compelling insights into the continuing importance and relevance of Turing's work, contextualizing it in contemporary contexts and providing richly elaborated explanations of how and why Turing's work remains seminal for a wide variety of fields, including computational science, cognitive science, artificial intelligence and more." --**

*Alan Turing: His Work and Impact*

**N. Katherine Hayles, Professor of Literature, Duke University**