A Review of the Hypercomputation Literature

A. Syropoulos, Hypercomputation: Computing Beyond the Church-Turing Barrier. New York, Springer, 2008.

There is now a wide range of proposals for physical (more or less) systems that purportedly compute functions that are not computable by Turing machines.  This new book reviews many proposals from the hypercomputation literature, such as infinite time Turing machines, interactive machines, Hogarth’s machines, etc.  There is even a chapter on “hyperminds”, i.e., the thesis that minds have hypercomputational powers.

This area is full of problems, some of which are physico/mathematical and some of which are conceptual.  Unfortunately, from a quick sample, Syropolous’s book does not avoid common mistakes and confusions–some of which I’ve been trying to correct in my own work.

This area of the literature has a long way to go before it is put on a sound footing.  There is lots of good work waiting to be done.