6 ms·

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

by ekez 2y ago

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.
      - lisper 2y ago
        Yes, you're right. See https://news.ycombinator.com/item?id=41154273 https://news.ycombinator.com/item?id=41154273 for my post-mortem.
    - bubblyworld 2y ago
      The order relation on computable reals is undecidable - this is well known, and the parent's argument is correct. If both x<y and x>y were decidable then you could easily decide equality too by just checking them and seeing if the answer to both was "no". Computability theory is mathematics.
      - lisper 2y ago
        Tracing back through this thread, the term "deciable" was introduced in a very unfortunate way: ekez: why is it impossible to decide whether x<0, x=0, or x>0 as in Example 1? lisper: 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: That cannot be true, because if both x<0 and x>0 are decidable then x=0 is also decidable. Both lisper (me) and teraflop are correct. The problem is that inequality is not decidable, it's semi-decidable. It's teraflop who introduced the word "decidable" into the discussion, not me, but I didn't pay enough attention to that at that time. /u/scarmig got it right in this comment: https://news.ycombinator.com/item?id=41150519 https://news.ycombinator.com/item?id=41150519
        bubblyworld 2y ago
        Right, I agree that they are semidecidable, thanks for clarifying. My interpretation of "only x=0 is undecidable" was that you were claiming the other two were decidable (which is a reasonable reading imo). But it sounds like we don't actually disagree here.
        lisper 2y ago
        It's my fault for not being more explicit. I just didn't think it all the way through.
  - nyrikki 2y ago
    Equality of real numbers is undecidable. Specifically recursively undecidable, which is the same as uncomputable. The Real numbers are topologically weird when you dig into it. Random example. https://mathworld.wolfram.com/RichardsonsTheorem.html https://mathworld.wolfram.com/RichardsonsTheorem.html
    - teraflop 2y ago
      I agree that given two computable real numbers x,y, asking whether x=y is undecidable. The point I'm making is that it can't be true that x<y or x>y are decidable, because then x=y would also be decidable, and it isn't.
      - nyrikki 2y ago
        A computable number is real number that can be computed to by a finite, terminating algorithm. x<y meets that definition because you can compare digits until one doesn't match. The same can be done for not equal, testing until there is a difference. Real real numbers are infinite precision. Showing that a number is not, not equal always requires you to normalize, truncate etc... No matter how many digits you test, there is an uncountable infinity of real numbers between you epsilon. That means you do not have a finite terminating algorithm.
        nequo 2y ago
        Is x < y decidable or semidecidable? If x and y are the same number, then a Turing machine that compares the digits of x and y to determine whether x < y will never terminate. Doesn’t this mean that x < y is not decidable?
        nyrikki 2y ago
        A Turing machine as an infinite long tape, and even if it takes 10 times the time to the heat death of the universe x<y will halt. Finite time is not practical time. Given two Turing machines A and B approximating numbers a and b, where a ≠ b, you can use an epsilon to prove a > b, that is 'sufficient' for a proof. You are trying to convert that one sided, semi-decidable 'a>b' into a two sided a>b f Id yes and a≤b is no. That is undecidable. Even if you change the ≤ into <, which does imply the exitance of b. It doesn't prove equality. You have to resort to tactics like normalization for that. Type theory is probably a good path to understand why. You seem to be coming from a set perspective and you will run into the limits of ZFC that way.
  - mgsouth 2y ago
    Haven't seen the paper, but I'd guess the argument is something like "if the domain for x includes 0, then [edit: whenever x = 0] the Turing machine will get into an infinite loop looking for the first inverted bit[1]. _None_ of the three states will ever be provably true or false. If the domain _excludes_ 0 then you can prove that the machine will hit a non-zero bit in finite time, thus terminate, and either x<0 or x>0 will be shown true. But if you exclude 0 then you've also shown that the =0 state will never be true." [1] multiple zero bits and a one bit is >0, multiple 1 bits and a zero bit is <0. Infinite zero bits (even if followed by a one bit) is +0, infinite 1 bits (even if followed by a zero bit) is -0.
  - nine_k 2y ago
    An exact comparison is undecidable. You can only say if the numbers sufficiently differ. This is equivalent to saying that x > 0 + ε or x < 0 - ε, where ε > 0. If you represent numbers in binary, ε = 2^(-n), where n is the maximum number of bits you allocate to represent a number. Obviously you have n < ∞ in any finite machine.
