Limits to
Computability
In the late
1930’s, the
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:
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, 2011
Paul Cockshott,
Allin Cottrell,
Lewis Mackenzie,
Greg Michaelson,