7 ms·

Non-computability of solutions of certain equations on digital computers (2022)

88 points by lisper 2y ago

BraveNewCurency 2y ago
All models are wrong. Some (wrong) models are useful. Computers can't represent 0.1 (in floating point), yet that hasn't stopped anyone from doing finances on their computer. I don't think this is big news OR a parlor trick. It's just some obscure thing computers can't do that nobody has noticed for 70 years because nobody needed it.
- lisper 2y ago
  > Computers can't represent 0.1 (in floating point) Of course they can. They just can't do it in binary [EDIT: base 2]. But they can certainly do it in (say) BCD [EDIT: base 10].
  - brewmarche 2y ago
    .NET’s decimal datatype for example represents a decimal floating point number
  - pvg 2y ago
    Just as a total pedantipoint, they also do that in binary (hence the B in BCD, in that specific case).
    - lisper 2y ago
      I've updated my comment with appropriate pedantedits.
      - BraveNewCurency 2y ago
        But BCD is not floating point (generally shorthand for the IEEE 754 Floating Point standard, which nearly every CPU and GPU have hardware support for). And I don't know much about BCD, but it is probably missing niceties like NaN and Inf for capturing edge cases that happen deep inside your equations. These matter if your system is to be reliable.
        lisper 2y ago
        > generally shorthand for the IEEE 754 Floating Point standard Yes, generally, but that is just a social convention. There is nothing stopping you from doing floating point in base 10 rather than base 2, and if you do, 0.1 becomes representable exactly. It's just a quirk that 1/10 happens to be a repeating decimal in base 2. It is in no way a reflection of a limitation on computation.
        brewmarche 2y ago
        IEEE 754 defines decimal floating point in single (32 bit), double (64) and quadruple (128) precision since the 754-2008 revision. (However .NET’s type I mentioned above even though it’s 128-bit is its own thing and does not adhere to it).
- deleted 2y ago
  [deleted]
- TacticalCoder 2y ago
  > Computers can't represent 0.1 (in floating point), yet that hasn't stopped anyone from doing finances on their computer. floating point for financial data may have made sense back when my 386 DX CPU has a FP coprocessor and computation were dog slow. In this day and age though you'll typically be not just a bit but much better using an abstraction that can represent numbers with decimals precisely, which frees you from a great many rounding error, epsilon computation, error propagation, etc.
ekez 2y ago
why is it impossible to decide whether x<0, x=0, or x>0 as in Example 1?
- lisper 2y ago
  Only x=0 is undecidable. It's because you have to check an infinite number of digits past the decimal point to see if all of them are zero, and that will not halt.
  - teraflop 2y ago
    > Only x=0 is undecidable. That cannot be true, because if both x<0 and x>0 are decidable then x=0 is also decidable.
    - lisper 2y ago
      Nope. You're thinking about this mathematically, not algorithmically. The question is essentially to decide whether the output of a TM is all zeros or whether it will eventually output a 1. If it outputs a 1 you will know that in a finite amount of time by running the program, but if it never outputs a 1 then you can't tell that by running the program, and it's impossible in general to tell any other way because that would be tantamount to solving the halting problem. Here is a concrete example: write a program that systematically tests all numbers for counterexamples to the Goldback conjecture. Every time a number fails to be a counterexample, output a zero, otherwise output a 1. Consider the output of that program to be a real number expressed as a binary decimal. If that number is not zero you will know in a finite amount of time, but if it is zero you will not know that until someone proves the Goldbach conjecture.
      - teraflop 2y ago
        > Nope. You're thinking about this mathematically, not algorithmically. I don't know what you mean by this, and I'm not sure how it relates to what I said. I'm using "decidable" in the strict, computer-science sense of the word. The statement in example 1 of the paper, which we're discussing, is about computable real numbers. A computable real number is one for which there is a Turing machine that can calculate it to any desired finite precision in finite time. A semidecidable problem is one for which there is a program that halts if the answer is "yes", but may not halt if the answer is "no". The halting problem is in this category. Given a computable real number x, asking whether x<0 or x>0 are semidecidable but not decidable problems.
