Books : reviews

Paul Cockshott, Lewis M. Mackenzie, Greg Michaelson.
Computation and its Limits.
OUP. 2012

rating : 2.5 : great stuff
review : 30 December 2013

Computation and its Limits is an innovative cross-disciplinary investigation of the relationship between computing and physical reality. It begins by exploring the mystery of why mathematics is so effective in science and seeks to explain this in terms of the modelling of one part of physical reality by another. Going from the origins of counting to the most blue-skies proposals for novel methods of computation, the authors investigate the extent to which the laws of nature and of logic constrain what we can compute. In the process they examine formal computability, the thermodynamics of computation, and the promise of quantum computing.

One of my research interests is unconventional computation: systems that use non-standard approaches to perform computation. This is partly in the hope we might find something more powerful that we already have, but mostly because it is more fruitful to examine an upper limit barrier from both sides rather than just from below. It is, unfortunately, a research area where a lot of nonsense can be heard, often because researchers from one discipline extrapolate their results incorrectly in another discipline.

So it is very refreshing to see a book that examines many of these issues, explaining precisely where the problems in many proposed unconventional computers lie. It covers many topics, and is essentially discussing the difference between proposed computational models and the constraints of the implementing physics. Many (all?) unconventional computational models are simply unphysical, in a range of different ways.

The discussion starts with mechanical computers, going all the way back to the ancient Greek Antikythera mechanism, a special purpose astronomical computer. As well as the usual discussion about gear ratios, and so on, the authors provide a fascinating speculation about why the Greeks preferred to model eccentric circular orbits rather than elliptical ones: it made their computers easier to build!

p33. It is easier to construct an eccentric coupling … than it is to make a direct mechanical implementation of Kepler’s law. The choice of model proposed by the Greek astronomers to explain the lunar orbit may thus have been influenced by what they could feasibly build into a computer. Appollonius of Perga, who proposed the eccentric model for lunar orbits, also developed the theory of ellipses in his work on conic sections, so he would have been well equipped to propose ellipses as a basis for orbits. The preference of the Greek astronomers for circular motions might have been influenced by a concern for mechanization.

There is a lot of good discussion here of analogue computers, and the role of real numbers. Some researchers claim that the continuous real numbers have more computational power than discrete integers, and that therefore analogue computers (based on reals) have more computational power than discrete digital computers. The authors dismiss this with two separate arguments. (i) Even if a physical system implements real numbers, there is no way to access the result to the infinite precision needed (indeed, no more than a few decimal places are possible). (ii) More seriously, such researchers are confusing the model, formulated in terms of real numbers, and physical reality; the model is only ever an approximation to reality:

pp.84-5. In an actual analogue computer, these operators have to be implemented by some apparatus the effect of which is analogous to that of the mathematical operator. The analogy is never exact. Multipliers turn out to be only approximately linear, adders show some losses, and so on. All of these mean that even if the variables were perfect representations of the abstract concept of real numbers, the entire apparatus would only perform to bounded accuracy.

I repeat: The analogy is never exact.

There is also a lot of excellent discussion of thermodynamic limits, and quantum limits, and systems that demand Newtonian physics in order to display their promised properties. Finally, the authors take some specific hypercomputer proposals, and dissect them, showing where they break down.

This book should be read by anyone proposing a new kind of unconventional computation. It will stop them falling into some of the most common errors.