3 ms·
You sound like a computer scientist, so think of it this way. When would your breadth-first search terminate, given an irrational number to locate? Can you ev
by colanderman 13y ago
You sound like a computer scientist, so think of it this way. When would your breadth-first search terminate, given an irrational number to locate? Can you even bound it? The answer is no, because there are an infinite number of digits in any irrational number. The breadth-first search would not terminate; the result would diverge toward infinity.
With the rationals in a grid, even ignoring that I can trivially arithmetically compute the corresponding natural (interleave the (finite!) digits of the numerator and denominator), I can give a bound on a similar search (say Z-order): O(n²).
I think the fundamental idea you are missing is that a natural number must have a finite number of digits. (This stems from the construction of naturals as finite objects.) Reals are not subject to this limitation, as evidenced by the existence of the irrationals.
[Actually, that last paragraph begs another question: what are the theoretical implications of the fact that any specific real must have a finite representation of some form? Does the reason we can reason about reals which we can't specifically identify with a finite construction have anything to do with the axiom of choice?]
- freefrancisco 13y agoThis actually helps a lot with the intuition, thanks! So in a sense every irrational number is an infinite number because there is no way to actually represent it in a finite way.
- colanderman 13y agoAlmost! See pesenti's link about definable numbers: most irrationals have no finite representation, although almost all the ones we are familiar with (e.g. sqrt(2), π, e) do: they can be represented as mathematical formulæ. (And indeed, note that such "definable" reals are countable!) So in my example above, π would not work if, say, your tree was a parse tree of mathematical formulæ: one could locate the formula for π in finite time. Unfortunately I cannot give an example of a single number which does not have such a finite parse tree, as, by its very nature, I cannot write down a finite description of it!
- jfarmer 13y agoNot quite. I can represent pi in a finite way, like so: π. That's about as finite as it gets! However, if you fix a finite alphabet beforehand, you will never be able to describe all real numbers using strings constructed from this alphabet. You can always add a new symbol to your alphabet to represent some new irrational number, but no matter how many symbols you add you'll never be able to reach "every" irrational number. Put another way, for a given alphabet there's no way to represent every irrational number in a finite way. However, you could have an irrational number that can be finitely represented in one alphabet, but unable to be finitely represented in another.
- pesenti 13y agowhat are the theoretical implications of the fact that any specific real must have a finite representation of some form? See http://en.wikipedia.org/wiki/Definable_number http://en.wikipedia.org/wiki/Definable_number
- colanderman 13y agoGreat, thanks! It's helpful to know that such definable numbers are in fact a superset of computable numbers [1]; I was naïvely assuming these notions to be equivalent. [1] http://en.wikipedia.org/wiki/Computable_number http://en.wikipedia.org/wiki/Computable_number