5 ms·

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 significan

• almostgotcaught 2y ago
  > Big News The paper is from May 2022. Don't you have the answer to whether it's big news? Whether the news is big is (usually) apparent/assessed when it is new.
  • lisper 2y ago
    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.
• solveit 2y ago
  > 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.1307%2Fmmj%2F1029000631 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.
  • 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.
• deleted 2y ago
  [deleted]
• NegativeK 2y ago
  Is it specifically the fact that it's a physical process that makes it earth shattering? Physical models of computers ( https://en.wikipedia.org/wiki/Billiard-ball_computer https://en.wikipedia.org/wiki/Billiard-ball_computer ) have been around for a long time, which means that noncomputability has been tangible for a long time. 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.
  • vinnyvichy 2y ago
    Hey, I feel you, my first thought was that continuously differentiable functions aren't physical :)
    • jpt4 2y ago
      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. [0] https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers https://en.wikipedia.org/wiki/Decidability_of_first-order_th...
      • vinnyvichy 2y ago
        Wikipedia can be confusing.. https://mathoverflow.net/questions/134259/is-the-first-order-theory-with-of-real-numbers-with-addition-and-multiplicat https://mathoverflow.net/questions/134259/is-the-first-order...
  • 082349872349872 2y ago
    > it seems like noncomputability is the default compare https://en.wikipedia.org/wiki/Weierstrass_function#Density_of_nowhere-differentiable_functions https://en.wikipedia.org/wiki/Weierstrass_function#Density_o... (1872 et seq)?
• fgdorais 2y ago
  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.
• roywiggins 2y ago
  > 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: https://en.wikipedia.org/wiki/Real_computation https://en.wikipedia.org/wiki/Real_computation
  • ogogmad 2y ago
    > It is already known that a computer with access to real numbers with infinite precision can perform hypercomputation I took an interest in this area once, and this is not true. "Computable analysis / computable topology" says quite the opposite.
    • roywiggins 2y ago
      Isn't this describing such a machine? https://en.m.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine https://en.m.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Sm...
      • ogogmad 2y ago
        No. There's literally an article on Computable Analysis, and it details Type Two Turing Machines.
  • adrian_b 2y ago
    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.
• dooglius 2y ago
  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.
  • lisper 2y ago
    > curious why you don't think so? Uh, because Myhill says so? "We first define the function f non-constructively..." But I agree with your analysis. It seems constructive to me too. I don't understand his proof that f is recursive though.
    • dooglius 2y ago
      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.
• raverbashing 2y ago
  > [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
  • bubblyworld 2y ago
    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.
• ogogmad 2y ago
  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 [edit] Changed oo to 0.
  • lisper 2y ago
    Thanks! 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.
    • ogogmad 2y ago
      The arctan has the advantage that it's differentiable infinitely many times over R.
• bubblyworld 2y ago
  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. Anyway, not sure if I'm making sense here.
  • lisper 2y ago
    > 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. Also, you might find this interesting: https://www.sciencedirect.com/science/article/pii/S0304397524001889 https://www.sciencedirect.com/science/article/pii/S030439752...
    • bubblyworld 2y ago
      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.