Comment by solveit | Hacker News Reader

Comment by solveit | Hacker News Reader

Parent Full thread

> how is it possible that there can be a continuous computable function whose derivative is uncomputable?

For others: The original paper is short and very readable - https://projecteuclid.org/journalArticle/Download?urlId=10.1...

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.

0: https://en.wikipedia.org/wiki/Chaitin%27s_constant

1: And so strictly-containing-rational-numbers, although predicting which rational numbers is nontrivial.

2: The rounding error from assuming all machines that halt after y steps actually run forever scales as O(1/y) in the worst case.

> 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).

This is wrong. The function f you've defined is not continuously differentiable. The one in Myhill's paper is.

Evidently I should have been more explicit:

> > A much simpler[-and-more-nitpickable] version

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.

> 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.

Reply on news.ycombinator.com