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
Assume you have a neural network performing some real-valued transformation. Does a downstream neural network, which is sensitive to such real values, count as an observer?
I would also like to comment on the last sentence. It seems that there may be a difference between usable and observable in this context. One could certainly have a real-valued voltage or current along some wire (or axon), and “use” that real value to manipulate other parts of the system. But I take “observing” to mean that a value has a computable digital representation that can be determined by an observer, such that this representation (or, in other words perhaps, the “name” of this value) could be used as the input to some other computation.
I think that if you define computation such that the values upon which it operates must be usable and observable by humans, then there simply could not be computations on a large set of values that seem important to physical theory. For example, it is not clear that the value of pi or the Euler constant are observable: although they are computable, one cannot observe them in their entirety.
A potentially more serious issue would be to produce a definition of “observable” that didn’t preclude the very possibility of having non-Turing computable inputs to a computation. If one cannot have inputs that are not Turing-computable in the first place, then one cannot, just by definition, have so-called hypercomputations.
Another separate issue is how computations in Turing machines and possible physical computations “match up.” For instance, some physical processes, like protein folding, are not tractable by digital/discrete algorithms, suggesting the possibility that the physical process is not operating under the description of such an algorithm. However, such a process is still computable; the algorithm is just inefficient compared to however it is actually done in the real world. This seems to present a separate kind of problem for the Physical CT Thesis, but I’m not sure how serious.
In the paper, I am talking about ordinary human observers. I suppose you could extend the argument to a broader notion of observer, including neural networks. But I would say that an observer in this sense must retain the feature of ordinary observers that they can tell the difference between different observations. That is, for two observations to count as different, the observer must be able to discriminate between the two.
I’m sorry for using “usable” out of context. By “usable”, I mean usable for learning the values of a function that is specified independently of running the process (e.g., addition). In this sense, observability is a necessary condition for usability.
Things seem to get tricky, then. Since realistic neural network models are continuous, it seems we have non-Turing physical computations going on. The big question, for your purposes, is whether such continuity extends to the computational properties of the system. Since a neural network can (trivially) implement the identity function, it seems that in some cases we would want to describe the computations as operating over the reals.
One issue is noise in such continuous systems. All real physical systems have noise. Because of this, it is possible to describe the system using a discrete set of states. While this implies that any real physical system can be modelled using discrete math, it is a discrete approximation to a continuous (noisy) system.
I’m not sure if this is a good thing or a bad thing, but wouldn’t the contstraints you introduce regarding useability and observability entail that there could be no evidence for the proposition that “nature contains real-valued quantities that vary along a continuum”?
My constraints are on what counts as physical computation. I am not placing constraints on what counts as evidence for a physical theory. Nevertheless, independently of discussions of physical computation, there is a good question to ask: what counts as evidence for the proposition that nature contains real-valued quantities that vary along a continuum? As far as I know, there is no known direct way to confirm or disconfirm such a proposition. The best we can do is formulate physical theories that either entail this proposition or its negation and see which ones do best at fitting all the evidence we have.