almostgotcaught 2y ago
[flagged]
- lisper 2y ago
  This paper is not unremarkable. It's actually quite a surprising result. The only question is whether it's earth-shattering, or just a parlor trick. My money is on parlor-trick, but I don't understand the math well enough to be confident of that. I posted this here hoping to find someone who could shed some light on this question.
  - almostgotcaught 2y ago
    It is unremarkable - it has 5 citations since May 2022. I have papers with more cites from this year. Edit: it's a parlor trick because they invent a decision procedure (bounds on maxima) and then prove something based on that premise: > It will be shown that non-computability of the first derivative is not detectable by a Turing machine for two concrete examples I wonder if they rigged the game hmmm. In general people do this kind of thing all the time to get published (build both a technique and a foil for their technique) and it's always a weak paper.
    - cscurmudgeon 2y ago
      1. https://academia.stackexchange.com/questions/37021/why-is-it-bad-to-judge-a-paper-by-citation-count https://academia.stackexchange.com/questions/37021/why-is-it... 2. > it has 5 citations since May 2022 ... I have papers with more cites from this year ... In general people do this kind of thing all the time to get published People also play games to get citations.
      - almostgotcaught 2y ago
        [flagged]
        immibis 2y ago
lisper 2y ago
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 significance. Is this Big News or a parlor trick? If it really is an example of an uncomputable physical process, that would seem to me to be earth-shattering, and yet this result does not appear to have made a splash. It is based on a construction of J. Myhill of a continuous recursive (and hence computable) function whose derivative is not computable. The proof is non-constructive, and it assumes the existence of a partially decidable set called A which somehow (this is the part I don't quite understand) results in a computable function despite the fact that its derivative can't be computable because that would imply A is decidable. Any clues would be much appreciated. [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? [UPDATE2] Here is a link to the Myhill paper for easy reference. https://projecteuclid.org/download/pdf_1/euclid.mmj/1029000631 https://projecteuclid.org/download/pdf_1/euclid.mmj/10290006... It's remarkably short, only two pages.
- 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.
deleted 2y ago
[deleted]
jfoutz 2y ago
This reminds me of this reddit question https://www.reddit.com/r/askmath/comments/1eakt5c/if_you_pick_a_real_number_from_0_to_1_what_is_the/ https://www.reddit.com/r/askmath/comments/1eakt5c/if_you_pic... "If you pick a real number from 0 to 1, what is the probability that it is rational?" and the first response, " With a uniform random process over an interval (a, b), you can find the probability of picking an element from a set X by integrating 1/(b - a) over the set X. Since the (lebesgue) integral of the rational numbers is 0, the probability of picking a rational number is 0. " And that kinda broke my brain for an afternoon. So, when a computer represents a number, it's always rational. You can have a lot of memory, but always finite. Now, you can go further, and represent things symbolically, like sage math or a bunch of other systems. But (I believe) at the end of the day Godel always wins. There are always true statements that can't be proved. If I remember right, computable stuff is a subset (maybe improper?) of provable stuff. Looks interesting. Thank you for posting it. I'll try to read it later. Although, I'm a math tourist. I probably won't be able to give you any grand insight.
- deleted 2y ago
  [deleted]
- rjurney 2y ago
  I got this one without realizing the complex basis for it... there's an infinite number of real numbers between 0 and 1, compared with a limited proportion of rational numbers.
  - jerf 2y ago
    There's an infinite number of both. A way to intuit why you have a zero probability of choosing a rational is to consider randomly picking digits one at a time. Suppose you start with a "3". What is necessary to get one third as your random choice? You must now uniformly randomly select an infinite number of 3s. You can think of that as just a contradiction without much loss here, in that selecting an infinite number of 3s is infinite proof that your process must not be random. (Putting rigor on that might be a challenge but I think it's a fine intuition.) This argument similarly holds for any rational, because no matter how large any given rational's repeat may be, it is always finite, and in order for that rational to be your choice you have still fully determined the result of a putatively uniformly random process for an infinite number of exact picks, and if it is truly random, the probability of that process producing the exact necessary repeat infinitely is always 0.
transfire 2y ago
I haven’t read the whole article yet, but I’m guessing it boils down to a Halting Problem? And I assume if a Turing machine can’t, neither can a human. If that is not the case, something smells fishy in Denmark.
dooglius 2y ago
At a glance, this paper seems extremely questionable. It appears to take an offhand comment by Kahneman in a Lex Friedman podcast regarding the limits of AI and interpret it as asking whether there is a problem that humans can solve but machines cannot -- which is definitely not a reasonable interpretation IMO as in context Kahneman is talking about the limitations of present AI systems, and computability is a totally different question. The paper's claim to have found such a class of problem would mean the Church-Turing thesis is false, and so it is quite surprising that the Church-Turing thesis and existing discussion around it does not appear to be mentioned or cited. Anyway, the paper constructs at some length a non-computable problem and then declares, "Nevertheless, a human can certainly solve this problem by creative work." While I haven't gone through the construction in-depth to see whether that's reasonable, this certainly doesn't come across as a very rigorous proof. Also, in the introduction, it makes the bold claim that "digital computers ... are able to compute with finite sequences of rational numbers only," (and suggests that analog and quantum computers lack such limitations) which is certainly false as can be seen by programs such as Mathematica that easily solve many systems involving irrational and transcendental numbers.
nlewycky 2y ago
From the abstract, "simulations of such systems are usually done on digital computers, which are able to compute with finite sequences of rational numbers only." Not at all! Digital computers can use computable reals which are defined as any function from a rational value (the error bound) to a rational value which is within the supplied error-bounds from the true value. Do not mistake this for computing in the rationals, these functions which perform the described task are the computable real numbers. There are countable-infinity many of these functions, one for each computable real. For instance, note that you can always compare two rationals for equality, but you can't always compare two computable reals for equality, just like reals. Hans Boehm (of Boehm garbage collector fame) has been working on this for a long time, here is a recent paper on it: https://dl.acm.org/doi/pdf/10.1145/3385412.3386037 https://dl.acm.org/doi/pdf/10.1145/3385412.3386037
Animats 2y ago
Most fractal functions don't have a well-defined derivative. If the length of the fractal curve increases indefinitely as you zoom in, the concept of a local slope is not meaningful. More direction changes appear as you zoom in. Is there more to this result than that observation?

88 points by lisper 2y ago

All models are wrong. Some (wrong) models are useful. Computers can't represent 0.1 (in floating point), yet that hasn't stopped anyone from doing finances on their computer. I don't think this is big news OR a parlor trick. It's just some obscure thing computers can't do that nobody has noticed for 70 years because nobody needed it.

lisper 2y ago
> Computers can't represent 0.1 (in floating point) Of course they can. They just can't do it in binary [EDIT: base 2]. But they can certainly do it in (say) BCD [EDIT: base 10].
- brewmarche 2y ago
  .NET’s decimal datatype for example represents a decimal floating point number
- pvg 2y ago
  Just as a total pedantipoint, they also do that in binary (hence the B in BCD, in that specific case).
  - lisper 2y ago
    I've updated my comment with appropriate pedantedits.
    - BraveNewCurency 2y ago
      But BCD is not floating point (generally shorthand for the IEEE 754 Floating Point standard, which nearly every CPU and GPU have hardware support for). And I don't know much about BCD, but it is probably missing niceties like NaN and Inf for capturing edge cases that happen deep inside your equations. These matter if your system is to be reliable.
      - lisper 2y ago
        > generally shorthand for the IEEE 754 Floating Point standard Yes, generally, but that is just a social convention. There is nothing stopping you from doing floating point in base 10 rather than base 2, and if you do, 0.1 becomes representable exactly. It's just a quirk that 1/10 happens to be a repeating decimal in base 2. It is in no way a reflection of a limitation on computation.
      - brewmarche 2y ago
        IEEE 754 defines decimal floating point in single (32 bit), double (64) and quadruple (128) precision since the 754-2008 revision. (However .NET’s type I mentioned above even though it’s 128-bit is its own thing and does not adhere to it).
deleted 2y ago
[deleted]
TacticalCoder 2y ago
> Computers can't represent 0.1 (in floating point), yet that hasn't stopped anyone from doing finances on their computer. floating point for financial data may have made sense back when my 386 DX CPU has a FP coprocessor and computation were dog slow. In this day and age though you'll typically be not just a bit but much better using an abstraction that can represent numbers with decimals precisely, which frees you from a great many rounding error, epsilon computation, error propagation, etc.

ekez 2y ago

why is it impossible to decide whether x<0, x=0, or x>0 as in Example 1?

lisper 2y ago
Only x=0 is undecidable. It's because you have to check an infinite number of digits past the decimal point to see if all of them are zero, and that will not halt.
- teraflop 2y ago
  > Only x=0 is undecidable. That cannot be true, because if both x<0 and x>0 are decidable then x=0 is also decidable.
  - lisper 2y ago
    Nope. You're thinking about this mathematically, not algorithmically. The question is essentially to decide whether the output of a TM is all zeros or whether it will eventually output a 1. If it outputs a 1 you will know that in a finite amount of time by running the program, but if it never outputs a 1 then you can't tell that by running the program, and it's impossible in general to tell any other way because that would be tantamount to solving the halting problem. Here is a concrete example: write a program that systematically tests all numbers for counterexamples to the Goldback conjecture. Every time a number fails to be a counterexample, output a zero, otherwise output a 1. Consider the output of that program to be a real number expressed as a binary decimal. If that number is not zero you will know in a finite amount of time, but if it is zero you will not know that until someone proves the Goldbach conjecture.
    - teraflop 2y ago
      > Nope. You're thinking about this mathematically, not algorithmically. I don't know what you mean by this, and I'm not sure how it relates to what I said. I'm using "decidable" in the strict, computer-science sense of the word. The statement in example 1 of the paper, which we're discussing, is about computable real numbers. A computable real number is one for which there is a Turing machine that can calculate it to any desired finite precision in finite time. A semidecidable problem is one for which there is a program that halts if the answer is "yes", but may not halt if the answer is "no". The halting problem is in this category. Given a computable real number x, asking whether x<0 or x>0 are semidecidable but not decidable problems.

almostgotcaught 2y ago

[flagged]

lisper 2y ago
This paper is not unremarkable. It's actually quite a surprising result. The only question is whether it's earth-shattering, or just a parlor trick. My money is on parlor-trick, but I don't understand the math well enough to be confident of that. I posted this here hoping to find someone who could shed some light on this question.
- almostgotcaught 2y ago
  It is unremarkable - it has 5 citations since May 2022. I have papers with more cites from this year. Edit: it's a parlor trick because they invent a decision procedure (bounds on maxima) and then prove something based on that premise: > It will be shown that non-computability of the first derivative is not detectable by a Turing machine for two concrete examples I wonder if they rigged the game hmmm. In general people do this kind of thing all the time to get published (build both a technique and a foil for their technique) and it's always a weak paper.
  - cscurmudgeon 2y ago
    1. https://academia.stackexchange.com/questions/37021/why-is-it-bad-to-judge-a-paper-by-citation-count https://academia.stackexchange.com/questions/37021/why-is-it... 2. > it has 5 citations since May 2022 ... I have papers with more cites from this year ... In general people do this kind of thing all the time to get published People also play games to get citations.
    - almostgotcaught 2y ago
      [flagged]
      - immibis 2y ago

lisper 2y ago

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 significance. Is this Big News or a parlor trick? If it really is an example of an uncomputable physical process, that would seem to me to be earth-shattering, and yet this result does not appear to have made a splash. It is based on a construction of J. Myhill of a continuous recursive (and hence computable) function whose derivative is not computable. The proof is non-constructive, and it assumes the existence of a partially decidable set called A which somehow (this is the part I don't quite understand) results in a computable function despite the fact that its derivative can't be computable because that would imply A is decidable. Any clues would be much appreciated. [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? [UPDATE2] Here is a link to the Myhill paper for easy reference. https://projecteuclid.org/download/pdf_1/euclid.mmj/1029000631 https://projecteuclid.org/download/pdf_1/euclid.mmj/10290006... It's remarkably short, only two pages.

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.

deleted 2y ago

[deleted]

jfoutz 2y ago

This reminds me of this reddit question https://www.reddit.com/r/askmath/comments/1eakt5c/if_you_pick_a_real_number_from_0_to_1_what_is_the/ https://www.reddit.com/r/askmath/comments/1eakt5c/if_you_pic... "If you pick a real number from 0 to 1, what is the probability that it is rational?" and the first response, " With a uniform random process over an interval (a, b), you can find the probability of picking an element from a set X by integrating 1/(b - a) over the set X. Since the (lebesgue) integral of the rational numbers is 0, the probability of picking a rational number is 0. " And that kinda broke my brain for an afternoon. So, when a computer represents a number, it's always rational. You can have a lot of memory, but always finite. Now, you can go further, and represent things symbolically, like sage math or a bunch of other systems. But (I believe) at the end of the day Godel always wins. There are always true statements that can't be proved. If I remember right, computable stuff is a subset (maybe improper?) of provable stuff. Looks interesting. Thank you for posting it. I'll try to read it later. Although, I'm a math tourist. I probably won't be able to give you any grand insight.

deleted 2y ago
[deleted]
rjurney 2y ago
I got this one without realizing the complex basis for it... there's an infinite number of real numbers between 0 and 1, compared with a limited proportion of rational numbers.
- jerf 2y ago
  There's an infinite number of both. A way to intuit why you have a zero probability of choosing a rational is to consider randomly picking digits one at a time. Suppose you start with a "3". What is necessary to get one third as your random choice? You must now uniformly randomly select an infinite number of 3s. You can think of that as just a contradiction without much loss here, in that selecting an infinite number of 3s is infinite proof that your process must not be random. (Putting rigor on that might be a challenge but I think it's a fine intuition.) This argument similarly holds for any rational, because no matter how large any given rational's repeat may be, it is always finite, and in order for that rational to be your choice you have still fully determined the result of a putatively uniformly random process for an infinite number of exact picks, and if it is truly random, the probability of that process producing the exact necessary repeat infinitely is always 0.

transfire 2y ago

I haven’t read the whole article yet, but I’m guessing it boils down to a Halting Problem? And I assume if a Turing machine can’t, neither can a human. If that is not the case, something smells fishy in Denmark.

dooglius 2y ago

At a glance, this paper seems extremely questionable. It appears to take an offhand comment by Kahneman in a Lex Friedman podcast regarding the limits of AI and interpret it as asking whether there is a problem that humans can solve but machines cannot -- which is definitely not a reasonable interpretation IMO as in context Kahneman is talking about the limitations of present AI systems, and computability is a totally different question. The paper's claim to have found such a class of problem would mean the Church-Turing thesis is false, and so it is quite surprising that the Church-Turing thesis and existing discussion around it does not appear to be mentioned or cited. Anyway, the paper constructs at some length a non-computable problem and then declares, "Nevertheless, a human can certainly solve this problem by creative work." While I haven't gone through the construction in-depth to see whether that's reasonable, this certainly doesn't come across as a very rigorous proof. Also, in the introduction, it makes the bold claim that "digital computers ... are able to compute with finite sequences of rational numbers only," (and suggests that analog and quantum computers lack such limitations) which is certainly false as can be seen by programs such as Mathematica that easily solve many systems involving irrational and transcendental numbers.

nlewycky 2y ago

From the abstract, "simulations of such systems are usually done on digital computers, which are able to compute with finite sequences of rational numbers only." Not at all! Digital computers can use computable reals which are defined as any function from a rational value (the error bound) to a rational value which is within the supplied error-bounds from the true value. Do not mistake this for computing in the rationals, these functions which perform the described task are the computable real numbers. There are countable-infinity many of these functions, one for each computable real. For instance, note that you can always compare two rationals for equality, but you can't always compare two computable reals for equality, just like reals. Hans Boehm (of Boehm garbage collector fame) has been working on this for a long time, here is a recent paper on it: https://dl.acm.org/doi/pdf/10.1145/3385412.3386037 https://dl.acm.org/doi/pdf/10.1145/3385412.3386037

Animats 2y ago

Most fractal functions don't have a well-defined derivative. If the length of the fractal curve increases indefinitely as you zoom in, the concept of a local slope is not meaningful. More direction changes appear as you zoom in. Is there more to this result than that observation?