3 ms·
I'm not a mathematician, but it sounds like what this is saying is that as soon as you allow a number to contain an infinite number of digits, you can get an in
by skybrian 7y ago
I'm not a mathematician, but it sounds like what this is saying is that as soon as you allow a number to contain an infinite number of digits, you can get an infinite loop when you try to do a simple comparison. (For example, try to compare pi to an number that's not-quite pi. It might be a little more or a little less, but you can't know this without looking at all the digits, which is impossible.)
As a consequence, there are only two boolean-valued total functions: always return true, or always return false.
I guess that's why we don't use infinite streams of numbers for computation.
- lonelappde 7y agoYou don't need to look at all the digits, but there is no finite stopping point you can choose in advance. It's similar to the problem of comparing two natural numbers given in least significant bit order.
- skybrian 7y agoGiven a comparison function, an adversary can construct streams of digits that will make it run forever. This would be true either way. The problem seems to be with allowing algorithmically generated streams as input? Maybe our domain should be limited to numbers generated by algorithms that are known to terminate? But despite eliminating irrational numbers, this guarantee doesn't seem like enough for practical computing. Even arbitrary precision algorithms require their inputs not only to be computable, but actually computed in advance, showing at least that they fit in memory.