Computability in Context

- an annotated reading list -

"I didn't become a mathematician because mathematics was so full of beautiful and difficult problems that one might waste one's power in pursuing them without finding the central question" - Albert Einstein

Antonio Damasio: The Feeling Of What Happens: Body and Emotion in the Making of Consciousness, Harcourt, Orlando, FL., 1999.
Challenges many conventional views of the relationship between mind and body, and between emotions and thought processes. Many of the problems discussed resonate with familiar computability-theoretic problems of representation and the modelling of phase transitions and the role of emergent nonlocality.
Martin Davis: The Universal Computer - The Road from Leibniz to Turing, W. W. Norton, New York, London, 2000.
By prime-mover in the development of a negative solution to Hilbert's Tenth Problem. Relates the development of computers to underlying logical concepts, focussing particularly on the work and lives of Leibniz, Boole, Frege, Cantor, Hilbert, Gödel and Turing. Very readable.
David Deutsch: The Fabric of Reality, Allen Lane/Penguin, London, New York, 1997.
Cult book by a seminal figure in the development of quantum computing. Brings out the relationship between basic scientific issues and computability theoretic considerations. On balance, a more conservative view of the possible role of incomputability in nature.
Murray Gell-Mann: The Quark and the Jaguar: Adventures in the Simple and the Complex, Allen Lane/Penguin, London, New York, 1997.
By Nobel Prize winner, and key figure in the development of the quark model for elementary particle physics. Now closely associated with the paradigm-shifting community of scientists grouped around the Santa Fe Institute. This book, reflects Gell-Mann's thinking about such issues as emergence, complexity and the role of reductionism in science. Not directly about computability, but plenty to think about for those seeking to reduce the world to a Turing machine.
Jacques Hadamard: The Mathematician's Mind - The Psychology of Invention in the Mathematical Field, Princeton University Press, Princeton, New Jersey, 1945 and 1973.
A classic investigation of the role of unconscious processes in mathematical invention and other creative activity. Essential reading for anyone interested in theoretical models of human thinking. A good companion to Turing's 1939 paper, which approaches a similar agenda from a very different viewpoint, but with strikingly convergent conclusions.
Andrew Hodges: Alan Turing: The Enigma, Burnett Books/Hutchinson, London, 1983.
Classic biography of Alan Turing, by a former student of Roger Penrose. Packed with insights into Turing's life and scientific work - probably the most literary of the books on this list, and, though essential reading, a long and attention-demanding text. Particularly valuable for the way it brings out the ebb and flow of Turing's thought on different scientific issues, and how this thinking underpins and lends coherence to a whole range of current research agendas.
Douglas R. Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid, Harvester Press/Penguin Books, London, New York, 1979.
Popular book, hard to leave out, analysing the role and mechanics of feedback and self-reference in the construction of meaning out of simple mechanisms. Described by the author as "a metaphorical fugue on minds and machines in the spirit of Lewis Carroll", there is no denying its influence on thinking about artificial intelligence.
Steven Johnson: Emergence - The Connected Lives of Ants, Brains, Cities and Software, Scribner/Allen Lane, London, New York, 2001.
One of the few books on this list by a journalist, but none the worse for that. Taking Turing's work on morphogenesis as its starting point, it gives a descriptive guide to the ever widening relevance of emergence as a computational phenomenon. Gives plenty of food for thought for the computability theorist searching for mathematical models capable of capturing the underlying content of emergence in nature.
Thomas S. Kuhn: The Structure of Scientific Revolutions, University of Chicago Press, Chicago, London, 1962.
Hugely influential work - a case where "essential reading" means just that. And for a computability theorist, the book is also about the content of the science, not just the sociology.
David Leavitt : The Man Who Knew Too Much - Alan Turing and the Invention of the Computer W. W. Norton, New York, London, 2006.
Very readable, if not entirely reliable, introduction to Turing by a gay creative writing lecturer from Florida. Criticised by some reviewers (such as Andrew Hodges) for his over-emphasis on Turing's sexual orientation as an influence on his scientific work. But interesting and persuasive when he describes the psychological link between Turing and his computing machines.
Roger Penrose: The Emperor's New Mind - Concerning Computers, Minds, and the Laws of Physics, Oxford University Press, 1989.
A relatively readable book dealing with all sorts of computability-relevant topics, from Turing machines to the computability of the Mandelbrot set, and from Gödel's Incompleteness Theorem to quantum effects in the brain, and the predictability, or otherwise, of quantum phenomena.
Constance Reid: Hilbert, Springer-Verlag, New York, 1996.
Popular science writing at its best from the sister of Julia Robinson, a book by a non-mathematician that mathematicians can read and enjoy. Helps place the dramatic twentieth century developments in logic and computability within the context of earlier mathematical expectations.
Lee Smolin: The Trouble With Physics: The Rise of String Theory, The Fall of a Science, and What Comes Next, Houghton Mifflin, 2006.
Smolin's theme, that understanding the fundamental role of causality is basic to transcending gaps in the explanatory power of the standard model of particle physics, makes this readable book very relevant to the computability theorist. And even if that does not come through clearly, this is still an important update on the current state of "big science", and the need for a more radical analysis of how natural laws and physical constants emerge.
Doron Swade: The Cogwheel Brain - Charles Babbage and the Quest to Build the First Computer, Little, Brown and Co., London, 2000.
Story of the man who came close to building a universal calculating machine using nineteenth century engineering capabilities, and then was largely forgotten until the significance of his work was rediscovered in the computer age. Includes interesting material on Ada, Countess of Lovelace and daughter of Lord Byron, often credited with composing the first computer programme.


Compiled by Barry Cooper