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