3 ms·

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

by a1369209993 2y ago

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

ogogmad 2y ago
> 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.
- a1369209993 2y ago
  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.
solveit 2y 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.

ogogmad 2y ago

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

a1369209993 2y ago
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.

solveit 2y 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.