3 ms·

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 co

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