Alan Turing: His Work and Impact

This book is now published, June 2013

Book: Alan Turing  His Work and Impact
Editors: S Barry Cooper and Jan van Leeuwen
This book, published by Elsevier in the first half of 2013,
includes most of the writings of Turing from the 4
volume set of the Collected Works of A. M. Turing, published by
NorthHolland in 1992/2001, together with further items not previously included,
and a wide spectrum of accompanying
short commentaries from worldleading experts on the significance and
contemporary impact of the work. The book, originally intended to appear in time for
the 2012 centenary of Turing's birth in London, subsequently developed into
a project of huge magnitude and complexity, with 914 pages
of writings by over 70 contributors listed in a 9page contents section.
The book delivers a more modern perspective
than to be found so far in the literature; and gives 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 is extensively 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.
Forming a worthy contribution to the Turing Centenary and Turing's legacy, the book
presents 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 achieve this, the contributors of commentaries
have been chosen from many different fields and backgrounds, and
their pieces accompanying particular Turing items are generally
short, not more than 8 pages, and typically 3 to 5 pages.
The authors were encouraged
to be brief, concise, and lively in their presentation. Personal
viewpoints have been encouraged, 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 (provisional as at May 2012):
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 194344
( Practical forms of type theory II).
 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
 On Computable Numbers, with an Application to the
Entscheidungsproblem, Proc. Lond. Math. Soc. (2) 42, pp
230265 (1936)
+ ibid  correction,
Proc. Lond. Math. Soc. (2) 43, pp 544546 (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 clearcut
ChurchTuring 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 `quasiparadox'
of computation which runs parallel to the `quasiparadox 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 NonHalting 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 NonTerminating Circular AMachines
 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
 Church, A.,
Review of Turing 19367,
Journal of Symbolic Logic 2, p 42 (1937)
• Andrew Hodges:
Church's Review of
Computable Numbers  Comment on
Church's 'very significant' review
 Computability and λdefinability,
J. Symbolic Logic 2 pp 153163 (1937)
• Henk Barendregt, Giulio Manzonetto
and Rinus Plasmeijer:
The Imperative and Functional Programming Paradigm

functional vs
imperative programming
 The pfunction in λKconversion,
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 453455
• Henk Barendregt and Giulio
Manzonetto:
Turing's Contributions
to Lambda Calculus 
on the later importance of this work of Turing
 Systems of Logic based on Ordinals ,
Proc. Lond. Math. Soc (2) 45 pp 161228 (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 12001207
• 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

Practical Forms of Type Theory,
J. Symbolic Logic 13, pp 8094 (1948)
• Robin Gandy: Background remarks from
his Collected Works
PREFACE
to the paper
 The Use of Dots as Brackets in Church's
System, J. Symbolic Logic 7, pp 146156 (1942)
• Lance Fortnow: Turing's
Dots  insights into computer science
before there was computer science
 The Reform of Mathematical Notation
(194445, unpublished, in Collected Works)
• Juliet Floyd:
Turing, Wittgenstein and Types:
Philosophical Aspects of Turing's "The Reform
of Mathematical Notation and Phraseology" (19445)
• 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:

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
 A Method for the Calculation of the Zetafunction,
Proc. London Math. Soc. (2) 48 pp 180197 (1945, submitted 1939),
Some Calculations of the Riemann Zetafunction,
Proc. London Math. Soc. (3) 3 pp 99117 (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
 Solvable and Unsolvable Problems,
Science News 31, pp 723 (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.
 The Word Problem in Semigroups with Cancellation,
Ann. of Math. 52 (2), pp 491505 (1950)
• Gregory Chaitin:
Finding the Halting Problem and the Halting Probability in
Traditional Mathematics,
with
reference to
normal numbers, Part II, item 9
 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
 Roundingoff Errors in Matrix Processes,
Quart. J. Mech. Appl. Math. 1, pp 287308 (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)
 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
 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 193940; Alan's early days in the cottage
with Dilly Knox
 Also the innovative:
Speech System 'Delilah'  report on progress, 6 June 1944.
Threepage 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 129143 (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
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:
 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
 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ödelTuring
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
 Computing Machinery and Intelligence,
Mind 49, pp 433460 (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 Turinglike 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
questionanswer game
• Aaron Sloman:
The Mythical Turing Test
• Aaron Sloman:
Virtual Machinery and Evolution of Mind (Part 2)
• Kevin Warwick:
Turing's Future
 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
 Copeland has 3 interesting radio broadcasts from 195152. 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:
 The Chemical Basis of Morphogenesis,
Phil. Trans. R. Soc. London B 237 pp 3772 (1952),
(the famous 1952 paper)
•
Henri Berestycki:
Alan Turing and ReactionDiffusion 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 threecomponent systems. One needs the
threecomponent 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,
Ulamvon Neumann Cellular Automatas, the
FermiPastaUlam 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
 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
 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:
