3 ms·
You 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
by lonelappde 7y ago
You 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.