Happy to see this made it to the front page. I submitted it because I'm hoping someone here will be able to understand it well enough to explain its significance. Is this Big News or a parlor trick? If it really is an example of an uncomputable physical process, that would seem to me to be earth-shattering, and yet this result does not appear to have made a splash. It is based on a construction of J. Myhill of a continuous recursive (and hence computable) function whose derivative is not computable. The proof is non-constructive, and it assumes the existence of a partially decidable set called A which somehow (this is the part I don't quite understand) results in a computable function despite the fact that its derivative can't be computable because that would imply A is decidable. Any clues would be much appreciated.
[UPDATE] Let me put this more succinctly: how is it possible that there can be a continuous computable function whose derivative is uncomputable? What exactly is it about this function that makes numerical differentiation fail?
[UPDATE2] Here is a link to the Myhill paper for easy reference.
The intuition seems to be that computability of a function is actually approximability, and derivatives can be large even when the function is very small, by having the large slope confined to a very small area. So by constructing a function f that contains an uncomputable (but recursively enumerable!) set encoded in the derivative by strategically placing little bumps, but having the bumps grow exponentially smaller, Myhill was able to construct a function that was easily approximable but whose derivative wasn't.
The key detail here is that the bumps grow exponentially smaller in the order the uncomputable set appears in its enumeration. This allows Myhill to construct a sequence of computable functions that (uniformly) approximate f to within 2^(-n). If the bumps weren't ordered in this way, we wouldn't know how far down the sequence to go to approximate f to within 2^(-n). The ordering lets us just look at the first n elements of the uncomputable set.
Why doesn't this allow us to approximate the derivative? Because at any x, we don't know how well we have to approximate f in order to approximate f'(x), so we need knowledge of the entire uncomputable set, which we cannot have.
> The key detail here is that the bumps grow exponentially smaller
Pedantically, it's that the bumps grow exponentially narrower.
IIUC, a simpler (but more nitpickable) version would be f'(n+1/y) = [the fraction of n-state Turing machines that halt within y steps] (for positive integers n, and 0 elsewhere); then f is the integral of f'. The value of f(x) can be approximated arbitrarily well by running every floor(x)-state Turing machine for a large finite number of steps[2], but f'(x) is equal to Chaitin's constant[0] for n-state Turing machines over a strictly-positive-length[1] subinterval of [n,n+1).
A much simpler version is f'(x) = {-1 if x<0; +1 if x>0; Chaitin's constant if x=0}. f(x) = abs(x).
Basically, this isn't even a parlor trick. It's a nothing burger, disguised as something by means of a parlor trick.
> Pedantically, it's that the bumps grow exponentially narrower.
Has to be smaller in both directions, right? It has to be vertically smaller to allow f to be computable, but horizontally smaller to keep f' large.
> IIUC, a simpler (but more nitpickable) version would be...
Here I think your f as defined is identically zero, and so you don't get f' by differentiating.
> A much simpler version is f'(x) = {-1 if x<0; +1 if x>0; Chaitin's constant if x=0}. f(x) = abs(x).
Similarly, differentiating abs(x) doesn't get you that function.
But I see where you're coming from, and I agree this doesn't tell us anything profound about computability. That said, it is a cute result that differentiable functions are flexible enough to admit this kind of construction, and that's straightforward but not obviously trivial, as your attempts somewhat ironically show. I think Myhill's proof is pretty close to a minimal working example and trying to fix your examples would result in something that looked very similar.
Myhill uses a parlor trick to make his version continuously differentiable. It's a pretty good parlor trick, but it doesn't have much to do with computability.
I might be numb, though, to the fact that much of what want to understand can't be. If the universe isn't discrete, then it seems like noncomputability is the default.
The first order theories of the real numbers using addition and multiplication are decidable [0], while FO theories of the integers under the same operations are not.
The relevant book Computability in Analysis and Physics by Pour-El and Richards is from 1989 but it is quite readable. The main requirements are a strong mathematical background (mostly in analysis and PDEs and an acquaintance with computability theory) and perhaps some appreciation for physics.
I wonder to what degree this is an artifact of the definition of "computable real" in common use (originally sure to Turing I believe), which is a Turing machine that outputs successive digits of your real number.
The point, I think, is that this gives you a good model for doing mathematics - it's a simple definition, and it allows you to talk about real numbers to arbitrary precision in arbitrary computational problems. But the downside is it's a minefield of subtle logical issues - addition is non-computable! So is the order relation, and equality, and a host of other basic stuff. It's not surprising that a complex limit-based process like taking a derivative would be also be non-computable.
On the other hand physicists want to model reality, which is a totally different set of constraints. I suspect that, as mathematicians, we've taken a logical construction that maps reasonably well onto the universe in some cases (real numbers) and stretched it far beyond its applicability there, because it leads to interesting mathematics. Physicists, if they ever find the cracks, will just come up with a better abstraction and move on.
> It's not surprising that a complex limit-based process like taking a derivative would be also be non-computable.
The reason it was surprising to me is that it would naively imply that an analog computer could compute something that a TM could not. If that were true, it would be Big News. But the construction of a computable function whose derivative is uncomputable is such that this function cannot be physically realized because you run into quantum effects.
Nice, thanks for the link. I knew that "printable" and "computable" reals were equivalent logically but it didn't occur to me that the equivalence itself would be uncomputable! This is exactly what I mean about a minefield of subtlety haha.
But to my point, I don't even think the examples in the OP paper are that convincing to me. Sure, you can construct examples of circuits with computable inputs and non-computable outputs, but this basically comes down to fractal-like driving behaviour that can't be approximated at any scale correctly. It's an artifact of the mathematics, which lets you do this kind of thing to an input signal, but at that point (my belief is that) you've left the realm of physics/reality and are now chasing pure logical implications.
It's like extrapolating from the edge of a map and concluding that there's no ocean because your original map had no water in it. Actually, you just needed a different map.
A weaker but easier result is that the differentiation operator is uncomputable: Define f_t(x) = t arctan(x/t). As t -> 0, f_t -> 0. But notice that f'_t(0) = 1.
By contrast, the integration operator is computable. Why? Because a piece of code that defines a function f over the real numbers can be generalised to interval numbers (see "interval arithmetic") -- it then follows that the upper and lower Darboux sums are both computable. QED
I think you don't even need arctan for this. Just put one of Myhill's "bumps" at x=0 and shrink it down. That function approaches f(x)=0 for all x but its derivative at x=0 remains 1.
I would consider the Myhill proof to be constructive, curious why you don't think so?
Set A as desired that is non-recursive, recursively enumerable is conceptually easy to construct: let A be the binary encoding of all Turing Machines that halt. This is well known not to be recursive (computable), but you can recursively enumerate them by taking a bijection from s: N -> NxN (possible since NxN is known to be countable) and on step i emit M if Turing Machine with binary encoding M halts on step B, where s(i)=(M,B).
The resulting Myhill function f is indeed computable and derivative non-computable, but it is highly dubious that such a function would be physically realizable. Why and how would we expect such a function to possibly arise in nature, based on a non-computable set A? For one thing, it's second derivative diverges so hard it can't be bounded as x -> 0 by any computable function. Also, one very quickly is dealing with x and y scopes far below Plank limits.
Ah, I think the non-constructive comment is just about presentation order; he gives a sketch of how f works first then later he gives an explicit formula partway through page 2 after theta, alpha, beta, and h are defined.
For why f is recursive (computable), here's maybe a helpful way of thinking about it: Let's think about the halting behavior of an input Turing Machine M. Consider the following pseudocode infinitary program which "outputs" two variables A_M and B_M after infinite time:
for each integer n:
if M halts on step n:
return A_M = 2^(-n) ; B_M = 1
if M never halts, return A_M = 0 ; B_M = 0
Clearly, B_M is not computable; that's the halting problem. However, A_M is actually computable, as computability of real-valued functions is defined as the ability to give an estimate to arbitrarily small queried precision: for precision epsilon, pick 2^(-c) < epsilon and run our algorithm above for just the first c steps; then pass on the value if it returned, or we can return zero and that's fine as we are within epsilon of the true A_M. So, A_M is computable whereas B_M is not.
The trick then is to observe that we can construct theta-functions with arbitrarily small values but constant-sized derivatives; so by summing a bunch of these together we get a function whose value at 2^(-M) behaves like A_M and whose derivative at 2^(-M) behaves like B_M.
> If it really is an example of an uncomputable physical process
I guess first you'd have to prove that there are physical processes are actually continuous, and that this continuum is genuinely the continuum of the reals.
It is already known that a computer with access to real numbers with infinite precision can perform hypercomputation, I'm not sure how much this is relevant, but:
The continuity of physical processes is not something that can be proved. It is an assumption that is included or not included among those on which a mathematical model of the physical processes is based. The suitability of any such model is based on the comparison between its predictions and the experimental results.
In standard physics, the space and time are continuous, and nothing else. All the physical quantities that are derived from length or angles or time are continuous (this includes quantities like mass and energy, which are derived from time). Besides those, there are no other physical quantities that are continuous.
The mathematical models that assume the continuity of space and time match extremely well any experiments and for now there exists no evidence whatsoever that space and time are not continuous.
Besides the standard physics, there have been a few attempts to create mathematical models of the physical processes where the space and time are discrete. Nevertheless, these mathematical models did not succeed to demonstrate any advantage over the standard models with continuous space and time.
> The continuity of physical processes is not something that can be proved.
I agree with you, but is there any peer-reviewed publication that can be cited? The idea makes sense to me, firstly the Reals \ Inaccessible Reals = Computable Reals, secondly you can't ever input an inaccessible real to an experiment nor retrieve one out of an experiment -- but then I'm not completely certain in making the conclusion that no experiment can be devised which shows that inaccessible reals exist in physical space.
I am concerned about this in the field of complexity analysis of quantum computers too, I think that the use of reals in physics is leading to mathematically correct but non-physical results about complexity theory of quantum computers. Having a paper to point at and say "look, stop assuming your Bloch spheres are backed by uncountable sets, it's leaking non-computable assumptions into your analysis of computation" would be helpful.
> [UPDATE] Let me put this more succinctly: how is it possible that there can be a continuous computable function whose derivative is uncomputable? What exactly is it about this function that makes numerical differentiation fail?
Like this
f(0) = 1
f(x!=0) = 0
It's more of a mathematical trick than anything else, it's not a "natural function" let's put it this way
Equality over computable reals is not decidable, so I don't think you've actually defined a computable function here. The issue is much more subtle than that.
Two years it not that old, and the topic is obscure enough that it could plausibly have gone unnoticed. Bell's inequality went virtually unnoticed when it was first published.
My money is definitely on parlor trick, but I would still like to understand why.
[UPDATE] Let me put this more succinctly: how is it possible that there can be a continuous computable function whose derivative is uncomputable? What exactly is it about this function that makes numerical differentiation fail?
[UPDATE2] Here is a link to the Myhill paper for easy reference.
https://projecteuclid.org/download/pdf_1/euclid.mmj/10290006...
It's remarkably short, only two pages.