A topic that has received increasing attention in the last few years is hypercomputation (see also the Wikipedia article), a term coined by Jack Copeland for the computation of functions that are not computable by Turing machines. Real numbers are often invoked in recipes for hypercomputation. I have tried to explain my skepticism about such recipes in a paper I’ve just written on the Physical Church-Turing thesis (cf. previous post).
The following is a brief excerpt from my paper in which I try to motivate my concern with unrestricted appeals to real numbers in attempts at finding recipes for hypercomputation. I’d be interested in knowing whether what I say strikes people as reasonably intelligible and sound.
(Definition: Physical CT = Physical Church-Turing thesis, i.e., the thesis that what can be computed by physical systems can be computed by Turing machines.)
Many of our physical theories assume that nature contains real-valued quantities that vary along a continuum. These may include the velocity of objects, the coordinates that define the position of their center of gravity in the spacetime manifold, and more. If these physical theories are correct, then many properties of many entities take arbitrary real numbers as their values. And most real numbers in any continuous interval are Turing-uncomputable. In fact, there are only countably many computable numbers, but any continuous interval contains uncountably many real numbers. Thus, the probability that a randomly picked real-valued quantity is computable is zero. Hence, if our physical theories are correct, most transformations of the relevant physical properties are transformations of Turing-uncomputable quantities into one another. For instance, an object’s change of speed, or even its simple change of spatial location are, in general, transformations of one Turing-uncomputable real-valued quantity into another. But a transformation of one Turing-uncomputable value into another Turing-uncomputable value is certainly a Turing-uncomputable operation. Hence, it would seem that given many of our physical theories, the physical world is chock-full of operations that outstrip the power of TMs. Does this falsify
The problem lies in the unconstrained appeal to operations defined over real numbers, or equivalently, real-valued physical quantities, in formulating