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.
Paul Cockshott, University of Glasgow
Allin Cottrell, Wake-Forest University
Lewis Mackenzie, University of
Glasgow
Greg Michaelson, Heriot-Watt
University
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, 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 and Greg Michaelson, `Tangled Tapes:
Infinity, Interaction and Turing Machines′, Turing Centenary Conference:
CIE 2012 - How the World Computes, Cambridge, June 2012 PDF of full paper
Paul Cockshott, ′Turing: the irruption of materialism
into thought′, OUPBlog, July 2012 - also at Nature:
soapboxscience
J. Davidson and G. Michaelson, `Brute force is not ignorance′,
Computability in Europe 2013, Milan, June, 2013 PDF
G. Michaelson, ′SKI combinators (really) are Turing
complete′, Glasgow, November 2014 - PPTX
`Letter to the editor′, FACS FACTS, Issue 2016-2,
December 2016, pp8-13 - PDF
J. Davidson and G. Michaelson, `Expressiveness, meanings and
machines′, Computability, 2018 - to appear - PDF
Paul Cockshott, `Turing and Thought′, May 2018 - video
K.
Kolozova, P. Cockshott and G. Michaelson, `Defending
Materialism. The Uneasy History of the Atom in Science and Philosophy', Bloomsbury, 2024 here
G.
Michaelson, Logic & Materialism here - original
Chapters 7-10 of `Defending Materialism'