Computation and its limits

Paul Cockshott, Lewis M. Mackenzie, Gregory Michaelson

Published by

OUP

ISBN

9780199640324

RRP

£35.00

Reviewed by

Patrick Hill CEng MBCS CITP

Score

8 out of 10

Given several decades of rapid technological advances and the current ubiquity of computing devices of various kinds, it is easy to suppose that the scope of possible computing applications and the potential evolution of supporting technologies are virtually limitless.

This book is a critical interdisciplinary survey of a wide range of topics relating to the history, nature, future and limitations of computation itself and of the devices, both real and imagined, that might be used to perform it.

The book starts with an investigation of the history of number and counting as representations of and operations on abstractions of real-world entities. The authors go on to consider the design and limitations of early mechanical computing devices and their more modern representatives, wherein the mechanical design of the computer implements the salient physical characteristics of the problems they are intended to solve.

Subsequent chapters consider the foundations of modern computing, such as propositional logic, set theory and predicate calculus, and also describe some of the paradoxes within these systems and implications for decidability.

Here also we meet Turing Machines and Lambda Calculus and develop the idea of general purpose, programmable computers along with an in-depth discussion of the physical and electrical limitations of electronic digital computers. The final three chapters of the book are concerned with more speculative areas of computing including quantum computing and hypercomputers.

Topics are discussed in depth and the material is challenging, particularly as it covers a wide range of disciplines such as mathematics, electronics and physics. In earlier chapters, concepts are lucidly explained in the text. However, in places, particularly in the chapter on quantum computing, the authors assume rather an advanced mathematical knowledge, and there is little supporting explanation. Thus the reader is required to find explanations elsewhere.

The chapters are quite lengthy and while a broad indication of chapter content is given at the start of the book and a listing of chapter sections is given at the head of each chapter, the chapters are usually without an introductory overview such that it can be easy to occasionally get lost in the detail. Most chapters also lack summaries or conclusions. I think these structural additions would have been useful in helping the reader to navigate through the diverse and complex material.

The nature of the subject matter and depth of exposition means this is not the easiest book to read and there are certainly sections that require multiple readings. Nonetheless, the book presents a fascinating and somewhat different perspective on computing, which should be of interest to a variety of readers, even if (like me), you don’t quite fully understand all of it.

Further information: OUP

September 2012