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.
That cannot be true, because if both x<0 and x>0 are decidable then x=0 is also decidable.
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.
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.
Computability theory is mathematics.
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
The Real numbers are topologically weird when you dig into it.
Random example.
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.
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.
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?
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.
> Finite time is not practical time.
Sorry for my daftness but if x and y are both a transcendental number, for example pi, then x and y have infinitely many digits so the Turing machine that determines whether x < y is true will not halt, even with an infinitely long tape, or will it? What am I misunderstanding?
If you could recommend a source that explains the basics of these arguments, I’d appreciate it.
For an introduction to real real analysis is an old book typically called the 'Baby Rudin' Principles of Mathematical Analysis by Walter Rudin.
It is tiny and expensive, as most college math text books are once you get past a certain level. No idea if there is something better now, it is from the 1950's and there are used copies in most used book shops for cheap (or there was). It has no definition of 'equals' but does have a concept of equivalent relations.
Dummit and Foote's Abstract Algebra book is a great reference, especially with the problem with AI pollution. Coming from a General Relativity background, it still took me two years to work through on my own.
I don't know any suggestions on a more modern approach of starting with type or category theory.
I am not really interested in constructivist math, it is a problem to get around for me, so maybe someone who is can chime in on a better path.
While not rigorous, this paper does a good job at explaining just how muddy the concept of 'equality' is.
[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.