Hacker News new | ask | show | jobs
by solveit 678 days ago
> 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.