fgdorais 2y ago
This is better known as the Table Maker's Dilemma. Say you have some computable number p, that means you can compute a (rational) approximation p' to p within any given tolerance eps > 0 (i.e. you know |p - p'| < eps). To determine whether p > 0, p = 0, or p < 0, you compute an approximation p' to a certain tolerance eps. If p' > eps then you know p > 0, if p < -eps then you know p < 0, otherwise you need a better approximation... Without further knowledge about p, there is no point where you can assert p = 0.
- ekez 2y ago
  Thank you for the response. (I assume you mean "p' < -eps" in the second conditional?) How often are rational approximations computable within any given tolerance?
scarmig 2y ago
x > 0 and x < 0 are both semidecidable. Which is to say, they can be decided, but their converses cannot. So if either of those are true, they will halt (by running them in parallel, and halting once one halts), but if neither of them are, it may not halt. If you remove 0 from possible inputs, you no longer need to worry about that possibility, and the problem is then decidable.

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

by ekez 2y ago

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

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.
    - lisper 2y ago
      Yes, you're right. See https://news.ycombinator.com/item?id=41154273 https://news.ycombinator.com/item?id=41154273 for my post-mortem.
  - bubblyworld 2y ago
    The order relation on computable reals is undecidable - this is well known, and the parent's argument is correct. If both x<y and x>y were decidable then you could easily decide equality too by just checking them and seeing if the answer to both was "no". Computability theory is mathematics.
    - lisper 2y ago
      Tracing back through this thread, the term "deciable" was introduced in a very unfortunate way: ekez: why is it impossible to decide whether x<0, x=0, or x>0 as in Example 1? lisper: 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: That cannot be true, because if both x<0 and x>0 are decidable then x=0 is also decidable. Both lisper (me) and teraflop are correct. The problem is that inequality is not decidable, it's semi-decidable. It's teraflop who introduced the word "decidable" into the discussion, not me, but I didn't pay enough attention to that at that time. /u/scarmig got it right in this comment: https://news.ycombinator.com/item?id=41150519 https://news.ycombinator.com/item?id=41150519
      - bubblyworld 2y ago
        Right, I agree that they are semidecidable, thanks for clarifying. My interpretation of "only x=0 is undecidable" was that you were claiming the other two were decidable (which is a reasonable reading imo). But it sounds like we don't actually disagree here.
        lisper 2y ago
        It's my fault for not being more explicit. I just didn't think it all the way through.
- nyrikki 2y ago
  Equality of real numbers is undecidable. Specifically recursively undecidable, which is the same as uncomputable. The Real numbers are topologically weird when you dig into it. Random example. https://mathworld.wolfram.com/RichardsonsTheorem.html https://mathworld.wolfram.com/RichardsonsTheorem.html
  - teraflop 2y ago
    I agree that given two computable real numbers x,y, asking whether x=y is undecidable. The point I'm making is that it can't be true that x<y or x>y are decidable, because then x=y would also be decidable, and it isn't.
    - nyrikki 2y ago
      A computable number is real number that can be computed to by a finite, terminating algorithm. x<y meets that definition because you can compare digits until one doesn't match. The same can be done for not equal, testing until there is a difference. Real real numbers are infinite precision. Showing that a number is not, not equal always requires you to normalize, truncate etc... No matter how many digits you test, there is an uncountable infinity of real numbers between you epsilon. That means you do not have a finite terminating algorithm.
      - nequo 2y ago
        Is x < y decidable or semidecidable? If x and y are the same number, then a Turing machine that compares the digits of x and y to determine whether x < y will never terminate. Doesn’t this mean that x < y is not decidable?
        nyrikki 2y ago
        A Turing machine as an infinite long tape, and even if it takes 10 times the time to the heat death of the universe x<y will halt. Finite time is not practical time. Given two Turing machines A and B approximating numbers a and b, where a ≠ b, you can use an epsilon to prove a > b, that is 'sufficient' for a proof. You are trying to convert that one sided, semi-decidable 'a>b' into a two sided a>b f Id yes and a≤b is no. That is undecidable. Even if you change the ≤ into <, which does imply the exitance of b. It doesn't prove equality. You have to resort to tactics like normalization for that. Type theory is probably a good path to understand why. You seem to be coming from a set perspective and you will run into the limits of ZFC that way.
- mgsouth 2y ago
  Haven't seen the paper, but I'd guess the argument is something like "if the domain for x includes 0, then [edit: whenever x = 0] the Turing machine will get into an infinite loop looking for the first inverted bit[1]. _None_ of the three states will ever be provably true or false. If the domain _excludes_ 0 then you can prove that the machine will hit a non-zero bit in finite time, thus terminate, and either x<0 or x>0 will be shown true. But if you exclude 0 then you've also shown that the =0 state will never be true." [1] multiple zero bits and a one bit is >0, multiple 1 bits and a zero bit is <0. Infinite zero bits (even if followed by a one bit) is +0, infinite 1 bits (even if followed by a zero bit) is -0.
- nine_k 2y ago
  An exact comparison is undecidable. You can only say if the numbers sufficiently differ. This is equivalent to saying that x > 0 + ε or x < 0 - ε, where ε > 0. If you represent numbers in binary, ε = 2^(-n), where n is the maximum number of bits you allocate to represent a number. Obviously you have n < ∞ in any finite machine.

fgdorais 2y ago

This is better known as the Table Maker's Dilemma. Say you have some computable number p, that means you can compute a (rational) approximation p' to p within any given tolerance eps > 0 (i.e. you know |p - p'| < eps). To determine whether p > 0, p = 0, or p < 0, you compute an approximation p' to a certain tolerance eps. If p' > eps then you know p > 0, if p < -eps then you know p < 0, otherwise you need a better approximation... Without further knowledge about p, there is no point where you can assert p = 0.

ekez 2y ago
Thank you for the response. (I assume you mean "p' < -eps" in the second conditional?) How often are rational approximations computable within any given tolerance?

scarmig 2y ago

x > 0 and x < 0 are both semidecidable. Which is to say, they can be decided, but their converses cannot. So if either of those are true, they will halt (by running them in parallel, and halting once one halts), but if neither of them are, it may not halt. If you remove 0 from possible inputs, you no longer need to worry about that possibility, and the problem is then decidable.