Either the human mathematical mind cannot be captured by an algorithm, or there are absolutely undecidable problems [1, p. 310].
This is the statement of Gödel’s Disjunction, quoted on page 1 of the book, a consequence which he drew from his incompleteness theorems. Gödel believed that the first part of the disjunction was true and the second false. Another view (expounded by Penrose and Lucas but not generally accepted) is that the incompleteness theorems indicate or even prove that the human mind surpasses any machine. The book presents a series of largely self-contained articles and papers which emerged from two workshops held at Bristol University in 2012 and 2013 to explore the disjunction and get nearer the truth of the disjuncts. It is organised in three parts: Part I contributes to the understanding of key notions of algorithm, consistency and knowability. Part II is concerned with the first disjunct and Part III with the second. There are twelve contributors including the editors. Many of the arguments are informal but make use of formal results, for example provability within a given formal system can be precisely defined but ‘absolute provability’, although meaningful, is less rigorous as a mathematical concept. There is a crucial problem of definition here – as Emil Post argued in 1954: ‘prior to a definition of absolute provability, a definition of absolute definability is required’ (p. 240). The Church-Turing thesis equates a concept of computability by a Turing machine (a well-defined idealised computer) or other algorithmic device with the informal notion of effective computability. Gödel’s theorems tell us that in any axiomatic system that includes arithmetic there will be true but unprovable statements. Furthermore the consistency of such a system in not provable within that system. On the other hand the consistency of arithmetic has to be taken to be true – otherwise we could prove that 2 = 1! To investigate the issues important logical and philosophical ideas are required. One is Shapiro’s Epistemic Arithmetic – which includes a notion of ‘knowability’ or absolute provability. This is turn is an interpretation of Heyting (Intuitionist) Arithmetic. In Chapter 2 by Walter Dean, Algorithms and the Mathematical Foundations of Computer Science, there is some discussion of practical examples of algorithms and their implementation: the Merge-Sort algorithm, the Lucas-Lehmer test for primality as well as various programming languages. Most intriguing was Chapter 10 by Timothy Williamson, Absolute Provability and the Safe Knowledge of Axioms, in which he suggests that alternative creatures, possibly non-human, might adopt different axioms which to them appear intuitively obvious because ‘their brains have come to be wired so strongly’ by evolution. (p. 246). Possibly the ideas in these chapters could have been developed further to explore whether the structure of the human brain has any bearing on the problem of what is humanly knowable, and to what extent future computer developments, perhaps in quantum computing or artificial intelligence, might change our understanding of algorithms. This is a demanding text suitable for students or researchers of Mathematical Logic at postgraduate level. The more general mathematician will need to do some homework, but will be well rewarded for their efforts. Each chapter is well written and thoroughly referenced, however a glossary of notation would have been useful. Overall it does shed light on the intersection between Mathematical Logic and the Philosophy of Mathematics. Gödel’s Disjunction remains unresolved with the impression that it may itself be an undecidable problem. REFERENCE Gödel, K. (1995) Some basic theorems on the foundations of mathematics and their implications, in S. Feferman et al. (eds) Kurt Gödel. Collected Works. Volume III: Unpublished Essays and Lectures, Oxford University Press, pp. 304-323 (originally published 1951). Francis McGonigal CMath MIMA Book review first published in Mathematics Today April 2018 Published 15th March 2019