[h0mEDw]

It's extremely counter intuitive what would happen if a computer system (a Turing machine) was operating symbolically on real numbers, not floating point numbers which have vastly different properties (for example, addition is not associative there although it is commutative). We can refer to constructive logic proofs in the real number theory. There's a ton of surprising facts there, to pick two:

  1. For x and y you cannot prove that x<=y or x=>y
  2. Every function is continuous

Some hand-waving to see why 1. is a problem: given two numbers, x and y, as a lazily-computed infinite decimal expansion, the program that loops in parallel over the expansions and seeks the first difference (to determine which number is greater) will never terminate if x and y have identical expansions.

See this submission from two months ago: https://news.ycombinator.com/item?id=18411935

[mike00632]

Maybe I'm just arguing semantics here but I would say that while calculations are carried out using floating points the numbers themselves are represented symbolically. For example, if you came up with an algorithm to calculate euclidean distance then you would eventually employ a square root algorithm instead of an approximation of a square root stored as a floating point number. The algorithm "sqrt(2)" is a symbolic representation of the square root of 2.

[h0mEDw]

Yeah I meant that there's another layer to the symbolic representation of "sqrt(2)" than just the tree of operation, so that you can ask sensible questions about the value of the number. For instance a generator of decimal representation or a function like "given N return a fraction q/p that's within 1/2^N of the value".

And floats are really a whole other beast than fractions or naturals or real numbers. As I wrote earlier - the "+" operator isn't associative. Python snippet:

    def before():
        x = 0.0
        x += 1.0
        for i in xrange(1000):
            x += 1e-17
        return x

    def after():
        x = 0.0
        for i in xrange(1000):
            x += 1e-17
        x += 1.0
        return x


    print before() == 1.0
    print after() == 1.0

Will print:

   True
   False

[mike00632]

Rewrite your functions to be generator functions. They don't even need to be based on the desired level of precision to always be decidable.

[h0mEDw]

Not sure what your point is. I can just suggest to see the PDF: https://news.ycombinator.com/item?id=18411935

[PurpleBoxDragon]

Isn't it also possible for two numbers to have unequal expansions but still be equal? Take .3... * 3 vs 1. The first expands to .9... while the second expands to 1.0... but they are also equal.

[mike00632]

Right, but note that we can use numbers from countable sets and find different symbolic representations for them (3.0 vs 3). That problem is not inherent from the uncountability of the real numbers.

[h0mEDw]

Yup, it is possible. That was just a hand wavy example to show where the issue is. Symbolic real numbers need not be represented as small programs/objects generating a sequence of digits. But all of those implementations/representations will fail to compare some numbers.

Edit: for instance, you could imagine a representation (think object of a virtual class in c++) that gives you a fraction and a 1/2^n bound for error, where you can query the number for whatever n you see fit. Still, in some cases it's undecidable to determine which number is greater.