The Limits of Computation

Apostolos Syropoulos goes back to BASICs to consider whether the human brain is a computer.

- Apostolos Syropoulos

There is a school of thought that assumes that all intellectual problems can potentially be solved by computers [for example, see ‘The Future of Philosophy is Cyborg’, by Phil Torres in Issue 141]. However, is this really the case? Here I will try to explain why we do not know where the limits of computability are, and how this lack of knowledge affects our understanding in a number of areas.

Roughly, we can say that a computable (or solvable) problem is any problem that can be solved by a finite set of simple actions. Alternatively, we could say that a computable problem is anything that can be reduced to a mathematical equation and solved accordingly. For example, if someone has to travel to a number of towns and has to schedule her trip so that she has to go through each town only once, this is a mathematical problem. One may say that at first this does not look like a mathematical problem; but we can reduce it to, or transform it into, a mathematical problem (in topology). And if the number of towns that our pilgrim has to travel is small enough, then it is relatively easy to compute an answer. But when the number of towns becomes large enough, then it might not be possible to come up with a road map that goes through each town only once.

Although there are a number of seemingly precise definitions of ‘computability’, it is an imprecise and vague notion. Nevertheless, one can use a Turing machine to rigorously define