Limits to Computability

In the late 1930’s, the UK mathematician Alan Turing established fundamental limits to what we can reasonably expect to know about computations. Turing invented a very simple model of computation called a Turing Machine (TM), which uses a set of rules (quintuplets) to process a sequence of data symbols (tape). Turing explored the seemingly simple question of whether it’s possible to tell if an arbitrary TM will ever stop processing an arbitrary tape, and concluded that it is not possible: the Halting Problem for TMs is undecidable.

TMs have been shown to be equivalent to contemporary computer systems and programming languages, so this result has deep implications for what we can and can’t do with computers. For example, if we can’t tell whether or not an arbitrary program ever terminates then we can’t know in advance how long it will run for or how much memory it will need or how much power it will consume. We also can’t tell whether or not two arbitrary programs actually carry out the same computation. Of course it is possible to solve these problems for particular programs, it just isn’t possible in general.

People still question Turing’s results and try to come up with ways round them. For example, attempts are made to develop new mathematical characterisations of computation (e.g. “hypercomputation” or “superTuring”) that are more powerful than TMs, or to design hardware systems based on novel ideas from physics that can overcome apparent physical limitations to TMs. On the other hand, people also misuse Turing’s results to argue that human beings are necessarily more powerful than computers because they don’t share these limitations, or that there are fundamental limits to particular forms of rule based human activity, such as economic planning.

We are very interested in exploring and challenging such claims. While we are certainly open to new ways of looking at the world, we think that all the evidence shows that Turing’s results say something deep and fundamental about the limits to computability just as the laws of physics place fundamental constraints on how material reality works. Our publications include:

G. Michaelson and P. Cockshott, `Constraints on Hypercomputation', in A. Beckmann et al (Eds), Logical Approaches to Computational Barriers: Proceedings of Computability in Europe 2006, Swansea, Springer, LNCS 3988, pp378-387, July 2006. PDF

P. Cockshott and G. Michaelson, `Are there new models of computation: a reply to Wegner and Eberbach', Computer Journal, Vol 50, No 2, pp232-247, 2007 PDF

P.Cockshott, L. Mackenzie and G. Michaelson, `Physical constraints on hypercomputation', Theoretical Computer Science (A), Vol. 394, No 3, April 2008, pp159–174 PDF

A. Cottrell, P. Cockshott and G. J. Michaelson, `Is economic planning hypercomputational? The argument from Cantor diagonalisation', International Journal of Unconventional Computing - Special Issue: Future Trends in Hypercomputation, Volume 5, Number 3-4, 2009, p223-236 PDF Russian PDF

P. Cockshott, A. Cottrell, G. Michaelson, I. Wright and V. Yakovenko, `Classical Econophysics’, Routledge, 2010

P. Cockshott, L. Mackenzie and G. Michaelson, Non-classical computing: feasible versus infeasible, Proceedings of ACM-BCS Visions of Computer Science 2010, University of Edinburgh, April, 2010, to appear PDF

P. Cockshott, L. Mackenzie and G. Michaelson, `Computation and its limits’, Oxford University Press, 2012

Paul Cockshott, `Turing’s Universal Digital Computer’. British Mathematical Colloquium, Kent, April 2012 prezi

Greg Michaelson, `Limits to Computation, British Mathematical Colloquium’, Kent, April 2012 ppt

Greg Michaelson, `A Visit to the Turing Machine’

· CS4Fun, April 2012 here

· Take Tea With Turing, January 2013 – spoken word here

Paul Cockshott,’Turing: the irruption of materialism into thought’, OUPBlog, July 2012 – also at Nature: soapboxscience

Paul Cockshott, University of Glasgow

Allin Cottrell, Wake-Forest University

Lewis Mackenzie, University of Glasgow

Greg Michaelson, Heriot-Watt University