Computation and its Limits

More than most people mathematicians (and physicists) are good with limits. Understanding the behaviour of a function, f(x), as x tends to zero (or infinity) is part of our early training. We also appreciate how an infinite sequence can tend towards a value, but never quite reach it. Given these insights it is perhaps surprising how little I had thought about limits in other contexts. As this text demonstrates limits can be subtle, important and interesting.

The book begins by considering the question, ‘What is computation?’. A deliberately broad interpretation of the term is used with, for example, the current collection of UK coins being considered as a ‘token-based computing system’. This opening is effective in distinguishing the notion of ‘computation’ from the physical objects that we call ‘computers’.

This distinction is further developed in the following chapter, which focuses on ‘mechanical computers’. A key example here is the Antikythera, a calendrical computer that has been dated to between 150 BC and 100 BC. As well as using this device to demonstrate how simple gears can perform operations like addition and multiplication, the authors discuss whether it is an example of an analogue or a digital computer. The initial reaction is that since it is not based on an electronic representation of ones and zeros it must be analogue. However, the use of gears means that calculations are conducted using ratios of integers, which is a feature of digital computers. In keeping with the book’s title, the authors also discuss some of the limits of analogue computers, which include the precision with which components can be manufactured.

Having begun by considering physical devices the authors move on to the theoretical ideas that underpin computation. A limit in this context is provided by a somewhat clumsy description of the Halting Problem, which demonstrates that we cannot determine whether a particular program will halt or run forever.

The authors return to practical considerations by considering, amongst other things, about the importance of minimising power usage, and hence heat, in modern computer chips. A short but enlightening analysis is provided, which suggests that, should current trends continue, by 2045 we may develop chips that consume the theoretical minimum amount of power (i.e. they reach the Landauer limit). Although 2045 may seem some distance in the future, as the authors note it is likely to be within the working careers of students reading the book.

Another potential limitation with computation arises from the possibility that real numbers may not actually exist. To most mathematicians, and probably most physicists, this may be anathema. However, if at the smallest scale the world is built from quanta, which cannot be subdivided, it may follow that nature imposes a fundamental limit to the accuracy with which numbers can be specified.

Sadly there are a number of misprints in the book. These include the comment, ‘This is easier to see with some of the earlier mechanical computers, so we pay attention’ – quite what we’re paying attention to is not made clear. Another, similarly intrusive, error is in the quoted axiom that ‘X + 0 = 0’. Whilst these errors do not significantly detract from the value of the book they nevertheless suggest limits in the editing process. Such limitations are also apparent in the way that the book concludes; it halts rather abruptly after a consideration of various hypercomputing proposals. Due to the varied topics that have been considered it would, I believe, have been useful to include a set of overall conclusions that re-enforced the book’s unifying theme.

These editing issues are a shame, for it is clear that the authors have a great deal of enthusiasm for their subject and they have carried this into the book – I can’t think of many other works that include ‘Tee Hee’ as a footnote. The book also raises a number of interesting issues, which deserve serious contemplation. A perseverant reader with a general interest in mathematics and/or computation will find rewards in this text, but I can’t help feeling that these rewards could have been greater and easier to find.

Book review published directly onto IMA website (June 2013)